快排的扩展:如何对非数字对象排序
该视频从有趣视角介绍如何用快速排序对非数字对象(如rappers实力、三角恋关系)进行排序,展示快排的强大应用,并涉及相关经典论文。
做了一个视频(link),从一些有趣的视角出发去介绍一篇经典论文,内容包括- 如何对一群 rappers 按实力进行排序- 如何解决影视剧中”三角恋“的问题非数字对象这里的意思是 not transitive 。举个例子,a<b & b<c 并不意味着 a<c 。主要是想展示 快速排序 一些非常强大但却不太为人所知的应用。论文: Ailon, Nir, Moses Charikar, and Alantha Newman. "Aggregating inconsistent information: ranking and clustering." Journal of the ACM (JACM) 55, no. 5 (2008): 1-27.关键词:Quick Sort, KWIK Sort, Correlation Clustering, Minimum Feedback Arc Set