归并排序应用之Kendall tau distance
这里主要讲我对kendall tau distance的理解,以及如何把merge sort应用到此场景,如果大家对merge sort的基本概念不熟悉的话建议先了解一下它的工作原理.
在讲kentall tau之前,我先抛出一个问题:如何判断两组排列的相似性.注意,这里用到的术语是排列,而不是序列或列表.我们知道排列是对同一组数据在位置上的编排,而序列或列表则没有此类约束.比如,我们可以比较如下两组数据:
java
3,5,7,12,4,1
7,5,1,4,3,12