14 | 排序优化：如何实现一个通用的、高性能的排序函数.md

作者：鲁米

2023-12-07
北京
本文字数：2206 字
阅读完需：约 7 分钟

在今天的内容中，我分析了 C 语言的中的 qsort() 的底层排序算法，你能否分析一下你所熟悉的语言中的排序函数都是用什么排序算法实现的呢？都有哪些优化技巧？

Arrays.sort()

基本类型

public static void sort(int[] a) {    //双轴快速排序    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);}

复制代码

引用类型

public static void sort(Object[] a) {  //归并排序---1.8之后默认不在使用    if (LegacyMergeSort.userRequested)        legacyMergeSort(a);    else      //默认        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);}

复制代码

引用类型 + 自定义比较器

public static <T> void sort(T[] a, Comparator<? super T> c) {    if (c == null) {        sort(a);    } else {        if (LegacyMergeSort.userRequested)            legacyMergeSort(a, c);        else            TimSort.sort(a, 0, a.length, c, null, 0, 0);    }}

复制代码

TimSort.sort()

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,                     T[] work, int workBase, int workLen) {    // 参数检查    assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
    int nRemaining = hi - lo;    if (nRemaining < 2)        return;  // 数组大小为 0 或 1 时已经有序        // 如果数组较小，执行 "mini-TimSort"，即使用插入排序    if (nRemaining < MIN_MERGE) {        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);        binarySort(a, lo, hi, lo + initRunLen, c);        return;    }        // 创建 TimSort 对象    TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);    int minRun = minRunLength(nRemaining);        // 循环直到整个数组排序完成    do {        // 识别并扩展自然顺序的运行        int runLen = countRunAndMakeAscending(a, lo, hi, c);            // 如果运行较短，进行排序并扩展到 min(minRun, nRemaining)        if (runLen < minRun) {            int force = nRemaining <= minRun ? nRemaining : minRun;            binarySort(a, lo, lo + force, lo + runLen, c);            runLen = force;        }            // 将运行压入堆栈，并进行可能的合并        ts.pushRun(lo, runLen);        ts.mergeCollapse();            // 前进以找到下一个运行        lo += runLen;        nRemaining -= runLen;    } while (nRemaining != 0);        // 合并所有剩余的运行以完成排序    assert lo == hi;    ts.mergeForceCollapse();    assert ts.stackSize == 1;
}

复制代码

TimSort 算法思想

TimSort 是由 Tim Peters 在 2002 年设计的一种混合排序算法，主要用于对实际数据集进行排序。它结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的思想。

自适应性： TimSort 是一种自适应排序算法，能够根据输入数据的特性动态地调整算法的策略。对于已经有序或近似有序的数据集，TimSort 可以通过插入排序来提高性能。
归并排序和插入排序结合： TimSort 使用了归并排序的主要思想，即将数组递归地分成更小的子数组，对子数组进行排序，然后再将排好序的子数组合并。与此同时，对于较小的子数组，TimSort 使用插入排序来进行排序。
运行的定义： TimSort 将数组划分为多个运行（runs）。运行是连续递增或递减的子数组。通过找到并扩展这些运行，TimSort 为后续的归并操作做好准备。
最小运行长度： 为了保持性能，TimSort 限制运行的最小长度。较小的运行将通过插入排序进行排序，而不必进行完整的归并操作。
运行的合并： TimSort 使用一种特殊的归并策略，称为 galloping mode，以加速运行的合并。这种策略通过比较两个运行的首元素来确定是否可以直接合并，而不必进行完整的归并操作。
堆栈维护： 在 TimSort 的执行过程中，使用堆栈来维护运行的状态，以确保合并操作的正确性。

总体来说，TimSort 利用了归并排序的稳定性和可预测性，通过与插入排序的结合，使得它在实际应用中表现出色。其自适应性使得它能够在处理不同特性的数据时灵活地选择合适的策略，从而获得良好的性能。

DualPivotQuicksort 算法核心思想

DualPivotQuicksort 是一种改进的快速排序算法，用于对基本数据类型数组进行排序。相对于传统的快速排序，DualPivotQuicksort 使用了两个轴点（dual pivots）而不是一个，以提高性能。

选择两个轴点： DualPivotQuicksort 选择两个轴点作为划分数组的依据。通常，这两个轴点是数组的开头和结尾。
划分阶段： 在划分阶段，数组被划分为三个部分：
小于第一个轴点的元素。
介于两个轴点之间的元素。
大于第二个轴点的元素。这种划分方式有助于处理包含大量相同元素的数组。
递归排序： 对划分后的三个部分分别进行递归排序。由于划分的三个部分的大小通常是不等的，这种排序策略有助于避免对大量相同元素的多次排序。
插入排序优化： 对于较小的子数组，DualPivotQuicksort 使用插入排序来提高性能。这是因为插入排序对小规模数据的排序效果较好。

总体来说，DualPivotQuicksort 的核心思想是通过使用两个轴点，将数组划分为三个部分，从而提高排序的效率，特别是在处理包含大量相同元素的数组时。这种改进使得 DualPivotQuicksort 在实际应用中表现得相当高效。

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/6153799a61ec46c0fa7291766】。

鲁米

关注

生活黑客35 2019-06-11 加入

起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。

发布

暂无评论

创作场景

14 | 排序优化：如何实现一个通用的、高性能的排序函数.md

Arrays.sort()

基本类型

引用类型

引用类型 + 自定义比较器

TimSort.sort()

TimSort 算法思想

DualPivotQuicksort 算法核心思想

鲁米

评论