十大排序从入门到入赘

从今天起，与「排序」一刀两断。
前几天在讨论区上发布的如下两篇文章反馈良好（二分查找那篇一周内 阅读量 9k+ 收藏800+ 点赞近200 👀，虽然并查集我写得更用心…🧐）。

• 二分查找从入门到入睡
• 并查集从入门到出门(以并查集发明人的视角)

这让我进一步相信基础知识的总结和分享确实很有一部分受众，于是趁热打铁，连夜推出本文。我(几乎)可以肯定，你在别处(基本上)看不到比本文更深入更广泛地网罗「十大排序」方方面面的文章，如果有，我就把这句话划掉。

「排序」十分基础，但内容庞杂，网上做全面介绍的资料不可谓不多，但我所看过的材料，总是在这一处或那一处上有所遗憾。比如复杂度缺少证明，比如优化版本未给出，比如缺少便于理解的图示，或者干脆就是到处复制粘贴错误百出的公众号引流文等等等等。因此上作者试图（企图）在「面试」这一层面上，彻底对排序做一个了断，使得面试官(几乎)不可能问得比本文内容更深更广（如果你是面试官，我劝你别看👊😅）。

本文设想的读者应当是初学排序的同学，以及想对「排序」做一点查漏补缺工作的朋友，比如你突然想不起「双轴快排」该如何实现（对你竟然想要徒手实现双轴快排，我起立致敬🫡），或者「计数排序」稳不稳定，又或者「自底向上归并」该怎么写，你都可以在文中找到相应的答案。不过即便你就是纳闷，“不就是「排序」吗，自己随便看看不就好了，有什么好说的，还搞得这么煞有介事”，也十分欢迎你给出一些指导意见。

本文标题意在表达作者的一种希望，即看完本文，读者觉得确实有些帮助，甚或令七尺男儿拍案，以至于 「想嫁」 的心都有了，那就算对得起作者案头那把 键帽斑驳的双飞燕键盘 了。

发文的本心首要是向大家学习，其次是分享(一点微不足道)的心得。仍旧希望大家不吝赐教，你所指出的每一个错误，我都会立即更正。

本文主要内容（特色）如下：
内容(应该还算)全面。具体如下。

• 给出swap的三种实现。
• 给出十大排序中后面贴出的思维图所列的所有实现。
• 所有代码均经过验证，注释关键语句，力求所见即所得，贴到IDE上就能跑。
• 给出十大排序的所有稳定性和时空复杂度结论和分析证明。
• 在「希尔排序」中讨论了逆序数。
• 在「归并排序」中分析了 自顶向下/自底向上/原地/非原地 各情形排序过程，并给出各自的实现代码。
• 在「归并排序」中讨论了「手摇算法」。
• 在「快速排序」中讨论了三种基于不同轴选择的单轴快排（首位轴/随即轴/三数取中轴）并给出相应实现代码。分析给出了利用栈实现的迭代方式的快排。给出并逐行分析了「双轴快排」的代码。
• 讨论了「计数排序」的稳定性。
• 分别给出了基于计数排序和不基于计数排序的「基数排序」实现。
• 从「决策树」角度分析并证明了基于「比较」的排序时间复杂度下界为O(nlogn)O(nlogn)。
• 贴出「Stiring公式」的详细证明文章链接。

叙述(应该还算)准确。本文力求言必有据，所有性质，包括各类排序的稳定性，时空复杂度等关键信息，或给出例子，或给出图示，或严格证明，总之尽力拒绝模糊。
制作(应该还算)精良，公式一概以 LaTeX 编辑。有多处方便记忆的汇总表格。有大量图示，动图静图，有助于理解之处尽附详图。

排序分类

※1：输入数组已排序时最好。
※2: 时间复杂度与输入数组特点无关。
※3: 输入数组已排序时最好。
※4: 复杂度取决于增量序列，上为希尔增量，
    下为Knuth增量。输入数组已排序时最好。
※5: 所列复杂度为自顶向下非原地版本。
    自顶向下/自底向上，非原地/原地的时间空间复杂度见相应章节。
※6: 当输入数组有序，且总是选取第一个元素为主轴时，
    时间复杂度退化为O(n^2)。空间开销为递归深度。
※7: 原地堆排序空间复杂度为O(1)。输入数组所有数字相等时，
    时间复杂度为O(n)。
※8: k是计数数组大小。应用稳定性优化则稳定，否则不稳定。
    朴素版本空间复杂度为O(k)，稳定性优化版本空间复杂度为O(n + k)。
※9: d是最大数位数，k是计数数组大小，处理负数时k=19。
    采用稳定的计数排序则稳定，否则不稳定。
※10:稳定性取决于桶内排序是否稳定。空间取决于桶使用数组还是容器，
    若采用数组为O(kn)，容器则为O(n)。所有元素放入同一个桶时复杂度最大。

稳定性：当存在稳定和不稳定版本时，写为「稳定」。

三种交换方法

对于冒泡、选择、插入等采用比较和交换元素的排序方法，由于经常执行交换操作，通常将交换动作写为swap方法，需要交换时调用。最常见swap写法是利用一个临时数tmp来交换arr[i]，arr[j]。也可以通过arr[i]和和arr[j]的加减运算避免临时数tmp的开销，但由于涉及到加减法可能导致数字越界。第三种方法利用位运算中的异或运算，能够避免tmp的开销且不会导致数字越界。

// 方法一: 利用临时数tmp
private void swapWithTmp(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
// 方法二: 利用加减运算
private void swapByCal(int[] arr, int i, int j) {
    arr[i] = arr[i] + arr[j]; // a = a + b
    arr[j] = arr[i] - arr[j]; // b = a - b
    arr[i] = arr[i] - arr[j]; // a = a - b
}
// 方法三: 利用异或运算
private void swapXOR(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j]; // a = a ^ b，也可写成 arr[i] ^= arr[j];
    arr[j] = arr[i] ^ arr[j]; // b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a， 也可写成 arr[j] ^= arr[i];
    arr[i] = arr[i] ^ arr[j]; // a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b， 也可写成 arr[i] ^= arr[j];
}

冒泡排序

算法描述

对于要排序的数组，从第一位开始从前往后比较相邻两个数字，若前者大，则交换两数字位置，然后比较位向右移动一位。也就是比较arr[0]和arr[1]，若arr[0] > arr[1]，交换arr[0]和arr[1]。接着比较位移动一位，比较arr[1]和arr[2]，直到比较到arr[n - 2]和arr[n - 1] (n = arr.length)。第1轮从前到后的比较将使得最大的数字 冒泡 到最后，此时可以说一个数字已经被排序。每一轮的比较将使得当前未排序数字中的最大者被排序，未排序数字总数减1。第arr.length - 1轮结束后排序完成。

如下动图展示了{4,6,2,1,7,9,5,8,3}的冒泡排序过程（未应用优化）。
优化
提前结束优化

当某一轮比较均未发生交换，说明排序已完成，可设置一个布尔值记录一轮排序是否有发生交换，若无则提前退出循环结束程序。
冒泡界优化
记录前一轮交换的最终位置，说明该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。
复杂度分析
时间复杂度：两层for循环，第1轮比较 n - 1 次(n = arr.length)，最后一轮比较1次。总比较次数为 n*(n - 1) / 2n∗(n−1)/2 次，时间复杂度为 O(n^2)O(n 
2
 )。当输入数组为已排序状态时，在应用提前结束优化的情况下，只需一轮比较，此时为最佳时间复杂度 O(n)O(n)。

空间复杂度：算法中只有常数项变量，O(1)O(1)。

代码
无优化的基本冒泡排序代码此处不列出。
提前结束优化

public int[] bubbleSort(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1轮次执行，当前 n - 1 个元素排好后，最后一个元素无需执行，故i < arr.length - 1
    for (int i = 0; i < arr.length - 1; i++) {
        // 本轮执行是否有交换的标志，若无则false，若有则true
        boolean swapped = false;
        // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右
        for (int j = 1; j < arr.length - i; j++) {
            // 若左大于右则交换，并将swapped置为true
            if (arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
                swapped = true;
            }
        }
        // 若无交换，表示当前数组已完全排序，退出大循环
        if (!swapped) break;
    }
    return arr;
}

提前结束+冒泡界优化

public int[] bubbleSort(int[] arr) {
    if (arr.length < 2) return arr;
    boolean swapped = true;
    int lastSwappedIdx = arr.length - 1 ;
    int swappedIdx = -1;
    // lastSwappedIdx表示前一轮交换的最终位置，即下标为lastSwappedIdx是未排序部分中的最后一个数的下标，
    // 因此for中的界是i < lastSwappedIdx而不需要写成i <= lastSwappedIdx
    while (swapped) { // 当swapped = false时，排序完成
        // 本轮执行是否有交换的标志，若无则true，若有则false
        swapped = false;
        // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右
        for (int i = 0; i < lastSwappedIdx; i++) {
            // 若左大于右则交换，并将swapped置为true
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                swapped = true;
                swappedIdx = i;
            }
        }
        lastSwappedIdx = swappedIdx;
    }
    return arr;
}

选择排序
算法描述
对于要排序的数组，设置一个minIdx记录最小数字下标。先假设第1个数字最小，此时minIdx = 0，将arr[minIdx]与后续数字逐一比较，当遇到更小的数字时，使minIdx等于该数字下标，第1轮比较将找出此时数组中最小的数字。找到后将minIdx下标的数字与第1个数字交换，此时称一个数字已被排序。然后开始第2轮比较，令minIdx = 1，重复上述过程。每一轮的比较将使得当前未排序数字中的最小者被排序，未排序数字总数减1。第arr.length - 1轮结束后排序完成。

如下动图展示了{4,6,2,1,7,9,5,8,3}的选择排序过程（单元选择）。

微优化：在交换前判断minIdx是否有变化，若无变化则无需交换。当数组大致有序时，能够减少无效交换带来的开销。
稳定性：不稳定。
存在跨越交换。找到本轮次最小值之后，将其与本轮起始数字交换，此时若中间有与起始元素同值的元素，将打破稳定性。

例:　7 7 2 。第一轮交换第一个7和2，则两个7位置关系改变。
双元选择优化
在遍历寻找最小值下标minIdx时，可以同时寻找最大值下标maxIdx，这样就可以一轮遍历确定两个元素的位置，遍历次数减少一半，但每轮次的操作变多，因此该优化只能少量提升选择排序的速度（复杂度介于单元选择排序复杂度及其一半之间，只有系数上的区别）。

复杂度分析
时间复杂度：两层for循环，第1轮比较 n - 1 次(n = arr.length)，最后一轮比较1次。总比较次数为 n*(n - 1) / 2n∗(n−1)/2 次，时间复杂度为 O(n^2)O(n 2 )。 双元选择优化版本也是 O(n^2)O(n 2 )。
冒泡排序和选择排序的比较次数均为 O(n^2)O(n 2)，但选择排序的交换次数是 O(n)O(n)，而冒泡排序的平均交换次数仍然是二次的。
空间复杂度：算法中只有常数项变量，O(1)O(1)。
代码
单元选择排序

public int[] selectSort(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1 轮次执行,当前 n - 1 个元素排好后，最后一个元素无需执行，故 i < arr.length - 1
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        // 找到本轮执行中最小的元素，将最小值下标赋值给min
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx])  minIdx = j;
        }
        // 若本轮第一个数字不是最小值，则交换位置
        if (minIdx != i) swap(arr, i, minIdx);
    }
    return arr;
}

双元选择排序

public int[] selectSort(int[] arr) {
    if (arr.length < 2) return arr;
    // 每轮确定两个数字，因此界也会动态变化
    for (int i = 0; i < arr.length - 1 - i; i++) {
        int minIdx = i, maxIdx = i;
        // 找到本轮执行中最小和最大的元素
        for (int j = i + 1; j < arr.length - i; j++) {
            if(arr[j] < arr[minIdx]) minIdx = j;
            if(arr[j] > arr[maxIdx]) maxIdx = j;
        }
        // 若本轮最大值等于最小值，说明未排序部分所有元素相等，无需再排序
        if(minIdx == maxIdx) break;
        // 若本轮第一个数字不是最小值，则交换位置
        if (minIdx != i) swap(arr, i, minIdx);
        // 在交换i和minIdx时，有可能出现i即maxIdx的情况，此时需要修改maxIdx为minIdx
        if(maxIdx == i) maxIdx = minIdx;
        // 若本轮第一个数字不是最大值，则交换位置（将最大值与本轮最后一个数字交换位置）
        if (maxIdx != i) swap(arr, arr.length - 1 - i, maxIdx);
    }
    return arr;
}

插入排序
算法描述
对于待排序数组，从第2个元素开始(称作插入对象元素)，比较它与之前的元素(称作比较对象元素)，当插入对象元素小于比较对象元素时，继续往前比较，直到不小于(≥)比较对象，此时将插入对象元素插入到该次比较对象元素之后。重复这个插入过程直到最后一个元素作为插入对象元素完成插入操作。
如下动图展示了{4,6,2,1,7,9,5,8,3}的简单插入排序过程。
稳定性：简单插入和折半插入(二分插入)排序是稳定的。

对于大小相同的两个数字，简单插入和折半插入均使得后来的数字靠右放置 （因为条件是 ≥），因此不会改变其相对位置。

折半插入优化
注意到插入排序的每一轮向前插入都使得该元素在完成插入后，从第一个元素到该元素是排序状态（指这部分的相对排序状态，在它们中间后续可能还会插入其他数字），利用这一点，对一个新的插入对象向前执行折半插入，能够显著减少比较的次数。另一种优化是增量递减插入排序，也叫希尔排序，将在希尔排序章节中介绍。

折半插入的关键在于找到插入位置，折半过程代码如下。这实际上是二分查找「模版一」中的「小于等于」情形。如果你尚不能熟练且准确地写出如下代码，这可能是因为对二分查找写法不熟悉，推荐阅读我写的这篇文章: 二分查找从入门到入睡。

while (low <= high) {
    int center = low + (high - low) / 2;
    if (arr[center] <= target) low = center + 1;
    else high = center - 1;
}

复杂度分析
时间复杂度：两层for循环，外层总轮次为n - 1轮(n = arr.length)，当原数组逆序时，移动次数为 n*(n - 1) / 2n∗(n−1)/2 次，最坏时间复杂度为 O(n^2)O(n 2 )，平均时间复杂度同为 O(n^2)O(n 2)。当原数组已基本有序时，接近线性复杂度 O(n)O(n)。例如原数组已完全排序，则算法只需比较 n - 1 次。

※ 折半插入总的查找(比较)次数虽为 O(nlogn)O(nlogn)，但平均移动 (每轮移动一半的数字) 次数仍是 O(n^2)O(n 2)。

空间复杂度：算法中只有常数项变量，O(1)O(1)。

代码
简单插入排序

public int[] insertSort(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1轮次执行
    for (int i = 1; i < arr.length; i++) {
        int target = arr[i], j = i - 1;
        for (; j >= 0; j--) {
            if(target < arr[j]) arr[j + 1] = arr[j];
            else break;
        }
        // j变动表示发生了移动，此时的插入对象数字 ≥ j位置的数字，故插入位置为j + 1
        if (j != i - 1) arr[j + 1] = target; 
    }
    return arr;
}

折半插入排序

public int[] insertSortBinary(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1 轮次执行
    for (int i = 1; i < arr.length; i++) {
        // 若当前插入对象大于等于前一个对象，无需插入
        if (arr[i - 1] <= arr[i]) continue;
        int target = arr[i];
        // 折半查找 (二分查找「模版一」)
        int low = 0, high = i - 1;
        // while结束后，target要插入的位置为low或high + 1 (low = high + 1)
        while (low <= high) {
            int center = low + (high - low) / 2;
            if (arr[center] <= target) low = center + 1;
            else high = center - 1;
        }
        for (int j = i; j > low; j--) { // 移动
            arr[j] = arr[j - 1];
        }
        arr[low] = target; // 插入
    }
    return arr;
}

希尔排序
算法描述
希尔排序是简单插入排序的改进，它基于以下事实。

简单插入排序对排序程度较高的序列有较高的效率。假设初始序列已完全排序，则每一轮均只需比较一次，将得到 O(n)O(n) 的线性复杂度，冒泡排序和选择排序做不到这一点，均仍需 O(n^2)O(n 
2
 ) 次比较(冒泡排序在应用提前结束优化后可以做到)。
简单插入排序每次比较最多将数字移动一位，效率较低。
Donald Shell在1959年发表的论文中，针对第二点，提出如下方法。对原待排序列中相隔 gap 的数字执行简单插入排序，然后缩小 gap，对新的 gap 间隔的数字再次执行简单插入排序。以一种规则减少 gap 的大小，当 gap 为1时即简单插入排序，因此希尔排序也称作 增量递减排序。希尔在论文中提出的增量序列为{1, 2, 4, 8,...}，即2^k，k = 1, 2, 3, ...，在讨论希尔排序时，可将其称为 希尔增量。

程序开始时 gap 较大，待排元素较少，因此排序速度较快。当 gap 较小时，基于第一点，此时待排序列已大致有序，排序效率接近线性复杂度。因此能够期待希尔排序复杂度将优于 O(n^2)。详细见「复杂度分析」。

稳定性：不稳定。

gap > 1时，跨越gap的插入可能会改变两个相同值元素的位置关系。例如{0, 1, 4, 3, 3, 5, 6}，当gap = 2时，对{0, 4, 3, 6}简单插入排序后得到{0, 1, 3, 3, 4, 5, 6}，原数组中的两个3的位置互换了。

复杂度分析
时间复杂度：希尔排序的时间复杂度与增量序列的选择有关。最优复杂度增量序列尚未明确。

Shell增量(Shell, 1959): {1, 2, 4, 8,...}，即 2^k2 k，k = 1, 2, 3, ...，最坏时间复杂度 Θ(n^2)Θ(n 2)。

Hibbard增量(Hibbard, 1963)：{1, 3, 7, 15,...}，即 2^k - 12 k −1，k = 1, 2, 3, ...，最坏时间复杂度 Θ(n^\frac{3}{2})Θ(n 23)。

Knuth增量(Knuth, 1971)：{1, 4, 13, 40,...}，即 (3^k - 1) / 2(3 k −1)/2，k = 1, 2, 3, ...，最坏时间复杂度 Θ(n^\frac{3}{2})Θ(n 23 )。

Sedgewick增量(Sedgewick, 1982): {1, 8, 23, 77, 281}，即 4^k + 3*2^(k-1) + 14 k +3∗2 ( k−1)+1 (最小增量1直接给出)，k = 1, 2, 3, ...，最坏时间复杂度 Θ(n^\frac{4}{3})Θ(n 34 )。

复杂度的证明需要借助数论和组合数学，略 (我不会)。

空间复杂度：算法中只有常数项变量，O(1)O(1)。

逆序数
希尔排序是较早出现的 突破二次复杂度 的排序算法，下面从 逆序数 的角度来直观地证明为何希尔排序能够突破二次复杂度。

在一个排列中，如果任意一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个 逆序，一个排列中逆序的总数就称为这个排列的 逆序数。排序的过程就是不断减少逆序数 直到逆序数为 0 的过程。

回顾冒泡排序和简单插入排序，算法的每一次交换，都只交换相邻元素（简单插入排序中元素每次右移也看作交换），因此每次交换只能减少一个逆序。冒泡排序和简单插入排序的元素平均交换次数均为 O(n^2)O(n 2)， 也即逆序数(或逆序数减少次数)为 O(n^2)O(n 2 )。 如果能跨越多个数字进行交换，则可能一次减少多个逆序。在选择排序中，每轮选到最小元素后的交换即是跨越多个元素的，交换次数(减少逆序数的操作)为 O(n)O(n)，要少于冒泡和简单插入排序，只是因为比较次数仍是 O(n^2)O(n 2 )， 所以整体复杂度为 O(n^2)O(n 2 )。

现在来分析跨越多个元素的交换如何减少逆序数，假设 arr[i] > arr[j], i < j。对于任意的 arr[k] (i < k < j)：

若 arr[k] < arr[j]，交换 arr[i] 和 arr[j] 后，三者的逆序数从2变为1
若 arr[k] > arr[i]，交换 arr[i] 和 arr[j] 后，三者的逆序数从2变为1
若 arr[i] > arr[k] > arr[j]，交换 arr[i] 和 arr[j] 后，三者的逆序数从3变为0
arr[k] = arr[i] 或 arr[k] = arr[j] 的情况一样，都使得三者逆序数从2变为1，下图省略。



对 arr[i] 和 arr[j] 的逆序消除，使得逆序 至少 减少一次，并 有机会减少大于一次的逆序 (情况3)，因此能够以比 n^2n 2  低阶的次数消除所有逆序。
实际上归并排序，快速排序，堆排序均实现了 长距离交换元素，使得复杂度优于 O(n^2)。
代码

// 希尔排序： 采用Knuth增量
public int[] shellSort(int[] arr) {
    if (arr.length < 2) return arr;
    int gap = 1; // 初始化gap
    while (gap < arr.length / 3) { // Knuth增量序列
        gap = gap * 3 + 1;
    }
    // 不断缩小gap直到1，对每一个gap值执行一次插入排序
    while (gap > 0) {
        for (int i = gap; i < arr.length; i += gap) { // 注意步长增量是gap
            int target = arr[i], j = i - gap;
            for (; j >= 0; j -= gap) { 
                 if (target < arr[j]) arr[j + gap] = arr[j];
                 else break; 
            }
            if (j != i - gap) arr[j + gap] = target; // 插入
        }
        gap /= 3; // 缩小gap值
    }
    return arr;
}

归并排序
算法描述
归并排序是 分治思想 的应用，即将原待排数组 递归或迭代地 分为左右两半，直到数组长度为1，然后对左右数组进行合并(merge)，在合并中完成排序。详细过程需结合代码理解，如下动图展示了{4,6,2,1,7,9,5,8,3}的归并排序过程（自顶向下非原地）。合并过程采用 非原地 合并方法，即依次比较两部分已排序数组，将比较结果依次写入 新空间 中。后续会介绍一种称作 原地(in-place) 归并排序的改进，使得空间复杂度达到 常数级 (自底向上时，O(1)O(1))。
如下树状图中的橙色线表示递归的轨迹（自顶向下递归归并排序）。

稳定性：稳定。

合并时的此判断中的等号if(left[l_next] <= right[r_next])，保证了出现相等元素时，居左的元素总会被放在左侧，稳定性不受影响。
自顶向下和自底向上
可以通过 自顶向下(top-down) 或 自底向上(bottom-up) 的方式实现归并排序。

自顶向下(top-down)：从输入数组出发，不断二分该数组，直到数组长度为1，再执行合并。适合用 递归 实现。

自底向上(bottom-up)：从输入数组的单个元素出发，一一合并，二二合并，四四合并直到数组有序。适合用 迭代 实现。

后续给出 自顶向下原地 / 自顶向下非原地 / 自底向上原地 / 自底向上非原地 四种代码实现。
原地归并
前述归并排序，每一次合并都是将两部分待合并数组的比较结果写入一个与arr等大小的临时数组tmpArr中，写入后再将tmpArr中的合并结果写回到arr中。于是tmpArr的空间开销即为该实现的空间复杂度，为 O(n)O(n)。实际上，通过一种 原地旋转交换 的方法（俗称手摇算法/内存反转算法/三重反转算法），则只需要 O(1)O(1) 的辅助空间（由于递归空间为 O(logn)O(logn)，其总的空间复杂度仍为 O(logn)O(logn)）。以下介绍旋转交换的实现方法。

以b4b5b6a1a2a3序列为例，欲将b4b5b6和a1a2a3交换位置转换为a1a2a3b4b5b6，只需要执行三次旋转即可：

旋转b4b5b6，得到b6b5b4
旋转a1a2a3，得到a3a2a1
旋转b6b5b4a3a2a1得到a1a2a3b4b5b6。
以{1, 2, 4, 6, 7}与{3, 5, 8, 9}的合并为例，观察借助手摇算法实现原地归并的过程。

在{1, 2, 4, 6, 7}中找到第一个大于3的数4，其下标为2，i = 2。index = j = 5。在{3, 5, 8, 9}中找到第一个大于arr[i] = arr[2] = 4的数5，其下标为6，j = 6。
如上操作使得[0, i - 1]必是最小序列，[index, j - 1]必小于arr[i]。因此交换[i, index - 1]和[index, j - 1]（采用三次旋转完成交换）能够使得原右边数组中某一段序列插入到左边数组中，使得这部分序列在整个数组中有序。
交换后，继续执行上述过程，直到不满足该条件 ：i < j && j <= rightEnd。

复杂度分析
自顶向下非原地
时间复杂度

每次减半后的左右两半对应元素的对比(if(left[l_next] <= right[r_next]))和赋值(resArr[res_next++] = ??? )总是必须的，也即在每一层递归中(这里的一层指的是 递归树 中的层)，比较和赋值的时间复杂度都是 O(n)O(n)，数组规模减半次数为 lognlogn，即递归深度为 lognlogn，也即总共需要 lognlogn 次 O(n)O(n) 的比较和赋值，时间复杂度为 O(nlogn)O(nlogn)。

也可以这样求解。当 n=1 时，排序只需常数时间，可以记为 1。n个元素的归并排序时间由 n/2 个元素的归并排序的两倍，再加上将两个n/2大小的已排序数比较及合并的耗时得到。得到如下两个式子(第2个式子加号右边的 n 表示比较及合并的时间)。

空间复杂度

递归深度为 lognlogn，递归过程中需要一个长度为 n 的临时数组保存中间结果，空间复杂度为 O(n)O(n)。

自顶向下原地
时间复杂度
该方式的时间复杂度计算参考了此篇文章。
当序列为 链表 时，手摇算法只需做如下指针调整即可（只做示意，非实际代码）。

双向链表时：
tmp = index.prev 
index.prev = i.prev
i.prev = j.prev
j.prev = tmp

单向链表时：
(i-1).next = index
(index-1).next = j
(j-1).next = i

对于长度为 n 的序列，手摇算法操作元素个数至多不超过 n/2 个，容易得到下述递推式。



由前述计算方法可复杂度为 O(nlogn)O(nlogn)。

当序列为数组时，以 {1,3,5,7,...k} 和 {2,4,6,8,...,n} 的手摇合并为例，对于长度为 n 的序列，一次手摇算法需要对一半规模（非严格的一半）的元素进行翻转（翻转两次）。例如第一次手摇，需翻转{3, ..., k}和{2}（ {2} 只有一个元素，实际不翻转）得到 {k, ..., 3} 和 {2} ，然后再翻转 {k, ..., 3, 2} 得到 {2, 3, ..., k}。下一次手摇对象是{5, ..., k}和{4}，翻转元素个数相比上一次减少一个，可知完成 {1,3,5,7,...k} 和 {2,4,6,8,...,n} 的手摇合并所需要的对元素的翻转次数是 c*n^2c∗n 2  (等差数列求和，c是一常数)，于是有下列递推式。

空间复杂度

递归深度为 lognlogn，手摇算法仅需 O(1)O(1) 的辅助空间，综合来看空间复杂度为 O(logn)O(logn)。

自底向上非原地 & 自底向上原地
时间复杂度

同自顶向下非原地/原地的分析类似，只是程序运行过程从递归变为了迭代。

空间复杂度

自底向上非原地归并：迭代过程中需要一个长度为 n 的临时数组保存中间结果，空间复杂度为 O(n)O(n)。

自底向上原地归并：手摇算法仅需 O(1)O(1) 的辅助空间，其他空间开销均为常数级，空间复杂度为 O(1)O(1)。

总结
四种归并排序的时空复杂度总结如下（待排序序列是数组形式，不考虑链表形式）。

根据上述分析，原地相比非原地，空间消耗较少，采用自底向上原地归并排序时空间复杂度为常数级 O(1O(1)，但需要 O(n^2)O(n 2 ) 的时间复杂度。是一种以时间换空间的做法，通常空间不为瓶颈时，应采用 效率更高的非原地归并排序。
代码
自顶向下非原地归并

public int[] mergeSort(int[] arr) {
    if (arr.length < 2) return arr;
    int[] tmpArr = new int[arr.length];
    mergeSort(arr, tmpArr, 0, arr.length - 1);
    return arr;
}

private void mergeSort(int[] arr, int[] tmpArr, int left, int right) {
    if(left < right) {
        int center = left + (right - left) / 2;
        mergeSort(arr, tmpArr, left, center);
        mergeSort(arr, tmpArr, center + 1, right);
        merge(arr, tmpArr, left, center, right);
    }
}

// 非原地合并方法
private void merge(int[] arr, int[] tmpArr, int leftPos, int leftEnd, int rightEnd) {
    int rightPos = leftEnd + 1;
    int startIdx = leftPos;
    int tmpPos = leftPos;
    while (leftPos <= leftEnd && rightPos <= rightEnd) {
        if (arr[leftPos] <= arr[rightPos]) {
            tmpArr[tmpPos++] = arr[leftPos++];
        }
        else {
            tmpArr[tmpPos++] = arr[rightPos++];
        }
    }
    // 比较完成后若左数组还有剩余，则将其添加到tmpArr剩余空间
    while (leftPos <= leftEnd) {
        tmpArr[tmpPos++] = arr[leftPos++];
    }
    // 比较完成后若右数组还有剩余，则将其添加到tmpArr剩余空间
    while (rightPos <= rightEnd) {
        tmpArr[tmpPos++] = arr[rightPos++];
    }
    // 容易遗漏的步骤，将tmpArr拷回arr中
    // 从小区间排序到大区间排序，大区间包含原来的小区间，需要从arr再对应比较排序到tmpArr中，
    // 所以arr也需要动态更新为排序状态，即随时将tmpArr拷回到arr中
    for(int i = startIdx; i <= rightEnd; i++) {
        arr[i] = tmpArr[i];
    }
}

自顶向下原地归并

public int[] mergeSort(int[] arr) {
    if (arr.length < 2) return arr;
    mergeSort(arr, 0, arr.length - 1);
    return arr;
}

private void mergeSort(int[] arr, int left, int right) {
    if(left < right) {
        int center = (left + right) / 2;
        mergeSort(arr, left, center);
        mergeSort(arr, center + 1, right);
        merge(arr, left, center, right);
    }
}

/**
 * 原地排序的合并方法
 * #1. 对左右两部分已排序数组，记左数组第一个数下标为i，记右数组第一个数下标为j
 * #2. 找到左数组中第一个大于右数组第一个数字的数，记其下标为i
 * #3. 以index暂存右数组第一个元素的下标index = j，
 * #4. 找到右数组中第一个大于arr[i]的数，记其下标为j
 * #5. 交换[i, index-1]和[index, j]数字，通过三次翻转实现，翻转[i, index-1]，翻转[index, j]，翻转[i, j]
 * 重复上述过程直到不满足(i < j && j <= rightEnd)
 */
private void merge(int[] arr, int leftPos, int leftEnd, int rightEnd) {
    int i = leftPos, j = leftEnd + 1; // #1
    while(i < j && j <= rightEnd) {
        while(i < j && arr[i] <= arr[j]) i++; // #2
        int index = j; // #3
        while(j <= rightEnd && arr[j] < arr[i]) j++; // #4
        exchange(arr, i, index - 1, j - 1); // #5
    }
}

// 三次翻转实现交换
private void exchange(int[] arr, int left, int leftEnd, int rightEnd) {
    reverse(arr, left, leftEnd);
    reverse(arr, leftEnd + 1, rightEnd);
    reverse(arr, left, rightEnd);
}

private void reverse(int[] arr, int start, int end) {
    while(start < end) {
        swap(arr, start, end);
        start++;
        end--;
    }
}

自底向上非原地归并

public int[] mergeSortBU(int[] arr) {
    if (arr.length < 2) return arr;
    int[] tmpArr = new int[arr.length];
    // 间隔，注意不能写成gap < arr.length / 2 + 1，此种写法只适用于元素个数为2的n次幂时
    for(int gap = 1; gap < arr.length; gap *= 2) {
        // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...)
        for(int left = 0; left < arr.length - gap; left += 2 * gap) {
            // 调用非原地合并方法。leftEnd = left+gap-1; rightEnd = left+2*gap-1;
            merge(arr, tmpArr, left, left + gap - 1, Math.min(left + 2 * gap - 1, arr.length - 1));
        }
    }
    return arr;
}

自底向上原地归并

public int[] mergeSortBUInPlace(int[] arr) {
    if (arr.length < 2) return arr;
    // 间隔，注意不能写成gap < arr.length / 2 + 1，此种写法只适用于元素个数为2的n次幂时
    for(int gap = 1; gap < arr.length; gap *= 2) {
        // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...)
        for(int left = 0; left < arr.length - gap; left += 2 * gap) {
            // 调用原地合并方法。leftEnd = left+gap-1; rightEnd = left+2*gap-1;
            merge(arr, left, left + gap - 1, Math.min(left + 2 * gap - 1, arr.length - 1));
        }
    }
    return arr;
}

快速排序
算法描述
与归并排序一样，快速排序也是一种利用 分治思想 的排序方法，确定 主轴及分区 是快速排序的核心操作。首先在数组中确定一个主轴元素(下标记为pivot)，然后将数组分为两部分，小于主轴的放在（确定最终位置的）主轴左侧，大于等于主轴的放在主轴右侧。递归地对主轴左右两侧数组执行这个过程，每次递归都传入待排序数组arr和本次要处理的部分的左右界，只处理这个范围内的序列。当所有递归都到达基准情形时，排序完成。因为是原地交换，递归过程中arr总是在动态排序，递归过程无需返回，为尾递归形式。

详细过程需结合代码理解，如下动图展示了{4,6,2,1,7,9,5,8,3}的快速排序过程（以起始元素为主轴）。

主轴的选择

主轴为起始元素 (quickSortSimple)。每次选取当前数组第一个元素作为主轴。
优点：实现简单。
缺点：若输入是较为有序的数组，pivot总是不能均匀地分割数组。若输入数组本身有序，复杂度退化到 O(n^2)O(n 
2
 )。
主轴为随机下标元素 (quickSortRandom)。每次随机选取当前数组的下标，将该下标元素作为主轴。
优点：避免了主轴为起始元素时对于基本有序的输入，因不能均匀分割数组导致复杂度退化的情况。
缺点：随机数的选取本身消耗一定的性能。
主轴为左中右三数大小居中者 (quickSortMedian3)。每次比较当前数组起始、中间和末尾三个元素的大小，大小居中者为主轴。
优点：实现相对简单，且有效避免简单快排中的 劣质分割。
缺点：三数取中方法消耗一定性能。
快速排序也可以与其他排序相结合，例如当元素较少时使用简单插入排序能够获得更高的排序效率，实际上这就是JDK的做法，这里不展开介绍。

分区方法(partition)

快速排序中的 核心方法为partition。partition方法执行后，要实现主轴左边元素均小于主轴，主轴右边元素均大等于主轴元素。

选定一个数作为主轴后（无论是上述哪种方法选取主轴元素，都将选定的主轴置于当前数组的起始位置），设置一个 index (index = pivot + 1)动态更新最终的主轴下标。从左到右将主轴后的所有元素依次与主轴元素比较，若小于主轴则将该数字与下标为index的数字交换，index右移一位，使得 index的前一位总是当前最后一个小于主轴的元素。遍历比较结束后，交换下标为pivot与index - 1的数字，并将当前主轴的下标index - 1返回。

稳定性：不稳定。

partition中在确定了主轴位置后，将一开始设置的主轴元素与最后一个小于主轴的元素x交换时，若中间有与x同值的元素，则稳定性被破坏。

例：7 2 4 4 8 9
7为主轴元素，partition过后交换7和第二个4，则两个4的位置关系发生变化。
非递归快排
前述快排以递归形式写出，递归地确定[left, right]区间的pivot位置并对新的左区间[left, pivot - 1]和右边区间[pivot + 1, right]区间执行同样的过程。若要求不以递归形式实现快排，容易想到利用 栈保存区间左右界，每次partition划分确定pivot后将得到的pivot左右两侧的区间的left，right界压入栈中。过程如下：

初始时区间左右界是0, arr.length -1 ，将他们压入栈（按right, left顺序入栈）。
以while询问当前栈是否空，不空则弹出栈顶的一对界（依次为left，right）。
若满足left < right，则对当前这对left，right界的区间执行一次partition方法，得到该区间的pivot。
若满足left < pivot，则将pivot左侧区间的左右界压入栈（按pivot - 1，left顺序入栈）。并列地，若满足right > pivot，则将pivot右侧区间的左右界压入栈（按right，pivot + 1顺序入栈）
while结束时排序完成，返回此时的arr。
非递归快排代码实现后续给出，与递归快排一样，在partition方法前加入如下两行实现主轴的随机选取；

int randomIndex = new Random().nextInt(right - left + 1) + left;
swap(arr, left, randomIndex);

在partition方法前加入如下一行实现主轴的三数取中选取。

median3(arr, left, right);

双轴快排
双轴快排是单轴快排的改进，初次学习双轴快排需要仔细深入地理解各处细节，因此本小节将详细介绍其实现细节，展示确定双轴位置既区间划分的过程。

前述快排每次递归确定当前区间的主轴，并利用该主轴将当前区间划分为左右两个部分。双轴快排则以 两个轴 (pivot1, pivot2)将当前区间划分为 三个子区间，双轴三区间的划分结果要满足如下。为方便叙述，将[left, pivot1)称作区间1，(pivot1, pivot2)称作区间2，(pivot2, right]称作区间3，其中pivot1，pivot2指的是最终位置，区间1，区间2，区间3均指划分后的最终区间。

arr[i] < arr[pivot1],  i ∈ [left, pivot1) 区间1
arr[pivot1] ≤ arr[i] ≤ arr[pivot2], i ∈ (pivot1, pivot2) 区间2
arr[i] > arr[pivot2], i ∈ (pivot2, right] 区间3

对三个子区间执行同样的过程，直到无法划分时排序完成。算法主要过程和说明如下，结合后续代码实现的注释可准确把握各处细节。

dualPivotQuickSort执行开始，首先以if(left < right)为条件，只对大小大于等于2的区间执行双轴快排。

以如下语句令左右两端元素中较小者居左，后续以left为初始pivot1(下标)，right为初始pivot2(下标)，保证pivot1为左右两端元素中的较小者。

在程序后续内容中，arr[left]为pivot1的值(左轴值)，arr[right]为pivot2的值(右轴值)。

if(arr[left] > arr[right]) {
    swap(arr, left, right);
}

设置index = left + 1，lower = left + 1，upper = right - 1。

index表示当前考察的元素下标。

lower是用于推进到pivot1最终位置的动态向右扩展的下标（扩展区间1），在程序的任意时刻总有[left, lower)的元素确定在区间1中。

upper是用于推进到pivot2最终位置的动态向左扩展的下标（扩展区间3），在程序的任意时刻总有(upper, right]的元素确定在区间3中。

当循环结束时lower--和upper++为最终的pivot1和pivot2的位置。

初始时lower == left + 1，表示区间1元素个数为1，
因为lower以左(不含lower)才是确定在区间1中的元素。
在遍历结束后以两个swap完成双轴归位时，
最后一个确定在区间1的元素会与arr[left]交换。
所以说我们一开始就知道left处的元素最终一定在区间1中，
因此初始时令lower == left + 1。
upper == right - 1的初始取值也是基于同样的原因。
如果现在还无法很好地理解这一点，先将整个过程看完后再回过头来多推敲几次。

从此处开始，代码行为是要遍历从left + 1到right - 1的所有元素，通过与arr[left] (左轴值)和arr[right] (右轴值)的比较，以及元素交换操作，将 每一个元素正确地置于区间1，区间2和区间3中，与此同时，以lower的动态右移和upper的动态左移，不断扩展这三个区间。 通过index++，从左到右依次遍历所有元素，当所有元素遍历完成，也就意味着所有元素都已归于其应属的区间。显然，这些操作应在一个 循环 之内，下面进入该循环。

首先，循环的边界条件是while(index <= upper)。虽然还未开始分析upper的动态变化，但已经知道upper以右(不含upper)的元素是确定在区间3中的，index向右推进的时候不能超过upper，因为下标为upper + 1的元素是已确定在区间3中的 (但下标为upper的元素尚未确定其归属)，所以是 <=。

以if(arr[index] < arr[left])考察arr[index]是否应在区间1，若满足则在区间1。这意味需要将该元素置于lower左侧，且区间1需向右扩展1位，通过如下两行，交换arr[index]和arr[lower]后lower++来完成。

swap(arr, index, lower); 
lower++;

类似地，以else if(arr[index] > arr[right])考察arr[index]是否应在区间3，若满足则在区间3。这意味着需要将该元素置于upper右侧，且区间3需向左扩展1位。与上一步(4.2)不同的是，不能直接执行如下两行，即交换arr[index]和arr[upper]后upper--。因为如果被交换的当前的arr[upper]也是应当位于区间3中的元素，交换后，继续考察下一个元素，且因为考察界满足index <= upper，将导致该元素无法再被考察，也就无法将其正确地放入区间3中。而上一步并不存在该问题（因为与arr[index]交换的arr[lower]一定是属于区间2的元素）。

swap(arr, index, upper);
upper--;

因此，在执行上述两行之前，应该实现一种操作，使得与arr[index]交换的arr[upper]不是区间3中的元素。于是可以先从当前arr[upper]往左考察是否有arr[upper] > arr[right]，若满足则表示arr[upper] 确定在区间3中，于是upper--扩展区间3，直到不满足时表示此时arr[upper]确定是不在区间3中的元素，于是才交换arr[index]和arr[upper]，然后upper--，如下。需要注意的是while中还有一个条件，即index < upper，因为区间3左扩不可使index == upper，否则之后的第二条upper--将导致upper为一个已经确定了区间归属的元素的位置（arr[index - 1]为已考察过元素）。

while(arr[upper] > arr[right] && index < upper) {
    upper--;
}
swap(arr, index, upper);
upper--;

如上，交换arr[index]和arr[upper]后，此时的arr[index]确定不在区间3中，但在区间1还是区间2中仍需明确，否则之后index++跳过该元素后将可能导致该元素归属错误。于是再对其执行一次与4.2相同的步骤。

if(arr[index] < arr[left]) {
    swap(arr, index, lower);
    lower++;
}

上述if和else if完成了对一个属于区间1和区间3元素考察和处理，不满足if且不满足else if的元素属于区间2，其已处于(lower, upper)之间，无需移动。
前述操作完成了对arr[index]的考察和处理（移动或不移动），于是index++，考察下一个元素。
当while(index <= upper)结束时，所有元素考察处理完毕，此时最后一个确定在区间1的元素下标是lower--，最后一个确定在区间3的元素下标是upper++。如下，通过交换将初始轴归于其正确的位置。最后对三个子区间分别递归地执行双轴快排。

lower--;
upper++;
swap(arr, left, lower);
swap(arr, upper, right);
dualPivotQuickSort(arr, left, lower - 1); // 区间1
dualPivotQuickSort(arr, lower + 1, upper - 1); // 区间2
dualPivotQuickSort(arr, upper + 1, right); // 区间3

下图展示了双轴快排对{29, 46, 21, 90, 14, 1, 68, 34, 55, 8}的双轴位置确定也即区间划分的过程。浅蓝色表示未排序，绿色表示左轴值，深蓝色表示右轴值，黄色表示区间1，灰色表示区间2，橙色表示区间3。


复杂度分析
时间复杂度：平均 / 最好为 O(nlogn)O(nlogn)，最坏为 O(n^2)O(n 2)。
单轴快排每次partition主轴均居中，则递归深度为 i 的partition有 2^i2 i  个， 这 2^i2 i  个partition需要比较的次数是 (除去 2^{i-1}2 i−1  个主轴元素的元素个数) n - 2^{i-1}n−2 i−1 。给出如下复杂度估计。

可知时间复杂度为 O(nlogn)O(nlogn)。

也可通过如下递推式导出。

T(n)=2 T(n / 2)+n

最坏情形

对于单轴快排，当输入为已排序数组，且采用首位为主轴的方式，第 i 次partition后主轴左右两部分总是left = null，right = n - i, 第i次partition需要比较n - i次，共有n次partition，总比较次数 O(n^2)O(n 
2
 )。类似于对已排序的数组做 选择排序。

左右两端取轴的双轴快排对于已排序数组，同样是 O(n^2)O(n 2 ) 的最坏情形。

空间复杂度：递归形式的快排，取决于递归深度，为 O(logn)O(logn)。非递归形式的快排，保存分区信息的栈深度与递归深度相同，空间复杂度也是 O(logn)O(logn)。

不同于归并排序中需要借助一个临时数组保存每次合并的结果，快速排序以原地交换元素的形式，避免了 O(n)O(n) 的数组开销。

代码
递归快排

// 三数取中快排
public int[] quickSortMedian3(int[] arr) {
    if (arr.length < 2) return arr;
    quickSortMedian3(arr, 0, arr.length - 1); // 后两个参数是下标值
    return arr;
}

private void quickSortMedian3(int[] arr, int left, int right) {
      if (left < right) { 
        // 执行median3将左，中，右三数中值放到left位置上
        median3(arr, left, right);
        int pivot = partition(arr, left, right);
        quickSortMedian3(arr, left, pivot - 1);
        quickSortMedian3(arr, pivot + 1, right);
    }
}


/**
 * 三数取中方法
 * 将下标left到下标right的分区中，将left/center/right
 * 三者中的大小居中者放到当前分区的起始位置
 */
private void median3(int[]arr, int left, int right) {
    int center = (left + right) / 2;
    // 第一个if，确保左和中这两个元素，大者居中
    if (arr[left] > arr[center]) {
        swap(arr, left, center);
    }
    // 第二个if，确保此时中和右这两个元素，大者居右
    // 前两个if，确保左中右这三个元素，大者居右
    if (arr[center] > arr[right]) {
        swap(arr, left, right);
    }
    // 第三个if，确保此时左和中这两个元素，大者居左
    // 三个if后，确保左中右这三个元素，中者居左
    if (arr[left] > arr[center]) return;
    else swap(arr, left, center);
}

// 随机主轴快排
public int[] quickSortRandom(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    quickSortRandom(arr, 0, arr.length - 1);
    return arr;
}

private void quickSortRandom(int[] arr, int left, int right) {
    if (left < right) {
        // 取区间内随机下标，注意Random().nextInt(int x)方法的使用（含0不含x）
        int randomIndex = new Random().nextInt(right - left + 1) + left;
        // 交换随机取得的下标元素与当前起始元素
        swap(arr, left, randomIndex);
        int pivot = partition(arr, left, right);
        quickSortRandom(arr, left, pivot - 1);
        quickSortRandom(arr, pivot + 1, right);
    }
}

// 朴素快排(首位为主轴)
public int[] quickSortSimple(int[] arr) {
    if (arr.length < 2) return arr;
    quickSortSimple(arr, 0, arr.length - 1); // 后两个参数是下标值
    return arr;
}

private void quickSortSimple(int[] arr, int left, int right) {
    // 若left == right，表示此时arr只有一个元素，即为基准情形，完成递归(准确说是完成递进)
    // (尾递归，“回归”过程中不做任何事情）
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSortSimple(arr, left, pivot - 1);
        quickSortSimple(arr, pivot + 1, right);
    }
}

//　partition方法
private int partition(int[] arr, int left, int right) {
    int pivot = left, index = pivot + 1;
    // 注意此时right是坐标，要执行到最后一个元素，所以是<=
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, index, i);
            index++;
        }
    }
    // 最后一个小于主轴元素的元素下标是index - 1
    swap(arr, pivot, index - 1);
    return index - 1;
}

非递归快排 (迭代快排)

public int[] quickSortStack(int[] arr) {
    // 用于保存区间左右边界的栈，按right到left的顺序将初始区间界入栈
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(arr.length - 1);
    stack.push(0);
    // 判断栈是否空，不空则弹出一对left，right界
    while(!stack.isEmpty()) {
        int left = stack.pop(), right = stack.pop();
        if(left < right) { // 执行partition的前提是left小于right
            // 对[left, right]区间执行partition方法，得到pivot
              // 加入后续两行实现随机轴快排
            // int randomIndex = new Random().nextInt(right - left + 1) + left;
            // swap(arr, left, randomIndex);
              // 加入下行实现三数取中快排
            median3(arr, left, right);
            int pivot = partition(arr, left, right);
            // 当前pivot的左区间存在则将该区间right，left界入栈
            if(pivot > left) {
                stack.push(pivot - 1);
                stack.push(left);
            }
            // 当前pivot的右区间存在则将该区间right，left界入栈
            if(right > pivot) {
                stack.push(right);
                stack.push(pivot + 1);
            }
        }
    }
    return arr;
}

双轴快排

public int[] dualPivotQuickSort(int[] arr) {
    if (arr.length < 2) return arr;
    dualPivotQuickSort(arr, 0, arr.length - 1); // 后两个参数是下标值
    return arr;
}
/*
 *     区间1               区间2                         区间3
 * +------------------------------------------------------------+
 * |  < pivot1  | pivot1 <= && <= pivot2  |    ?    | > pivot2  |
 * +------------------------------------------------------------+
 *              ^                         ^         ^
 *              |                         |         |
 *            lower                     index      upper
 */
private void dualPivotQuickSort(int[] arr, int left, int right) {
    if(left < right) { // 排序对象是right大于left的区间（即大小大于等于2的区间）
        // 令左右两端元素中较小者居左，以left为初始pivot1，right为初始pivot2
        // 即arr[left]为选定的左轴值，arr[right]为选定的右轴值
        if(arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        int index = left + 1; // 当前考察元素下标
        int lower = left + 1; // 用于推进到pivot1最终位置的动态下标，总有[left, lower)确定在区间1中
        int upper = right - 1; // 用于推进到pivot2最终位置的动态下标，总有(upper, right]确定在区间3中
        // [lower, index)确定在区间2中，[index, upper]为待考察区间。

        // upper以右（不含upper）的元素都是确定在区间3的元素，所以考察元素的右界是upper
        while(index <= upper) {
            // 若arr[index] < arr[left]，即arr[index]小于左轴值，则arr[index]位于区间1
            if (arr[index] < arr[left]) {
                // 交换arr[index]和arr[lower]，配合后一条lower++，保证arr[index]位于区间1
                swap(arr, index, lower); 
                // lower++，扩展区间1，lower位置向右一位靠近pivot1的最终位置
                lower++;
            }
            // 若arr[index] > arr[right]，即arr[index]大于右轴值，则arr[index]位于区间3
            else if(arr[index] > arr[right]) {
                // 先扩展区间3，使得如下while结束后upper以右（不含upper）的元素都位于区间3
                // 区间3左扩不可使index == upper，否则之后的第二条upper--将导致upper为一个已经确定了区间归属的元素的位置（即index - 1）
                while(arr[upper] > arr[right] && index < upper) {
                    upper--;
                }
                // 交换arr[index]和arr[upper]，配合后一条upper--，保证arr[index]位于区间3
                swap(arr, index, upper);
                upper--;
                // 上述交换后，index上的数字已经改变，只知道此时arr[index] ≤ arr[right]，arr[index]有可能在区间1或区间2，
                // 若arr[index] < arr[left]，即arr[index]小于左轴值，则arr[index]位于区间1
                if(arr[index] < arr[left]) {
                    // 交换arr[index]和arr[lower]，配合后一条lower++，保证arr[index]位于区间1
                    swap(arr, index, lower);
                    // lower++，扩展区间1，lower位置向右一位靠近pivot1的最终位置
                    lower++;
                }
            }
            index++; // 考察下一个数字
        }
        // while(index <= upper)结束后最后一个确定在区间1的元素的下标是lower--，
        // 最后一个确定在区间3的元素下标是upper++。
        lower--;
        upper++;
        // 双轴归位。此时的lower，upper即分别为最终pivot1(初始时为left)，最终pivot2(初始时为right)。
        swap(arr, left, lower);
        swap(arr, upper, right);
        // 对三个子区间分别执行双轴快排
        dualPivotQuickSort(arr, left, lower - 1); // 区间1
        dualPivotQuickSort(arr, lower + 1, upper - 1); // 区间2
        dualPivotQuickSort(arr, upper + 1, right); // 区间3
    }
}

堆排序
算法描述
将输入数组建立为一个 大顶堆，之后反复取出堆顶并对剩余元素重建大顶堆，将依次取出的堆顶逆序排列，即可将原数组从小到大排列完成排序。

一个直接的想法是在原数组之外新建一个数组保存每次取得的堆顶，这样会有 O(n)O(n) 的空间开销，可以用一种称作 **「原地堆排序」**的技巧避免此开销，具体做法如下。

首先将原待排序数组arr[]建立为一个大顶堆 (heapify堆化方法)。
交换堆顶和当前未排序部分中最末尾元素，则堆顶元素已排序（此时在数组最末尾）。
剩余元素中 只有当前堆顶（之前被交换的末尾元素）可能造成 堆失序，因此只需对堆顶调用一次调整堆序的下滤(siftDown)操作（操作范围为未排序部分），即可恢复未排序部分的堆序。
重复2，3直到所有元素已排序，返回arr[]。
上述通过交换堆顶与当前未排序部分末尾元素的做法，避免了额外的空间开销，即 原地堆排序，程序结束后返回的arr[]为已排序状态。

稳定性：不稳定。

交换可能会破坏稳定性。例：输入数组 {1, 2, 2}，变灰表示已排序。可以看到红2和绿2的相对顺序相比输入已改变。

堆化方法 (heapify)

将原输入数组看作一棵 完全二叉树(Complete Binary Tree)。根节点下标为0，于是根据完全二叉树的结构性质，任意一个节点(下标为 i )的左子节点下标为 2 * i + 12∗i+1，右子节点下标为 2 * i + 22∗i+2，父节点下标为 i / 2i/2。 堆化过程即使得整棵树满足堆序性质，也即任意一个节点大于等于其子节点（大顶堆）。堆化操作总结为一句话就是：对最后一个非叶子节点到根节点，依次执行下滤操作(siftDown)。

从最后非一个叶子开始下滤的原因是此节点之后的节点均为叶子节点，叶子节点无子节点，故其本身已满足堆序性质，也就无下滤的必要（也无法下滤）。每一次下滤使得该节点及其之后的节点都满足堆序性质，直到根节点。

※ 最后一个非叶子节点（也即最后一个元素的父节点）下标为 (n - 1) / 2(n−1)/2，n为数组长度。

如下动图是将输入数组{4, 6, 2, 1, 7, 9, 5, 8, 3} (1为最后一个非叶子结点) 堆化成大顶堆{9, 8, 5, 6, 7, 2, 4, 1, 3}的过程。
下滤方法(siftDown)
下滤(siftDown)是堆排序的核心方法，在堆排序中用于在程序开始时 创建大顶堆，以及在每次排序堆顶时用于 恢复未排序部分的堆序。
该方法来源于删除堆顶元素操作，先介绍下滤在删除堆顶元素操作中的处理过程。如下动图展示了删除大顶堆{9, 8, 5, 6, 7, 2, 4, 1, 3}堆顶元素9的过程（动图中出现的100表示堆顶，值为9）。
删除堆顶，堆中元素减1，将当前最后一个元素3暂时置为堆顶。
可以看到，此时影响堆序的只有该堆顶元素3，于是交换其与左右子节点中的较大者。
对元素3重复操作2，直到3再无子节点，堆序恢复。
恢复堆序的过程就是将影响堆序的元素不断向下层移动（并交换）的过程，因此形象地称之为下滤(siftDown)。
※ 注意，此处沿用JDK源码中下滤操作的方法名"siftDown"，sift为过滤之意，网上有的博客文章将其讹误成shift。

可以看到，对节点x的下滤操作的本质是恢复以x为根节点的树的堆序。因此在堆化操作中，只需要分别依次地对最后一个非叶子节点到根节点执行下滤操作，即可使整棵树满足堆序。在排序过程中，每次原地交换后（交换当前堆顶与当前未排序部分最后一个元素），只有新堆顶影响堆序，对其执行 一次 下滤操作（范围为未排序部分）即可使未排序部分重新满足堆序。
复杂度分析
时间复杂度：原地堆排序的时间复杂度为 O(nlogn)O(nlogn)。
建堆时间复杂度: O(n)O(n)，证明如下。

当前堆顶通过交换完成排序时，其下滤次数取决于当前树高，设当前未排序元素个数为i，其下滤次数最多为层高减1（根节点为第1层），即 logilogi。每排序一次堆顶，待排序部分元素个数减1，于是从一个大顶堆开始完成排序所需时间取决于 n - 1 次堆顶下滤(下滤范围分别为n, n -1, n-2,...,2)次数总和最大值。

代码

public int[] heapSort(int[] arr) {
    if (arr.length < 2) return arr;
    heapify(arr, arr.length - 1); // 构建大顶堆
    for (int i = arr.length - 1; i > 0; i--) { // i > 0即可，无需写成i >= 0，当n - 1个元素排序时，最后一个元素也已排序
        swap(arr, 0, i); // 交换堆顶和当前未排序部分最后一个元素
        // 此时除当前堆顶元素外都是保持堆序的，只需要对该堆顶调用一次下滤操作
        siftDown(arr, 0, i - 1); // i - 1是未排序部分最后一个元素下标，确保下滤不会超过此范围
    }
    return arr;
}

private void heapify(int[] arr, int endIdx) {
    for (int hole = (endIdx - 1) / 2; hole >= 0; hole--) { // (endIdx - 1) / 2伪最后一个非叶子节点下标
        siftDown(arr, hole, endIdx);
    }
}

private void siftDown(int[] arr, int hole, int endIdx) {
    int target = arr[hole]; // target是要下滤的节点
    int child = hole * 2 + 1;
    while(child <= endIdx) {
        // 满足第一个条件child < endIdx表示hole有右孩子，不满足则hole无右孩子，跳过
        // 第二个条件arr[child + 1] > arr[child]只在第一个条件成立前提下进行判断（因此不必担心arr[child + 1]越界），
        // 若满足，表示hole有右孩子且右孩子更大，令child为右孩子下标。
        // 因此此if过后使得child是hole的孩子中较大的那个
        if (child < endIdx && arr[child + 1] > arr[child]) {
            child++;
        }
        // 若child大于target，则child上移到当前hole，hole下滤到child位置 
        if (arr[child] > target) {
            arr[hole] = arr[child];
            hole = child;
            child = hole * 2 + 1; // 当然也可以写成child = child * 2 + 1
        } else break; // 若无需交换hole与child，说明hole已经满足堆序(无需/无法再下滤)，退出while
    }
    arr[hole] = target; // 将target填入hole中
}

计数排序
算法描述
计数排序是我们介绍的第一种 非比较排序，通常 适用于整数数组，是一种利用整数特点取得 线性复杂度 的非比较排序方法。假设待排序数组 arr 为正整数数组， 朴素 的计数排序过程如下：

创建一个计数数组countArr，其大小为arr中的最大值max再加1。
遍历arr，每读取一个arr[i]，直接令countArr[arr[i]]++。
从下标1开始遍历countArr，依次输出counter[i]个i，即为排序结果。
朴素做法有两个明显的缺陷，首先是 无法处理负数，其次是当元素个数较多，但很多相等元素使得元素分布 集中在较小范围 时，max+1大小的countArr中大部分空间是多余的。改进方法很简单，即创建大小为max - min + 1的countArr，max和min分别是arr中最大和最小元素。后续代码均会采用该改进。
如下动图展示了{4,6,2,1,7,9,5,8,3,1,1}的计数排序过程（不稳定版）。
稳定性：取决于是否采用稳定性优化版本。

采用则稳定，不采用则不稳定，稳定优化方法见后。

稳定性优化
经过上述改进的计数排序仍存在 稳定性缺陷，即通过计数来排序，当遍历到countArr[i]时，只是连续地输出countArr[i]次 i + min，稳定性得不到保证 （比如动图中，后放入的 1 会先输出）。要保证稳定，必须使 先记录的先输出。可以通过对countArr进行 变形 来满足稳定性，使得遍历到同一个数字，例如 k 时，能够将不同位置的 k 按他们在arr中出现的顺序放入到输出数组中。具体做法如下。

得到countArr后，遍历一次countArr，使得每一个countArr[i]的值都是从countArr[0]到countArr[i]中值不为0的项的值之和（前缀和）。例如对于待排序数组{5, 5, 4, 4, 1, 1}，得到大小为 5 - 1 + 1 = 5的countArr，具体为{2, 0, 0, 2, 2}，表示有两个1，0个2，0个3，2个4，2个5。按照前述方法将其变形为{2, 0, 0, 4, 6}，表示1的最大位置为第2位(下标为1)，4的最大位置为4(下标为3)，5的最大位置为6(下标为5)。
在输出排序结果时，新建一个大小等于arr的sortedArr数组，于是countArr[arr[i] - min] - 1即为arr[i]这个数应当放入sortedArr的位置(下标)，即sortedArr[countArr[arr[i] - min] - 1] = arr[i]，以倒序从arr.length遍历到0，每次向sortedArr填入一个数字后，令countArr[arr[i] - min]--。遍历结束后得到的sortedArr即为arr的稳定排序结果。(建议实际动手验证这个过程)

复杂度分析
时间复杂度：朴素版为 O(max)O(max)，max为原数组中最大值。改进版为 O(n + k)O(n+k)，n为元素个数，k 计数数组大小。当元素个数较少但最大最小值差值很大时，复杂度取决于 k。

空间复杂度：不考虑输入数组arr，朴素版的countArr的大小为k+1，故空间复杂度为 O(k)O(k)。稳定性优化版为 O(n + k)O(n+k)，n为sortedArr的大小，等于arr的大小。
代码
不稳定计数排序

public int[] countSortUnstable(int[] arr) {
    if (arr.length < 2) return arr;
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    int[] countArr = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - min]++;
    }
    int index = 0;
    for (int i = 0; i < countArr.length; i++) { // 遍历countArr
        for (int j = 0; j < countArr[i]; j++) { // countArr[i]可能有多个相同数字
            arr[index] = i + min; // 复用了原输入数组arr
            index++;
        }
    }
    return arr; 
}

稳定计数排序

public int[] countSort(int[] arr) {
    if (arr.length < 2) return arr;
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    int[] countArr = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - min]++;
    }
    // countArr变形
    int sum = 0;
    for (int i = 0; i < countArr.length; i++) {
        // 一处小改进，当输入数组取值比较稀疏时，该判断能避免大部分无意义的赋值操作
        if (countArr[i] != 0) {
            sum += countArr[i];
            countArr[i] = sum;
        }
    }
    // 根据sortedArr, nums, countArr三者关系完成sortedArr的输出
    int[] sortedArr = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        sortedArr[countArr[arr[i] - min] - 1] = arr[i];
        countArr[arr[i] - min]--;
    }
    return sortedArr;

基数排序
算法描述
非比较排序，「基」指的是数的位，例如十进制数123，共有百十个位，共3个位。基数排序 按数字的位进行循环，每一***作都是对当前位（基数）的计数排序，使得输出到arr后所有数字在截止到当前位上（即去掉未考察的位后）是排序状态，考察完最大位后完成排序。具体过程如下：

遍历待排序数组arr，找到最大值，计算其位数，例如arr中最大数为123，则maxDigitLen = 3。
数组的数字为n进制，就创建大小为n的计数数组countArr，也可以称为n个桶。
开始「位」的for循环，循环次数等于maxDigitLen，每一轮对 当前所有数字的当前位 执行一次 计数排序。
每次计数排序结束后将结果写回arr。
for循环结束后返回排序结果arr。
如下动图演示{6674, 1560, 5884, 2977, 2922, 4127, 5390, 7870, 1193, 7163}的基数排序过程。

也可以不使用计数排序，而是创建一个二维数组（可看作19个桶）保存每次遍历的中间结果，此写法耗费的空间较大（每个桶的大小都要等于arr大小+1，空间复杂度为O(19n)），是稳定排序，不详细说明，可以参考后续给出的代码实现。

以计数排序为基础的基数排序，每一位循环时都对所有数做该位的计数排序。

不以计数排序为基础的基数排序，每一位循环时都将所有数按顺序放入相应的桶中。

稳定性：取决于计数排序的稳定性。

两个同值的元素位数相同，按位循环，若采用稳定版本的计数排序则稳定，否则不稳定。

优化
处理负数优化：若存在负数，可以先找到最小值(负数)，对arr中的每个数，都加上此最小值的绝对值，排序完成后再减回去。但加法可能使得 数字越界，一种更好的办法是计数排序时 将countArr的大小扩展为 19，以[0, 19]对应可能出现的[-9, 9]。因此在每轮求当前基数时，要在原基数结果上 +9 以对应countArr的下标。

后续代码给出利用计数排序的应用此优化的版本。
复杂度分析
时间复杂度：d为绝对值最大的元素位数，总共进行d轮计数排序，O(n + k)O(n+k) 是计数排序的复杂度，其中k是位的取值范围，如果是非负数，则 k = 10 (0~9)，如果包含负数，则 k = 19 (-9~9)。所以总的时间复杂度为 O(d(n + k))O(d(n+k))。

空间复杂度：

利用计数排序的基数排序，空间复杂度与计数排序相同，为 O(n + k)O(n+k)。

不利用计数排序的计数排序，将以19个（应用处理负数优化）「桶」的二维数组作为排序过程中的存储空间，故空间复杂度为 O(19n)O(19n)，当n显著大于19时也可认为其空间复杂度为 O(n)O(n)。
代码
以计数排序为基础

public int[] radixSort(int[] arr) {
    if (arr.length < 2) return arr;
    int max = Math.abs(arr[0]); // 找到arr中绝对值最大者
    for (int i = 1; i < arr.length; i++) {
        max = Math.max(max, Math.abs(arr[i]));
    }
    int maxDigitLen = 0, base = 10; // 最大位数 & 基（几进制就是几）
    while (max != 0) {
        maxDigitLen++;
        max /= base;
    }
    // 在接下来的for中，每一轮都对当前位(基数)执行一次计数排序
    int[] sortedArr = new int[arr.length];
    for (int i = 0; i < maxDigitLen; i++) {
        int[] countArr = new int[19]; // 处理负数优化
        // 根据每一个数字当前位的数字，累计相应位置的计数
        for (int j = 0; j < arr.length; j++) {
            // 此步处理要注意，当base大于10时，例如base=100时，1234%100=34
            // 还需要再除以(base/10)，得到的3，然后再+9（考虑负数）才是本次的bucketIdx
            int bucketIdx = (arr[j] % base) / (base / 10) + 9;
            countArr[bucketIdx]++;
        }
        // countArr变形，得到每个下标所代表的arr中的数的当前位在arr中的最大位置（从1开始）
        for (int j = 1; j < countArr.length; j++) {
            countArr[j] += countArr[j - 1];
        }
        // 逆序输出保持稳定性
        for (int j = arr.length - 1; j >= 0; j--) {
            int thisBase = (arr[j] % base) / (base / 10) + 9;
            // countArr[thisBase]得到的从1开始计算的位置，转成下标要-1
            sortedArr[countArr[thisBase] - 1] = arr[j]; 
            countArr[thisBase]--;
        }
        // 完成当前位的计数排序后将排序结果拷贝回原数组
        arr = Arrays.copyOf(sortedArr, sortedArr.length);
        // base进一位，准备下一轮对下一位的计数排序
        base *= 10;
    }
    return arr;
}

不以计数排序为基础

public int[] radixSort(int[] arr) {
    if (arr.length < 2) return arr;
    // 找到arr中绝对值最大者
    int max = Math.abs(arr[0]);
    for (int i = 1; i < arr.length; i++) {
        max = Math.max(max, Math.abs(arr[i]));
    }
    int maxDigitLen = 0, base = 10; // 最大位数 & 基
    while (max != 0) {
        maxDigitLen++;
        max /= base;
    }
    // arr.length + 1的作用是令每个桶的第0位保存该桶的元素个数。
    int[][] buckets = new int[19][arr.length + 1]; // 处理负数优化
    // 在每一位上将数组中所有具有该位的数字装入对应桶中
    for (int i = 0; i < maxDigitLen; i++) {
        for (int j = 0; j < arr.length; j++) {
            // 此步处理要注意，当base大于10时，例如base=100时，1234%100=34
            // 还需要再除以(base/10)，得到的3才是本次的bucketIndex
            int bucketIdx = (arr[j] % base) / (base / 10) + 9; // +9使其可以处理负数
            int currentBucketQuantity = buckets[bucketIdx][0];
            buckets[bucketIdx][currentBucketQuantity + 1] = arr[j];
            buckets[bucketIdx][0]++;
        }
        // 将当前所有桶的数按桶序，桶内按低到高输出为本轮排序结果
        int arrIdx = 0;
        for (int j = 0; j < buckets.length; j++) {
            for (int k = 1; k <= buckets[j][0]; k++) {
                arr[arrIdx++] = buckets[j][k];
            }
        }
        // 每一轮过后将桶计数归零
        for (int[] bucket : buckets) bucket[0] = 0;
        base *= 10; // 调整base
    }
    return arr;
}

桶排序
算法描述
桶排序将原数组划分到称为 「桶」 的多个区间中，然后对每个桶单独进行排序，之后再按桶序和桶内序输出结果。适合于分布较均匀的数据，具体做法如下。

根据数据规模按照 一定的方法 将待排序数组arr划分为多个区间，每个区间称作一个桶。
每个桶可以是数组，也可以是泛型容器，用于保存arr中落在该桶范围内的数。
对每一个桶都单独排序，需要 以适当的排序 方法支持，例如插入排序，快速排序等。
所有桶完成排序后，按桶序，桶内序依次输出所有元素，得到arr的排序结果。
稳定性：取决于桶内排序方法的稳定性。

复杂度分析
时间复杂度：找最大最小值和分配桶均耗费 O(n)O(n)，之后的复杂度取决于每个桶内的排序算法复杂度之和。假设有k个桶，且数据分布均匀，若采用 O(n^2)O(n 
2
 ) 的排序算法，那么总排序时间复杂度为 O(n^2/k)O(n 
2
 /k)，若采用 O(nlogn)O(nlogn) 的排序算法，总排序时间复杂度为 O(k(n/k)log(n/k))O(k(n/k)log(n/k))，即 O(nlog(n/k))O(nlog(n/k))。若桶内排序采用 O(nlogn)O(nlogn) 算法，且k的大小适当，例如 k = n/pk=n/p，p是一个较小的数例如2，3等。那么整体的时间复杂度约为 O(n)O(n)。虽然形式上为线性复杂度，但其n的系数较大，未必优于O(nlogn)O(nlogn)的排序算法。

当所有元素都被分到同一个桶中，达到最大时间复杂度，为 O(n^2)O(n 
2
 ) 或 O(nlogn)O(nlogn)（取决于桶内排序采用的排序方法）。

空间复杂度：取决于桶的数据结构，若采用静态数组，由于每个桶都需要保证有n个位置，则空间复杂度为 O(kn)O(kn)，若采用泛型容器，则为 O(n)O(n)。

代码

public int[] bucketSort(int[] arr) {
    int min = arr[0], max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    // 用泛型List存储所有桶，每个桶是一个ArrayList<Integer>，并初始化所有桶。
    // arr.length/3表示设置数组大小三分之一数量的桶
    List<ArrayList<Integer>> buckets = new ArrayList<>(arr.length / 3);
    for (int i = 0; i < arr.length; i++) {
        buckets.add(new ArrayList<>());
    }
    // 遍历arr，根据元素值将所有元素装入对应值区间的桶中
    for (int i = 0; i < arr.length; i++) {
        // (arr[i] - min)/D为arr[i]元素应该装入的桶的下标，间隔D = (max-min)/(arr.length-1)
        // 虽可写成(arr[i] - min)*(arr.length-1)/(max-min)的形式，但当输入数组取值范围较大且元素较多时
        // (arr[i] - min)*(arr.length-1)可能会超过int上限，因此先做除法求出double类型的D
        // 再做一次除法求出bucketIndex，可以避免计算精度不够高带来的问题
        double interval = (double)(max - min) / (double)(arr.length - 1);
        int bucketIdx = (int) ((arr[i] - min) / interval);
        buckets.get(bucketIdx).add(arr[i]);
    }
    // 桶内排序(调用库函数，从小到大)
    for (int i = 0; i < buckets.size(); i++) {
        Collections.sort(buckets.get(i));
    }
    int index = 0;
    for (ArrayList<Integer> bucket : buckets) {
        for (int sortedItem : bucket) {
            arr[index] = sortedItem; // 复用输入数组arr
            index++;
        }
    }
    return arr;
}

决策树
利用 决策树 来理解基于比较的排序算法的复杂度的理论下界为 O(nlogn)O(nlogn)。本节内容学习自Weiss的数据结构与算法分析：Java语言描述 。

n个不同元素组成的序列，有 n!n! 种可能的排列。考虑这样一棵决策树，根处存放着所有 n!n! 种可能的排序，比较其中两个元素a和b，只有两种可能 a > ba>b 或者 a < ba<b（不考虑等于）。a 和 b 的大小关系确定后，都将去除根处 n!n! 种排列中的一半。将 a > ba>b 确定后的剩下的一半可能作为根的左子节点，a < ba<b 确定后剩下的另一半可能作为根的右子节点，每次确定某两个元素的大小后，都会剩下一半可能，作为左右子节点加入到决策树中，因此该决策树是一棵叶子节点总数为 n!n! 的二叉树，决策步数为到达排序状态的序列的叶子节点的深度。

对于深度为 d (根节点在0深度处)的二叉树，其叶子结点数量至多为 2^d2 
d
 ，当二叉树为 完美二叉树 (perfect binary tree) 时达到最大值。于是对应地，具有n个叶子节点的二叉树，深度至少为 ⌈logn⌉⌈logn⌉ ，当二叉树为 完全二叉树(complete binary tree) 时深度最浅。 于是具有 n!n! 个叶子节点的二叉树的深度至少为 ⌈log(n!))⌉⌈log(n!))⌉，这个深度就是通过比较得到排序结果的最少比较次数。根据Stirling公式 得到如下结果，因此，通过比较来排序的算法的时间复杂度 下界 为 O(nlogn)O(nlogn)。

JDK中的排序
（TODO）



应用
与元素大小相关的问题基本上都可以用排序来解决，例如从数组中取出前k个大(小)，第k个大(小)数等。也有通过适当的排序过程获取某些信息的问题，例如消除逆序数。（TODO）
🐮🐮🐮
牛啊兄弟，你竟然真的看到这里了。






























#面试##内推##春招##实习##笔试题目##面经##Java##MySQL#