Java Sort中Comparator的语义分析

Comparator中compare的语义： 接口约定返回值与o1,o2的相对大小的对应关系， 即ret<0时，语义上等价于o1<o2; ret==0时，语义上等价于o1==o2; ret>0时，语义上等价于o1>o2. 具体Comparator子类override compare函数时，则需要依据约定，即采用o1-o2的策略 上述语义约定在排序算法上会有何影响呢？以JDK7为例，分析Collection.sort的内部实现 阐述下sort与compare约定的关系。一般Comparator的用法如下： 其调用关系如下： 核心调用为 老版本使用归并排序(属于稳定排序，性能弱于快排)，新版本使用TimSort排序(一种改良的归并排序算法，其算法复杂度为O(nlogn), 空间复杂度为n/2，在随机数组中性能较优)，介绍如下： 此处不赘述这两种算法的实现细节，只关注comparator在排序中的语义作用。以传统归并实现为例： c.compare>0时交换dest[j-1]和dest[j]，排序时有升序和降序之分，升还是降由compare的规则决定， 即，若compare(dest[j-1], dest[j])>0内部规则为dest[j-1] > dest[j]，导致small value在数组左侧，即升序； 若compare>0内部规则为dest[j] > dest[j-1], 导致small value在数组右侧，即降序。 总结一下： 1.Collections.sort内部采用(改良)归并排序算法 2.Collections.sort排序算法定义了规则：compare<=0时value位置不变，compare>0时交换位置 3.compare(o1, o2)其中o1对应dest[j-1]，o2对应dest[j]，分别代表数组中相邻比较的左右值 4.采用o1-o2方式结合排序内部规则，导致升序，o2-o1导致降序

转载于:https://www.cnblogs.com/tonybright/p/4903006.html

总结

以上是生活随笔为你收集整理的Java Sort中Comparator的语义分析的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。