排序算法总结

排序算法

排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 堆排序
- 计数排序
- 基数排序
- 桶排序

排序算法

排序算法分为比较排序和非比较排序。

比较排序：冒泡排序，选择排序，插入排序，希尔排序，归并排序，快速排序，堆排序，

非比较排序：计数排序，基数排序，桶排序。

排序算法	平均时间	最好时间	最坏时间	空间	稳定性
冒泡	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	稳定
选择	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	不稳定
插入	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	稳定
希尔	O ( n log ⁡ n ) ∼ O ( n 2 ) O(n log n) sim O(n^2) O(nlogn)∼O(n2)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)	不稳定
归并	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n ) O(n) O(n)	稳定
快速	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n 2 ) O(n^2) O(n2)	O ( n log ⁡ n ) O(n log n) O(nlogn)	不稳定
堆	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( 1 ) O(1) O(1)	不稳定
计数	O ( n + k ) O(n + k) O(n+k)	O ( n + k ) O(n + k) O(n+k)	O ( n + k ) O(n + k) O(n+k)	O ( n + k ) O(n + k) O(n+k)	稳定
基数	O ( d ( n + k ) ) O(d(n + k)) O(d(n+k))	O ( d ( n + k ) ) O(d(n + k)) O(d(n+k))	O ( d ( n + k ) ) O(d(n + k)) O(d(n+k))	O ( n + k ) O(n + k) O(n+k)	稳定
桶	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n ) O(n) O(n)	稳定

交换元素的三种方式

// 方法一: 利用临时数tmp
private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 方法二: 利用加减运算
private void swapCal(int[] arr, int i, int j) {
    if(i == j) 
    // 若无法保证swapCal被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
        return;
    
    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) {
    if(i == j)
    // 若无法保证swapXOR被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
        return;
    
    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[n - 2] 和 arr[n - 1]。

比较将使得最大的数字冒泡到最后，此时可以说一个数字已经被排序。每一轮的比较将使得当前未排序数字中的最大者被排序，同时未排序数字总数减 1。第 n - 1 轮结束后排序完成。

也可以对执行的轮次数进行优化：当某一轮比较均未发生交换，说明排序已完成，可设置一个布尔值记录一轮排序是否有发生交换，若无则提前退出循环结束程序。

稳定性：稳定的排序算法。

复杂度

时间复杂度： O ( n 2 ) O(n^2) O(n2)，当数组有序的情况下，时间复杂度为 O(n)。

空间复杂度：O(1)。

public int[] bubbleSort(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    // n-1轮次执行，当前n-1个元素排好后，最后一个元素无需执行，故i
        // 本轮执行是否有交换的boolean型标志，若无则false，若有则true
        boolean swapped = false;
        // 每轮循环，通过依次向右比较两个数(j-1和j)，将本轮循环中最大的数放到最右
        for (int j = 1; j < n - 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) {
    int n = arr.length;
    if (arr.length < 2)
        return arr;
    boolean swapped = true;
    // lastSwappedIdx表示前一轮交换的最终位置，即下标为lastSwappedIdx是未排序部分中的最后一个数的下标，也即表示[lastSwappedIdx+1, n)范围内的元素已排序完成
    int lastSwappedIdx = n - 1;
    // swqppedIdx记录当前轮交换的idx，每轮结束后表示当前轮交换的最终位置，传给lastSwappedIdx
    int swappedIdx = -1;
    while (swapped) {   // 当swapped = false时，表示排序完成
        // 本轮执行是否有交换的标志，若无则true，若有则false
        swapped = false;
        // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右
        // 由于是i与i+1处的元素进行比较，而lastSwappedIdx+1开始已经排序完成
        // 因此循环的界是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 轮结束后排序完成。

稳定性：不稳定的排序算法。

复杂度

时间复杂度： O ( n 2 ) O(n^2) O(n2)。冒泡排序和选择排序的比较次数均为 O ( n 2 ) O(n^2) O(n2)，但选择排序的交换次数是 O(n)，而冒泡排序的平均交换次数仍然是二次的。

空间复杂度：O(1)。

public int[] selectSort(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    // n-1 轮次执行,当前 n-1 个元素排好后，最后一个元素无需执行，故 i < n-1
    int minIdx;
    for (int i = 0; i < n - 1; i++) {
        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[] selectSortDouble(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length;
    // 每轮确定两个数字，因此界也会动态变化
    for (int i = 0; i < n - 1 - i; i++) {
        int minIdx = i, maxIdx = i;
        // 找到本轮执行中最小和最大的元素
        for (int j = i + 1; j < n - 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 != n - 1 - i) swap(arr, n - 1 - i, maxIdx);
    }
    return arr;
}

插入排序

输入数组已排序时最好

对于待排序数组，从第 2 个元素开始（下标从 1 开始，称作插入对象元素），比较它与之前的元素（称作比较对象元素），当插入对象元素小于比较对象元素时，继续往前比较，直到不小于 (≥) 比较对象，此时将插入对象元素插入到该次比较对象元素之后。重复这个插入过程直到最后一个元素作为插入对象元素完成插入操作。

稳定性：不稳定的排序算法。

复杂度

时间复杂度： O ( n 2 ) O(n^2) O(n2)，如果给定的数组有序，则只需遍历一次，发现每个元素都不需要移动，因此最好情况下为 O(n)。

空间复杂度：O(1)。

// 直接插入排序
public int[] insertSort(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
	// n-1 轮次执行，从 i=1 开始
    for (int i = 1; i < n; i++) {
        int target = arr[i];
        for (int j = i - 1; j >= 0; j--) {
            if(target < arr[j])
                // 表示 target 应该插入到下标 j 或更前面，所以将 j 的值覆盖到 j+1
                // 原 target 所在位置 i 的值被 i-1 的值覆盖
                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) {
    int n = arr.length;
    if (n < 2)
        return arr;
    // n-1 轮次执行
    for (int i = 1; i < n; 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)
        // low 处的元素就是有序序列中第一个大于target的元素的位置
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        // 循环将low开始到i-1的元素，都移动到后一位，但需要逆序
        for (int j = i; j > low; j--) {
            arr[j] = arr[j - 1];
        }
        arr[low] = target;
    }
    return arr;
}
// 折半插入总的查找(比较)次数虽为 O(nlogn)，但平均移动 (每轮移动一半的数字) 次数仍是 O(n^2)。

希尔排序

希尔排序是简单插入排序的改进，基于以下事实：

简单插入排序对排序程度较高的序列有较高的效率。假设初始序列已完全排序，则每一轮均只需比较一次，将得到 O(n) 的线性复杂度，冒泡排序和选择排序做不到这一点，均仍需 O ( n 2 ) O(n^2) O(n2) 次比较（冒泡排序在应用提前结束优化后可以做到 O(n)）。
简单插入排序每次比较最多移动一个数字，效率较低。

对原待排序列中相隔 gap 的数字执行简单插入排序，然后缩小 gap，对新的 gap 间隔的数字再次执行简单插入排序。以一种规则减少 gap 的大小，当 gap 为 1 时即简单插入排序，因此希尔排序也称作增量递减排序。

稳定性：不稳定的排序算法。

希尔排序与简单插入排序的不同在于，简单插入排序寻找插入位置时的间隙为 1，希尔排序的间隙为 gap，且要将 gap 递减到 1。

复杂度

时间复杂度由不同增量而不同：

Shell 增量：增量为 n / 2 k n / 2^k n/2k，k = 1,2,…。最坏时间复杂度 O ( n 2 ) O(n^2) O(n2)。如果给定的数组有序，则只需遍历一次，发现每个元素都不需要移动，因此最好情况下为 O ( n log ⁡ n ) O(n log n) O(nlogn)。
Hibbard 增量：{1, 3, 7, 15, …}，增量为 2 k − 1 2^k-1 2k−1，k = 1,2,…。最坏时间复杂度 O ( n 3 / 2 ) O(n^{3/2}) O(n3/2)。
Knuth 增量：{1, 4, 13, 40, …}，增量为 3 k − 1 3^k-1 3k−1，k = 1,2,…。最坏时间复杂度 O ( n 3 / 2 ) O(n^{3/2}) O(n3/2)。
Sedgewick 增量：{1, 8, 23, 77, 281, …}，增量为 4 k + 3 ∗ 2 k − 1 + 1 4^k+3∗2^{k−1}+1 4k+3∗2k−1+1，k = 1,2,…。最坏时间复杂度 O ( n 4 / 3 ) O(n^{4/3}) O(n4/3)。

空间复杂度：O(1)。

希尔排序是较早出现的突破二次复杂度的排序算法。

逆序数

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

冒泡排序和简单插入排序，算法的每一次交换，都只交换相邻元素（简单插入排序中元素每次右移也看作交换），因此每次交换只能减少一个逆序。冒泡排序和简单插入排序的元素平均交换次数均为 O ( n 2 ) O(n^2) O(n2)，也即逆序数 (或逆序数减少次数) 为 O ( n 2 ) O(n^2) O(n2)。如果能跨越多个数字进行交换，则可能一次减少多个逆序。

在选择排序中，每轮选到最小元素后的交换即是跨越多个元素的，交换次数 (减少逆序数的操作) 为 O(n)，要少于冒泡和简单插入排序，只是因为比较次数仍是 O ( n 2 ) O(n^2) O(n2)，所以整体复杂度为 O ( n 2 ) O(n^2) O(n2)。

分析跨越多个元素的交换如何减少逆序数，假设 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] 的逆序消除，使得逆序至少减少一次，并有机会减少大于一次的逆序，因此能够以比 n 2 n^2 n2 低阶的次数消除所有逆序。实际上归并排序，快速排序，堆排序均实现了长距离交换元素，使得复杂度优于 O ( n 2 ) O(n^2) O(n2)。

// 希尔排序：采用Shell增量 n / 2^k
public int[] shellSortShell(int[] arr) {
    int n = arr.length;
    if (n < 2)
        return arr;
    // gap 初始为 n/2，缩小 gap 直到 1
    // shell 增量的值从 n/2 开始，循环除以 2 直到为 1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 步长增量是 gap，当前增量下需要对 gap 组序列进行简单插入排序
        // 也即对从 start 开始，间距为 gap 的子序列进行简单插入排序
        for(int start = 0; start < gap; start++) {
            // 此 for 及下一个 for 对当前增量序列执行简单插入排序
            // i 从开始位置起，距离 gap 的位置开始
            for (int i = start + gap; i < n; i += gap) {
                int target = arr[i];   // 需要插入的元素
                // j 从有序序列的最后一个元素开始，当 target 小于这个元素，则将这个元素向后移
                for (int j = i - gap; j >= 0; j -= gap) { 
                     if (target < arr[j]) {
                         arr[j + gap] = arr[j];
                     } else 
                         break; 
                }
                // 此时 target >= arr[j]，j 是需要插入的位置
                if (j != i)   // 需要插入的位置 j 不是开始位置，也即需要将 target 插到有序的位置中间
                    arr[j] = target;
            }
        }
    }
    return arr;
}



// 希尔排序：采用 Hibbard 增量 {1, 3, 7, 15,...}
public int[] shellSortHibbard(int[] arr) {
    int n = arr.length;
    if (n < 2)
        return arr;
    int gap = 1; 
    while (gap < n / 2)
        gap = gap * 2 + 1;   // 初始化gap (Hibbard增量序列)，值为
    for (; gap > 0; gap /= 2) {   // 缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i];
                for (int j = i - gap; j >= 0; j -= gap) { 
                     if (target < arr[j]) {
                         arr[j + gap] = arr[j];
                     } else 
                         break; 
                }                 
                if (j != i) 
                    arr[j] = target;
            }
        }
    }
    return arr;
}



// 希尔排序： 采用 Knuth 增量 {1, 4, 13, 40,...}
public int[] shellSortKnuth(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    int gap = 1; 
    while (gap < n / 3) 
        gap = gap * 3 + 1; // 初始化gap (Knuth增量序列)
    for (; gap > 0; gap /= 3) { // 缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i];
                for (int j = i - gap; j >= 0; j -= gap) { 
                     if (target < arr[j]) {
                         arr[j + gap] = arr[j];
                     } else 
                         break; 
                }                 
                if (j != i) 
                    arr[j] = target;
            }
        }
    }
    return arr;
}

归并排序

归并排序是分治思想的应用，即将原待排数组递归或迭代地分为左右两半，直到数组长度为 1，然后对左右数组进行合并 (merge)，在合并中完成排序。合并过程采用非原地合并方法，即依次比较两部分已排序数组，将比较结果依次写入新空间中。合并过程也可以原地 (in-place) 合并，是归并排序的改进，使得空间复杂度达到常数级 (自底向上时，O(1))。

可以通过自顶向下 (top-down) 或自底向上 (bottom-up) 的方式实现归并排序。

自顶向下 (top-down)：从输入数组出发，不断二分该数组，直到数组长度为 1，再执行合并。适合用递归实现。
自底向上 (bottom-up)：从输入数组的单个元素出发，一一合并，二二合并，四四合并直到数组有序。适合用迭代实现。

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

应用「手摇算法」对两个排序序列的「原地归并」过程如下：

记左数组第一个数下标为 i，记右数组第一个数下标为 j。

找到左数组中第一个大于右数组第一个数字的数，记其下标为 i。即 nums[i] 是左数组中大于右数组首个元素的第一个元素。

以 index 暂存右数组第一个元素的下标 index = j。

找到右数组中第一个大于等于 arr[i] 的数，记其下标为 j。即 nums[j] 是右数组中大于左数组第一个大于右数组首个元素的第一个元素。此时必有 [i, index - 1] 下标范围的序列大于 [index, j - 1] 下标范围的序列。（如果找「大于」而不是「大于等于」，对于数字数组排序，结果正确，但将破坏稳定性。如果是大于，则等于 arr[i] 的数会被包含在 [index, j - 1] 内，此时在对两个区间的元素执行第 5 步时，三次翻转会将后半部分区间的相对元素移到前半部分）

通过三次翻转交换 [i, index - 1] 和 [index, j - 1] 序列 (指下标范围)，即依次翻转 [i, index - 1]（递增序列变为递减），翻转 [index, j - 1]（递增序列变为递减），翻转 [i, j - 1]（两个递减序列分别变为递增，且第三次翻转会将前后序列反转，且内部也会重新变为递增）。

重复上述过程直到不满足 (i < j && j <= rightEnd)。

稳定性：稳定的排序算法。合并时的此判断中的等号 if(left[l_next] <= right[r_next])，保证了出现相等元素时，居左的元素总会被放在左侧，稳定性不受影响。

复杂度

归并排序	平均时间	最好时间	最坏时间	空间
自顶向下非原地	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n ) O(n) O(n)
自顶向下原地	O ( n 2 ) O(n^2) O(n2)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n 2 ) O(n^2) O(n2)	O ( log ⁡ n ) O(log n) O(logn)
自底向上非原地	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n ) O(n) O(n)
自底向上原地	O ( n 2 ) O(n^2) O(n2)	O ( n log ⁡ n ) O(n log n) O(nlogn)	O ( n 2 ) O(n^2) O(n2)	O ( 1 ) O(1) O(1)

自顶向下非原地

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

空间复杂度为 O(n)。递归深度为 O ( log ⁡ n ) O(log n) O(logn)，但辅助数组的大小为 O(n)。

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

private void mergeSort(int[] arr, int[] tmpArr, int left, int right) {
    if(left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, tmpArr, left, mid);   // 递归排序左半部分
        mergeSort(arr, tmpArr, mid + 1, right);   // 递归排序右半部分
        merge(arr, tmpArr, left, mid, right);   // 将排好序的左右部分
    }
}

// 非原地合并方法
private void merge(int[] arr, int[] tmpArr, int leftPos, int leftEnd, int rightEnd) {
    int rightPos = leftEnd + 1;   // 右半部分的开始下标
    int startIdx = leftPos;   // 当前两个序列开始的下标，用于将 tmpArr 数组中的部分元素赋值回原数组
    int tmpPos = leftPos;   // tmpArr 中的开始下标
    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];
    }
}

自顶向下原地

利用数组 + 手摇算法实现原地归并，算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)（因为要进行三次翻转，翻转次数相当于对数组中的全部元素进行两次翻转，通过链表实现手摇算法的时间复杂度才是 O ( n log ⁡ n ) O(n log n) O(nlogn)）。

空间复杂度为 O ( log ⁡ n ) O(log n) O(logn)，其中手摇算法的空间复杂度为 O(1)。递归深度为 log ⁡ n log n logn。

最好的情形是输入数组已经排序，则只需递归比较，无需手摇，此时时间复杂度为 O ( n log ⁡ n ) O(n log n) O(nlogn)，是 log ⁡ n log n logn 递归并且每层递归进行 n 次判断的复杂度。

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

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

// 原地归并（手摇算法）
private void merge(int[] arr, int leftPos, int leftEnd, int rightEnd) {
    int i = leftPos, j = leftEnd + 1;   // #1 leftPos 和 rightPos 分别表示左右两数组的开始位置
    while(i < j && j <= rightEnd) {
        while(i < j && arr[i] <= arr[j])
            i++;   // #2 找到首个大于右数组未排序的部分的首个元素，则左数组此元素之后的所有元素都大于右数组未排序部分的首个元素
        int index = j; // #3 index 标记右数组未排序部分的首个元素
        while(j <= rightEnd && arr[j] < arr[i])
            // 找到的 j 是右数组未排序部分首个大于等于 nums[i] 的下标，即 [index, j-1] 的元素都小于 nums[i]
            j++; // #4 注意是 arr[j] < arr[i]，即找到j使得arr[j] 为第一个大于等于 arr[i]值
        exchange(arr, i, index - 1, j - 1); // #5 对 [i, j-1] 的元素进行重排，其中 [i, index-1] 的全部元素都大于 [index, j-1]。
    }
}

// 三次翻转实现交换
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--;
    }
}

private void swap(int[] arr, int start, int end) {
    arr[start] ^= arr[end];
    arr[end] ^= arr[start];
    arr[start] ^= arr[end];
}

自底向上非原地

public int[] mergeSortBU(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    int[] tmpArr = new int[n];
    // 间隔，不能写成gap < n / 2 + 1，此种写法只适用于元素个数为 2 的 n 次幂时
    for(int gap = 1; gap < n; gap *= 2) {
        // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...)
        // 即在空间充足的情况下，左右数组的长度分别是 gap
        // 左数组的范围是 [left, left + gap - 1]，右数组的范围是 [left + gap, left + 2*gap - 1 | n-1]
        // 当最后两组的右数组为空时，不需要合并，此时最后一组的 left = n-gap
        for(int left = 0; left < n - 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, n - 1));
        }
    }
    return arr;
}

// 非原地合并方法
private void merge(int[] arr, int[] tmpArr, int leftPos, int leftEnd, int rightEnd) {
    int rightPos = leftEnd + 1;   // 右半部分的开始下标
    int startIdx = leftPos;   // 当前两个序列开始的下标，用于将 tmpArr 数组中的部分元素赋值回原数组
    int tmpPos = leftPos;   // tmpArr 中的开始下标
    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[] mergeSortBUInPlace(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    // 间隔，注意不能写成gap < arr.length / 2 + 1，此种写法只适用于元素个数为2的n次幂时
    for(int gap = 1; gap < n; gap *= 2) {
        // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...)
        for(int left = 0; left < n - 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;
}

// 原地归并（手摇算法）
private void merge(int[] arr, int leftPos, int leftEnd, int rightEnd) {
    int i = leftPos, j = leftEnd + 1;   // #1 leftPos 和 rightPos 分别表示左右两数组的开始位置
    while(i < j && j <= rightEnd) {
        while(i < j && arr[i] <= arr[j])
            i++;   // #2 找到首个大于右数组未排序的部分的首个元素，则左数组此元素之后的所有元素都大于右数组未排序部分的首个元素
        int index = j; // #3 index 标记右数组未排序部分的首个元素
        while(j <= rightEnd && arr[j] < arr[i])
            // 找到的 j 是右数组未排序部分首个大于等于 nums[i] 的下标，即 [index, j-1] 的元素都小于 nums[i]
            j++; // #4 注意是 arr[j] < arr[i]，即找到j使得arr[j] 为第一个大于等于 arr[i]值
        exchange(arr, i, index - 1, j - 1); // #5 对 [i, j-1] 的元素进行重排，其中 [i, index-1] 的全部元素都大于 [index, j-1]。
    }
}

// 三次翻转实现交换
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--;
    }
}

private void swap(int[] arr, int start, int end) {
    arr[start] ^= arr[end];
    arr[end] ^= arr[start];
    arr[start] ^= arr[end];
}

快速排序

输入数组已排序时最坏

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

主轴元素的选择：

主轴为起始元素（quickSortSimple），每次选取当前数组第一个元素作为主轴。
- 优点：实现简单。
- 缺点：若输入是较为有序的数组，pivot 总是不能均匀地分割数组。若输入数组本身有序，复杂度退化到 O ( n 2 ) O(n^2) O(n2)。
主轴为随机下标元素（quickSortRandom），每次随机选取当前数组的下标，将该下标元素作为主轴。
- 优点：避免了主轴为起始元素时对于基本有序的输入，因不能均匀分割数组导致复杂度退化的情况。
- 缺点：随机数的选取本身消耗一定的性能。
主轴为左、中、右三数大小的居中者（quickSortMedian3），每次比较当前数组起始、中间和末尾三个元素的大小，大小居中者为主轴。
- 优点：实现相对简单，且有效避免简单快排中的劣质分割。
- 缺点：三数取中方法消耗一定性能。

快速排序中的核心方法为 partition。partition 方法执行后，要实现主轴左边元素均小于主轴，主轴右边元素均大等于主轴元素。选定一个数作为主轴后（无论是上述哪种方法选取主轴元素，都将选定的主轴置于当前数组的起始位置）。

方法一：设置一个 index (index = pivot + 1) 动态更新最终的主轴下标。从左到右将主轴后的所有元素依次与主轴元素比较，若小于主轴则将该数字与下标为 index 的数字交换，index 右移一位，使得 index 的前一位总是当前最后一个小于主轴的元素。遍历比较结束后，交换下标为 pivot 与 index - 1 的数字，并将当前主轴的下标 index - 1 返回。
方法二：设置两个变量 first 和 last，分别指向当前区间的第一个和最后一个元素下标，且将主轴元素保存到一个变量 pivot 中。先从 last 开始向前遍历，找到第一个小于主轴元素的值，此时将此处的值将开头原主轴元素所在位置 first 的值覆盖掉；然后从 first 开始向后遍历，找到第一个大于等于主轴元素的值，将其覆盖到 last 位置（last 位置的元素已经移动到数组的前方）。循环执行，直到 first = right 即可，此时的索引就是主轴最终处于的位置。

稳定性：不稳定的排序算法。

复杂度

时间复杂度：平均 / 最好为 O ( n log ⁡ n ) O(n log n) O(nlogn)，最坏为 O ( n 2 ) O(n^2) O(n2)。快排每次 partition 主轴均居中，则递归深度为 i 的 partition 有 2 i 2^i 2i 个，这 2^i 个 partition 需要比较的次数是 (除去 2 i − 1 2^{i-1} 2i−1 个主轴元素的元素个数) n − 2 i − 1 n - 2^{i-1} n−2i−1，因此时间复杂度为 O ( n log ⁡ n ) O(n log n) O(nlogn)。最坏情况下，当输入为已排序数组，且采用首位为主轴的方式，第 i 次 partition 后主轴左右两部分总是 left = null，right = n - i，第 i 次 partition 需要比较 n - i 次，共有 n 次 partition，总比较次数 O ( n 2 ) O(n^2) O(n2)，类似于对已排序的数组做选择排序。

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

递归快排

// 三数取中快排
public int[] quickSortMedian3(int[] arr) {
    int n = arr.length;
    if (n < 2)
        return arr;
    quickSortMedian3(arr, 0, n - 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);   // pivot 位置是确定好的位置，则再排序左侧和右侧
        quickSortMedian3(arr, left, pivot - 1);
        quickSortMedian3(arr, pivot + 1, right);
    }
}

// 将left, center, right下标三个数中，大小居中者放到left下标处
private void median3(int[]arr, int left, int right) {
    int mid = left + (right - left) / 2;
    if (arr[left] > arr[mid]) 
        swap(arr, left, mid);   // 左中，大者居中
    if (arr[mid] > arr[right]) 
        swap(arr, mid, right);   // 中右，大者居右，此时最大者居右
    if (arr[mid] > arr[left]) 
        swap(arr, left, mid);   // 左中，大者居左，此时中者居左
}



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

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



// 朴素快排(首位为主轴)
public int[] quickSortSimple(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    quickSortSimple(arr, 0, n - 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) {
    // left 处是 pivot 即主轴点
    int pivot = left, index = pivot + 1;
    // 注意此时 right 是坐标，要执行到最后一个元素，所以是 <=
    // 遍历 index 开始后面的全部元素，将小于 arr[pivot] 的值都集中在前半部分
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, index, i);
            index++;
        }
    }
    // 遍历完成后，[index, right] 内的元素都大于等于主轴元素
    // 最后一个小于主轴元素的元素下标是 index - 1
    swap(arr, pivot, index - 1);
    return index - 1;
}

//　partition 方法的实现方式2
private int partition(int[] arr, int left, int right) {
    // 如果 left 和 right 相邻，则除去第一个元素是主轴，其余元素无需比较
    if(left == right)
		return left;
    // first 和 right 分别是第一个和最后一个元素
    int first = left, last = right, pivot = arr[first];
    while (first < last) {
        // 下方两个 while 中，条件中必须有一个包含 = 的情况，或两个都包含等于
        // 也就是说，不能从后往前与从前往后都是找第一个小于等于或大于等于主轴元素的值
        // 因为可能存在两个相等的元素，且都等于 pivot，此时会无限重复交换，导致超时
        
        // 从后往前找到第一个小于 pivot 的元素下标，为 last
        while (first < last && arr[last] >= pivot) {
            --last;
        }
        arr[first] = arr[last];   // 将后方第一个小于 pivot 的元素放在首部，此时其值不等于 pivot
        // 从前往后找到第一个大于等于 pivot 的元素下标，为 first
        while (first < last && arr[first] < pivot) {
            ++first;
        }
        arr[last] = arr[first];   // 将后方第一个大于等于 pivot 的元素放在后方，覆盖掉刚刚小于的元素
    }
    arr[first] = pivot;   // 此时 first = last，此位置就是最终的位置
    return first;
}

非递归快排（迭代快排）

上述快排以递归形式写出，递归地确定 [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。

public int[] quickSortStack(int[] arr) {
    // 用于保存区间左右边界的栈，按right到left的顺序将初始区间界入栈
    Deque 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 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;
}

双轴快排

双轴快排是单轴快排的改进。前述快排每次递归确定当前区间的主轴，并利用该主轴将当前区间划分为左右两个部分。双轴快排则以两个轴 (pivot1, pivot2) 将当前区间划分为三个子区间，双轴三区间的划分结果要满足：将 [left, pivot1) 称作区间 1，(pivot1, pivot2) 称作区间 2，(pivot2, right] 称作区间 3，其中 pivot1, pivot2 指的是最终位置，区间 1，区间 2，区间 3 均指划分后的最终区间，则区间 1 中的值全部小于 pivot1 处的值，则区间 2 中的值全部大于等于 pivot1 处的值且小于等于 pivot2 处的值，区间 3 中的值全部大于 pivot2 处的值。对三个子区间执行同样的过程，直到无法划分时排序完成。

算法过程：？

public int[] dualPivotQuickSort(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    dualPivotQuickSort(arr, 0, n - 1);   // 后两个参数是下标值
    return arr;
}

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
    }
}

堆排序

将输入数组建立为一个大顶堆，之后反复取出堆顶并对剩余元素重建大顶堆，将依次取出的堆顶逆序排列，即可将原数组从小到大排列完成排序。可以通过交换堆顶与当前未排序部分末尾元素的做法，避免了额外的空间开销，即原地堆排序，程序结束后返回的 arr[] 为已排序状态。

首先将原待排序数组 arr[] 建立为一个大顶堆（heapify 堆化方法）。
交换堆顶和当前未排序部分中最末尾元素，则堆顶元素已排序（此时在数组最末尾）。（堆中的元素是未排序元素，当将堆维护完成后，根节点即索引为 0 处的值就是堆中最大的值，将其与堆中的最后一个节点交换位置，此时此值就是已排序部分中的一个，再对此元素之前的堆进行重新维护）
剩余元素中只有当前堆顶（之前被交换的末尾元素）可能造成堆失序，因此只需对堆顶调用一次调整堆序的下滤 (siftDown) 操作（操作范围为未排序部分），即可恢复未排序部分的堆序。
重复2，3直到所有元素已排序，返回 arr[]。

堆化方法 (heapify)

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

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

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

下滤方法 (siftDown)

下滤 (siftDown) 是堆排序的核心方法，在堆排序中用于在程序开始时创建大顶堆，以及在每次排序堆顶时用于恢复未排序部分的堆序。

恢复堆序的过程就是将影响堆序的元素不断向下层移动（并交换）的过程，因此形象地称之为下滤 (siftDown)。对节点 x 的下滤操作的本质是恢复以 x 为根节点的树的堆序。因此在堆化操作中，只需要分别依次地对最后一个非叶子节点到根节点执行下滤操作，即可使整棵树满足堆序。在排序过程中，每次原地交换后（交换当前堆顶与当前未排序部分最后一个元素），只有新堆顶影响堆序，对其执行一次下滤操作（范围为未排序部分）即可使未排序部分重新满足堆序。

注意，此处沿用 JDK 源码中下滤操作的方法名 “siftDown”，sift 为过滤之意。

稳定性：不稳定的排序方法。

复杂度

时间复杂度： O ( n log ⁡ n ) O(n log n) O(nlogn)。原地堆排序的时间复杂度为 O ( n log ⁡ n ) O(n log n) O(nlogn)，建堆的时间复杂度是 O(n)。

空间复杂度：O(1)。

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

// 将hole处的值下涉到endIdx及之前的位置上
private void siftDown(int[] arr, int hole, int endIdx) {
    int target = arr[hole];   // target是要下滤的节点的值
    int child = hole * 2 + 1;   // child是此节点的左孩子，必存在的
    while (child <= endIdx) {
        // 满足第一个条件childarr[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;   // 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 中最大和最小元素。

稳定性

常规方法是不稳定的排序方法（可以看做是 countArr 是一个栈，先入后出，不稳定）。通过计数来排序，当遍历到 countArr[i] 时，只是连续地输出 countArr[i] 次 i + min，稳定性得不到保证。

要保证稳定，必须使先记录的先输出。可以通过对 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}，表示有 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 的稳定排序结果。例如得到 countArr 为 {2, 0, 0, 4, 6} 时，逆序遍历原数组 arr，将元素 1 放在 sortedArr 中的 countArr[0] - 1 的位置，即 sortedArr[1] = 1，此时 countArr[0]--，倒数第二个 1 放在 sortedArr[0]，使用此方法保证有序。

复杂度

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

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

// 不稳定的计数排序
public int[] countSortUnstable(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    // 得到数组的最小和最大元素
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; 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 < n; 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) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; 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 < n; 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;
        }
    }   // 此时countArr相当于是计算数组的前缀和，即表示大于等于此数的元素个数
    // 根据sortedArr, nums, countArr三者关系完成sortedArr的输出
    int[] sortedArr = new int[n];
    // 将原数组中的数逆序放入已排序数组，实现稳定排序
    for (int i = n - 1; i >= 0; i--) {
        // countArr[arr[i]-min]表示未排序部分小于等于当前元素的值一共有多少，减1表示索引
        sortedArr[countArr[arr[i] - min] - 1] = arr[i];
        countArr[arr[i] - min]--;
    }
    return sortedArr;
}

基数排序

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

遍历待排序数组 arr，找到最大值，计算其位数 maxDigitLen。
数组的数字为 n 进制，就创建大小为 n 的计数数组 countArr，也可以称为 n 个桶。
开始「位」的 for 循环，循环次数等于 maxDigitLen，每一轮对当前所有数字的当前位执行一次计数排序。
每次计数排序结束后将结果写回 arr。
for 循环结束后返回排序结果 arr。

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

稳定性：取决于使用的计数排序是否稳定。

复杂度

时间复杂度：O(d(n + k))。其中 d 是绝对值最大的元素的位数，要进行 d 轮排序，O(n + k) 是计数排序的时间复杂度，总的时间复杂度是 O(d(n + k))。

空间复杂度：O(n + k)，与计数排序相同。

public int[] radixSort(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    int max = Math.abs(arr[0]); // 找到arr中绝对值最大的数
    for (int i = 1; i < n; 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[n];
    for (int i = 0; i < maxDigitLen; i++) {
        int[] countArr = new int[19];   // 处理负数优化，分别表示-9~9的19个不同的值
        // 根据每一个数字当前位的数字，累计相应位置的计数
        for (int j = 0; j < n; j++) {
            // 此步处理要注意，当base大于10时，例如base=100时，1234%100=34
            // 还需要再除以(base/10)，得到的3，然后再+9（考虑负数）才是本次的bucketIdx
            // (arr[j] % base) / (base / 10) 是当前数在倒数第i位的值
            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 = n - 1; j >= 0; j--) {
            // thisBase是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;
}

不利用计数排序

创建一个二维数组（可看作 19 个桶）保存每次遍历的中间结果，耗费的空间较大（每个桶的大小都要等于 arr 大小+1，空间复杂度为 O(19n)）。

public int[] radixSort(int[] arr) {
    int n = arr.length;
    if (n < 2) 
        return arr;
    // 找到arr中绝对值最大者
    int max = Math.abs(arr[0]);
    for (int i = 1; i < n; 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][n + 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)，之后的复杂度取决于每个桶内的排序算法复杂度之和。假设有 k 个桶，且数据分布均匀，若采用 O ( n 2 ) O(n^2) O(n2) 的排序算法，那么总排序时间复杂度为 O ( k ( n / k ) 2 ) = O ( n 2 / k ) O(k(n/k)^2)=O(n^2/k) O(k(n/k)2)=O(n2/k)；若采用 O ( n log ⁡ n ) O(n log n) O(nlogn) 的排序算法，总排序时间复杂度为 O ( k ( n / k ) log ⁡ ( n / k ) ) = O ( n log ⁡ ( n / k ) ) O(k(n/k) log(n/k))=O(n log(n / k)) O(k(n/k)log(n/k))=O(nlog(n/k))。若桶内排序采用 O ( n log ⁡ n ) O(n log n) O(nlogn) 算法，且 k 的大小适当，例如 k = n/p，p 是一个较小的数例如 2，3 等。那么整体的时间复杂度约为 O(n)。虽然形式上为线性复杂度，但其 n 的系数较大，未必优于 O ( n log ⁡ n ) O(n log n) O(nlogn) 的排序算法。当所有元素都被分到同一个桶中，达到最大时间复杂度，为 O ( n 2 ) O(n^2) O(n2) 或 O ( n log ⁡ n ) O(n log n) O(nlogn)（取决于桶内排序采用的排序方法）。

空间复杂度：取决于桶的数据结构，若采用静态数组，由于每个桶都需要保证有 n 个位置，则空间复杂度为 O(kn)；若采用泛型容器，则为 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]);
    }
    int n = arr.length;
    // 用泛型List存储所有桶，每个桶是一个ArrayList，并初始化所有桶。
    // arr.length/3表示设置数组大小三分之一数量的桶，不初始化数量也可以
    List> buckets = new ArrayList<>(n / 3);
    // List> buckets = new ArrayList<>();
    for (int i = 0; i < n; i++) {
    // for (int i = 0; i <= n / 3; i++)   // k = n / 3 时
        buckets.add(new ArrayList<>());
    }
    // 遍历arr，根据元素值将所有元素装入对应值区间的桶中
    for (int i = 0; i < n; 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，可以避免计算精度不够高带来的问题
        // interval表示一个桶内要放置的数的区间大小
        double interval = (double)(max - min) / (double)(n - 1);
        // 下述的interval计算方法也可行
        // double interval = (double)(max - min + 1) / n;
        // k = n/3 的较优方式
        // double interval = (double)(max - min + 1) / (double)(n / 3);
        // arr[i] - min 表示当前数是从初始的min往后数多少个数，除以每个区间的数的个数，才是区间数
        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 bucket : buckets) {
        for (int sortedItem : bucket) {
            arr[index] = sortedItem;   // 复用输入数组arr
            index++;
        }
    }
    return arr;
}

排序算法总结

Java相关栏目本月热门文章