各大排序算法的比较、研究与实现

算法是程序最核心的东西啦，很多时候你不知道算法有什么用，这样跟你说吧，你平时用的库函数、方法，大部分都是封装好的算法实现哈哈哈

说明

算法操作对象与方式

操作对象：整型数组，采用随机数生成，为自然数数组
操作方式：本地算法，即在原数组上进行操作的算法，不需要临时的数组空间。
编写风格：本文代码以最小行数和最简洁方式的目标编写，不考虑代码的规范性。

元素交换方法

异或运算减少时间消耗：

private void swapElement(int[] nums, int i, int j) {
    if (nums[i] == nums[j]) return;
    nums[i] ^= nums[j];
    nums[j] ^= nums[i];
    nums[i] ^= nums[j];
}

数组无序程度

使用逆序对进行量化：

对于数组 A，如果存在正整数 i 和 j，且 i < j，存在 A[i] > A[j]。
那么数字对 <i, j> 或 <A[i], A[j]> 可以称之为数组 A 的一个逆序对。

求逆序对的方法有很多，在这里我采用树状数组的求法，当然可以用归并排序计算移动次数的方法来计算逆序对数量，但是为了不和此次的归并排序混在一起，采用同样 $O(n\log_2n)$ 的树状数组求法吧。

由于不同容量的数组，逆序对数量差异很大，为了直观表示，我们使用 逆序对/总元素对 的比率的方式，来量化数组的有序程度：

/**
 * 借助树状数组计算逆序对比例
 * 
 * @param nums 待计算数组
 * @param bound 待计算数组元素的范围，因为这是树状数组的大小
 * @return 逆序对占所有元素对的比率
 */
private static double inversionRatio(int[] nums, int bound) {
    int[] tree = new int[bound];
    long inversion = 0L;
    for (int i = 0; i < nums.length; i++) {
        TreeArrayUtil.add(tree, nums[i], 1);
        inversion += i + 1 - TreeArrayUtil.ask(tree, nums[i]);
    }
    return inversion / ((nums.length / 2.0) * (nums.length - 1));
}

请注意：排序算法的本质就是消除逆序对！

逆序对是本文最重要的概念，算法的速度比拼，本质上就是消除逆序对的速度的比拼！

数组混乱程度

可直接略过，本小节与排序无关。

使用信息熵计算公式：

$H = \sum_{i=0}^{n}-P(i)\log_2{P(i)}$

private double entropy(int[] nums, int bound) {
    // 计算所有元素出现的次数
    int[] times = new int[bound];
    for (int num : nums) times[num]++;
    double h = 0, p;
    for (int time : times) {
        p = 1.0 * time / nums.length;
        h -= p == 0 ? 0 : p * (Math.log(p) / Math.log(2));
    }
    return h;
}

插入排序

思路：

遍历数组，将每个元素逐个插入到已排序的数组中。
这是人类最直观的排序方法，现实中我们就是这么排扑克牌的。

演示：

插入排序

描述：

遍历数组，将遍历到的元素从已排序数组的末端开始比较，插入到已排序数组中合适的位置。

因为是本地算法，因此从末端开始比较就是和上一个元素开始比较，会降低代码复杂度和有效地减少比较次数。

实现：

private void insertSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        if (i == 0 || nums[i] > nums[i - 1]) continue;
        for (int j = i - 1; j > -1; j--) {
            if (nums[j] <= nums[j + 1]) break;
            swapElement(nums, j, j + 1);
        }
    }
}

分析：

时间复杂度：
- 最好： $O(n)$ ；当且仅当原数组为已排序状态；
- 最坏： $O(n^2)$ ；当且仅当原数组为倒序状态；
- 平均： $O(n^2)$ ；每遍历一个元素需要扫描一次已排序数组。
空间复杂度： $O(1)$ ；仅在遍历时用到下标指针；
稳定性：稳定；按顺序遍历，由右往左插入，不会改变相同元素的前后位置。

统计：

数组大小	无序程度	百次平均耗时 $n(ms)$	$\sqrt{n}(ms)$
$10^4$	0.4997	0042.1873	06.4952
$2\times 10^4$	0.5003	0166.2370	12.8933
$10^5$	0.4994	3897.7656	62.4321
$10^4$	0.6013	0049.7346	07.0523
$10^4$	0.7010	0057.4421	07.5791

数组大小与 $\sqrt{n}$ 大小成正比，算法平均耗时为 $O(n^2)$ 得证
算法耗时与算法的无序程度相关，算法无序程度越高，效率越低

缺陷：每一轮排序将未排序数组首元素插入已排序数组准确位置当中，由于数组的插入时间复杂度为 $O(n)$ ，而每一轮仅排序一个元素，因此算法复杂度为 $O(n^2)$ 。对于每一轮排序最好情况为发生 0 次交换，最坏为发生 k 次交换（即插入到已排序数组最前面），平均完成排序工作，需要发生 ${n(n - 1)}\over{4}$ 次交换。交换次数非常多，非常低效。
适用性分析：一般人类不用动脑筋的方法，都是最慢的那一个。

希尔排序

思路：

根据插入排序所存在的缺陷，我们可以设计一种方法，在插入排序开始之前，将较小元素移至数组首部，较大元素移至数组尾部，让数组的无序程度变小。同时，为了让元素跳着移动而非每次仅移动一位，我们可以将数组拆分成多组，组与组交相间隔，这样一组里面的元素间隔就会非常大，移动效率大大提高。

演示:

希尔排序

描述：

首先将数组元素分组，我们组里的成员之间的距离我们称为“步长”；

我们将初始步长设置为 len / 2，再遍历所有分组，对每一个分组内的元素都进行插入排序；

遍历完所有分组之后，我们将步长减半，再重新遍历所有分组和排序分组内的元素，直至步长为 1，为 1 的时候就是对整个数组进行插入排序了，此时数组中的元素已经非常适合进行插入排序了。

实现：

private void shellSort(int[] nums) {
    // 设置步长进行分组
    for (int stepLen = nums.length >> 1; stepLen > 0; stepLen >>= 1) {
        // 遍历所有分组
        for (int groupIdx = 0; groupIdx < stepLen; groupIdx++) {
            // 对每一个分组进行插入排序
            for (int i = groupIdx; i < nums.length; i += stepLen) {
                if (i == 0 || nums[i] > nums[i - 1]) continue;
                for (int j = i - stepLen; j > -1; j -= stepLen) {
                    if (nums[j] <= nums[j + stepLen]) break;
                    swapElement(nums, j, j + stepLen);
                }
            }
        }
    }
}

分析：

时间复杂度：
- 最好： $O(n)$ ；当且仅当原数组为已排序状态；
- 最坏： $O(n^2\log_2n)$ ；当且仅当每个分组都是倒序状态；
- 平均： $O(n^{1.3 \sim 2‬})$ ；不知道，科学家说：“大概是这么多”。
空间复杂度： $O(1)$ ；仅在遍历时用到下标指针和步长变量；
稳定性：不稳定；相同大小的元素在不同分组里前后顺序可能发生改变。

统计：

数组大小	无序程度	百次平均耗时 $n(ms)$	$^{1.65‬}\sqrt{n}(ms)$
$10^4$	0.4992	006.3399	03.0287
$2\times 10^4$	0.5005	021.2429	06.2565
$10^5$	0.5000	391.8142	35.9623
$10^4$	0.6004	005.3105	02.7232
$10^4$	0.7011	004.7598	02.5501

数组的无序程度越高，排序效率反而更高！于文末再做分析。
数组大小与 $^{1.65‬}\sqrt{n}$ 略成正比，本文的算法平均耗时由结果推算大概接近 $O(n^{1.7‬})$ ，主要原因是本文的初始步长选择是 n/2，而实际上选择某些特定步长效率会提高很多。

缺陷：不是稳定算法，时间复杂度也并不稳定，步长难以抉择，难以达到 $O(n^{1.3})$ 的时间复杂度。
适用性分析：适用于数据量小、无序程度较高且无需稳定排序的数组排序

选择排序

思路：

遍历未排序的数组，选择其中的最小值，与已排序数组的后面一位元素交换。

演示：

选择排序

描述：

可以看出，选择排序时间复杂度固定是 $O(n^2)$ ，但是它相比插入排序的聪明之处在于：大大地减少了移动元素的次数，每排序一个元素仅发生一次交换，有效减少了写的次数，完成排序仅需要写 n 次。尽管时间复杂度固定比插入排序高，但是它未必会比插入排序慢。

实现：

private void selectSort(int[] nums) {
    int min = 0, minIdx= -1;
    for (int i = 0; i < nums.length; i++) {
        min = nums[i];
        minIdx = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] >= min) continue;
            min = nums[j];
            minIdx = j;
        }
        swapElement(nums, i, minIdx);
    }
}

分析：

时间复杂度：
- 最好： $O(n^2)$
- 最坏： $O(n^2)$
- 平均： $O(n^2)$
空间复杂度： $O(1)$
稳定性：稳定；只要保持最小元素遇到相同元素不发生改变即可

统计：

数组大小	无序程度	百次平均耗时 $n(ms)$	$\sqrt{n}(ms)$
$10^4$	0.5001	0012.5922	03.5485
$2\times 10^4$	0.4997	0052.3975	07.2386
$10^5$	0.4999	1218.1501	34.9020
$10^4$	0.6005	0013.3029	03.6473
$10^4$	0.7008	0012.6927	03.5627

数组大小与排序耗时开根号成正比，时间复杂度 $O(n^2)$ 得证。
由于每一趟排序仅发生一次写入，因此写入次数恒定，排序效率不会因为数组的无序程度而发生任何影响！

缺陷：看起来很慢，虽然实际上的确慢，但是却比插入排序快！
适用性分析：没什么适用的地方哈哈哈

堆排序

思路：

大根堆的特性：最大的元素永远在堆顶；

我们可以将未排序的元素们转化为大根堆，那么我们只需要将堆顶那个取出来放在已排序数组首部；在重新将未排序数组转化成堆，在取出直至为堆空就可以完成排序啦。

演示：

初始化堆：

初始化堆

进行堆排序：

堆排序

描述：

操作：分为主要两部
1. 将未排序数组维护成大根堆
2. 取出堆顶元素放在排好的前面
条件：最开始要将整个未排序数组初始化成堆
要点：将堆顶元素放在排好的数组最前面，那么，就要将堆顶元素与堆最后一个元素进行交换啦，因为堆最后一个元素就是已排序数组的前一个元素。我们交换之后，堆顶元素成了很小的那个，这个时候我们要维护这个堆，将这个小小的元素下沉回堆底，让剩余最大的元素上浮至堆顶。
规律：对于以数组方式保存的堆，有这样的规律：
1. m 的父节点索引：(m + 1) / 2 - 1；
2. m 的子节点索引：左 (m + 1) * 2 - 1；右 (m + 1) * 2；
3. 所有父节点数量：len / 2；

实现：

private void heapSort(int[] nums) {
    // 将整个数组初始化成堆：从最后一个父节点开始初始化
    for (int i = nums.length - 1; i > -1; i--)
        toMaximumHeap(nums, i, nums.length);
    // 循环地从堆中取出最大值，再维护这个堆
    for (int i = nums.length - 1; i > -1; i--) {
        swapElement(nums, 0, i);
        toMaximumHeap(nums, 0, i);
    }
}

private void toMaximumHeap(int[] nums, int root, int len) {
    // 默认最大子节点为右子节点
    int child = (root + 1) * 2;
    // 若无子节点，退出
    if (child > len) return;
    // 获取最大子节点下标，若没有
    child = child == len ? child - 1
            : nums[child - 1] > nums[child] ? child - 1 : child;
    // 若子节点大于父节点，交换二者
    if (nums[root] >= nums[maxChild]) return;
    swapElement(nums, root, maxChild);
    // 初始化子节点
    toMaximumHeap(nums, maxChild, len);
}

分析：

时间复杂度：
- 最好： $O(n\log_2n)$
- 最坏： $O(n\log_2n)$
- 平均： $O(n\log_2n)$
每次执行 toMaximumHeap() 维护堆时，该方法时间复杂度是 $O(\log_2n)$ ；这是肯定的。

初始时构造最大堆时执行 n/2 次 toMaximunHeap() 方法，因此构造堆时间复杂度为 $n\log_2n$ ；

从堆顶取走最大值放入排序数组，总共将执行 n 次，每次都将执行 toMaximunHeap() 方法，因此进行排序的时间复杂度为 $n\log_2n$ ；

因此二者相加，时间复杂度依旧为 $O(n\log _2n)$ ，且恒定不变
空间复杂度： $O(n)$ ，如果硬要算递归执行 toMaximunHeap() 的栈空间的话，可以是 $O(\log_2n)$
稳定性：不稳定；在堆中，相同大小元素位置是不定的。

统计：

数组大小	无序程度	千次平均耗时 $n(ms)$
$10^4$	0.5000	001.0899
$10^5$	0.4999	011.3476
$10^6$	0.4999	151.5535
$10^4$	0.6006	001.1437
$10^4$	0.7007	001.0722

由于采用数组存储堆，使得元素的交换范围非常大，因此堆排序的效率非常高，在此我使用了排序一千次取平均值的方式。
同样由于大根堆的特性，使得数组的无序程度对于堆排序而言不仅没有影响，反而有助于将更大的数移至堆顶，因此堆排序在无序程度越高，即逆序对越多的地方可能会表现得越强。

$n\log_2n$	比 $10^4\log_210^4$	耗时	比 1.0899
132877‬	1	1.0899	1
1660960	12.4999	11.3476	10.41159
19931600	150.0004	151.5535	139.0527

各数组大小 n 计算出 $n\log_2n$ 的比值与时间的比值接近，表明时间复杂度近似为 $O(n\log_2n)$ ；但肯定是比 $O(n\log_2n)$ 小的。

缺陷：堆排序有点像是逆序排序，有的人觉得堆顶为最大元素，那么将堆顶往后移，后面重新构建堆就可以一步步排出从大到小的数组；但是从头初始化堆的成本远高于取出最大值再维护堆的成本；因此堆排序略微有些复杂，不容易被初学者接受。
适用性分析：不考虑稳定性，较为无序的数组排序。

冒泡排序

思路：

在未排序数组中循环进行左右比较，若左元素比右元素大，则左右交换，使得每一次循环将未排序数组中最大的元素推向数组末端直至完成排序。

演示：

冒泡排序

描述：

最暴力的、最容易实现的解法了，循环 n 次，每次冒出 1 个最大值。

可以设置一个 flag，用于记录数组是否已经排好序了，如果一次循环中并没有发生任何交换，那么这个数组是已经排序好的了。

实现：

private void bubbleSort(int[] nums) {
    boolean isFinish;
    for (int i = nums.length - 1; i > -1; i--) {
        isFinish = true;
        for (int j = 0; j < i; j++) {
            if (nums[j] <= nums[j + 1]) continue;
            swapElement(nums, j, j + 1);
            isFinish = false;
        }
        if (isFinish) break;
    }
}

分析：

时间复杂度：
- 最好： $O(n)$ ；感谢 isFinish 的存在；
- 最坏： $O(n^2)$ ；最坏和平均是一样的。
- 平均： $O(n^2)$ ；
空间复杂度： $O(1)$
稳定性：稳定，如果两个元素相等，则先将后面的元素推向最后

统计：

数组大小	无序程度	百次平均耗时 $n(ms)$	$\sqrt{n}(ms)$
$10^4$	0.5002	00150.0880	012.2510
$2\times 10^4$	0.4999	00614.2909	024.7849
$10^5$	0.5000	15232.5307	123.4201
$10^4$	0.6009	00143.7275	011.9886
$10^4$	0.7012	00130.3650	011.4177

数组大小与 $\sqrt{n}$ 大小成正比，算法平均耗时为 $O(n^2)$ 得证。
与数组的无序程度无关，会越来越快有点奇怪。

缺陷：慢得出奇，冒泡排序相邻交换的排序方式，使得它每一轮排序，最多消除 n - 1 个逆序对，0.5 无序程度的数组逆序对的数量为 $n(n - 1) / 4$ ，这表明它永远需要 n 轮排序，时间复杂度固定为 $O(n^2)$ ，而每一轮排序平均发生 n/2 次写入，平均完成一次排序需要进行 ${n(n - 1)}\over{2}$ 次写入，比插入排序还要慢，堪比蜗牛。
适用性分析：比插入排序还慢，沦为本文最慢的算法，一般是给初学编程者学习循环语法用。

鸡尾酒排序（双向冒泡排序）

思路：

由于单次冒泡总是至左向右单方向的进行，如果同时让大的往后冒，小的往左冒，会加快排序的速度，因为在一次循环消除了两倍于冒泡排序的逆序对。

演示：

鸡尾酒排序

描述：

设置左右边界，每一趟排序从左边界开始将大数推向右边界，从有边界开始将小数推向左边界，结束时左右边界减一。

同时依旧可以设置一个标识表示排序提前结束，实验中发现快了 5%；

由于左右边界是同时往中间夹逼，那么起始知道了左边界就可以算出右边界，不必特意为右边界设置变量：右边界 = 数组长度 - 1 - 左边界，即 nums.length - 1 - index 为右边界。

实现：

static void cocktailSort(int[] nums) {
    boolean isFinish = false;
    for (int index = 0; index < nums.length - 1 - index; index++) {
        if (isFinish) break;
        isFinish = true;
        for (int i = index; i < nums.length - 1 - index; i++) {
            if (nums[i] > nums[i + 1]) {
                swapElement(nums, i, i + 1);
                isFinish = false;
            }
            if (nums[nums.length - 1 - i] < nums[nums.length - 2 - i]) {
                swapElement(nums, nums.length - 1 - i, nums.length - 2 - i);
                isFinish = false;
            }
        }
    }
}

分析：

时间复杂度：
- 最好： $O(n)$ ，感谢 isFinish 的存在；
- 最坏： $O(n^2)$
- 平均： $O(n^2)$
空间复杂度： $O(1)$
稳定性：稳定，相同大小的元素并不会发生交换，因此前还是前，后还是后。

统计：

数组大小	无序程度	百次平均耗时 $n(ms)$	$\sqrt{n}(ms)$
$10^4$	0.4994	0089.9583	09.4846
$2\times 10^4$	0.5001	0389.3415	19.7317
$10^5$	0.5000	9773.6557	98.8618
$10^4$	0.6001	0123.3666	11.1071
$10^4$	0.7004	0113.6403‬	10.6602

缺陷：可以看到，其速度接近冒泡排序的一倍，但本质还是邻位比较交换，消除逆序对的效率太差，因此还是非常慢。
适用性分析：可以用来锻炼初学者的思考能力和代码实现能力。

快速排序

思路：

选取一个数，把比它小的放在它的左边，比它大的放在它的左边！

这样这个数就是在对的位置啦！

那我把左边也这样处理，右边也这样处理，处理到最后不久排好了吗？

演示：

以首元素为中介的快速排序：

快速排序

随机选取中介的快速排序：

随机快速排序

描述：

默认选取待排序数组的末元素，将其设置为中介；

遍历待排序数组，用指针记录最后一个比中介小的元素下标 cur；

若遍历元素大于中介，遍历下一元素；
若遍历到的元素小于等于中介：
- 若 cur 为当前元素的上一元素，则 cur++ 指向当前元素；
- 若 cur 并非指向前一元素，则 cur++，并将当前元素与 cur 所指向的元素交换。

实现：

void fastSort(int[] nums) {
    fastSortSubArray(nums, 0, nums.length);
}

void fastSortSubArray(int[] nums, int begIdx, int endIdx) {
    if (endIdx - begIdx == 1) return;
    if (endIdx - begIdx == 2) {
        if (nums[endIdx - 1] < nums[begIdx]) swapElement(nums, begIdx, endIdx - 1);
        return;
    }
    int cur = begIdx - 1;
    for (int i = begIdx; i < endIdx - 1; i++) {
        if (nums[i] > nums[endIdx - 1]) continue;
        if (++cur == i) continue;
        swapElement(nums, cur, i);
    }
    swapElement(nums, ++cur, endIdx - 1);
    if (cur != begIdx) fastSortSubArray(nums, begIdx, cur);
    if (cur != endIdx - 1) fastSortSubArray(nums, cur + 1, endIdx);
}

分析：

时间复杂度：
- 最好： $O(n\log_2n)$ ；
- 最坏： $O(n^2\log_2n)$ ；
- 平均： $O(n\log_2n)$ 。
空间复杂度： $O(1)$ ，如果要算上递归栈的话，最多是 $O(n\log_2n)$ 的空间。
稳定性：不稳定，由于远距离交换的缘故，二相同元素的最终顺序是难以预测的。

统计：

数组大小	无序程度	千次平均耗时 $n(ms)$
$10^4$	0.4999	000.7552
$10^5$	0.4999	008.6783
$10^6$	0.5000	116.3201
$10^4$	0.6008	001.1011
$10^4$	0.7012	001.3935‬

$n\log_2n$	比 $10^4\log_210^4$	耗时	比 0.7552
132877‬	1	0.7552	1
1660960	12.4999	8.6783	11.4914
19931600	150.0004	116.3201	154.0256

时间复杂度的增长从未达到 $O(n\log_2n)$ ，到超越 $O(n\log_2n)$ ，这透露出快速排序适用于小规模排序。
快速作为排序算法在远距离交换这一点是做的不错的，但是仍会随着无序度或数组大小的上升而花费更多时间。因为：快速排序的效率取决于中介的选取是否合理，如果中介的取值太大/太小，就会导致数组拆分得很不均匀，甚至是根本没有拆分！
因此我们可以优化快速排序算法，通过一系列初始操作，让中介的取值接近于中位数，甚至是设置多个中介，分多个区间！

缺陷：既不稳定，又不稳定。
适用性分析：适用于均匀的、规模较小的数组排序。

归并排序

思路：

分而治之，把数组分成两半，先排左边一半，再排右边半，然后整理并合起来！

演示：

归并排序

描述：

将数组拆分到只剩单个元素；
对每两个已经有序的子数组进行归并：

采用双指针的方法合并数组，将达到最快的 $O(n + m)$ 的时间复杂度

实现：

void mergeSort(int[] nums) {
    mergeSortSubArray(nums, 0, nums.length);
}

void mergeSortSubArray(int[] nums, int begIdx, int endIdx) {
    // 若仅剩一个元素，返回
    if (endIdx - begIdx == 1) return;
    // 若仅剩两个元素，判断交换后返回
    if (endIdx - begIdx == 2) {
        if (nums[begIdx] > nums[begIdx + 1])
            swapElement(nums, begIdx, begIdx + 1);
        return;
    }
    int midIdx = begIdx + (endIdx - begIdx) / 2;
    // 拆分为二子数组
    mergeSortSubArray(nums, begIdx, midIdx);
    mergeSortSubArray(nums, midIdx, endIdx);
    // 归并二已排序的子数组
    if (nums[midIdx - 1] < nums[midIdx]) return;
    int[] leftPart = new int[midIdx - begIdx];
    System.arraycopy(nums, begIdx, leftPart, 0, leftPart.length);
    if (nums[begIdx] > nums[endIdx - 1]) {
        for (int i = 0; i < endIdx - midIdx; i++) {
            swapElement(nums, begIdx + i, midIdx + i);
        }
        System.arraycopy(leftPart, 0, nums, begIdx + (endIdx - midIdx), leftPart.length);
    } else {
        int cur = begIdx, i = 0, j = midIdx;
        while (i < leftPart.length && j < endIdx) {
            nums[cur++] = leftPart[i] <= nums[j] ? leftPart[i++] : nums[j++];
        }
        if (i < leftPart.length) {
            System.arraycopy(leftPart, i, nums, cur, leftPart.length - i);
        }
    }
}

分析：

时间复杂度：
- 最好： $O(n\log_2n)$ ；
- 最坏： $O(n\log_2n)$ ；
- 平均： $O(n\log_2n)$ ；
空间复杂度： $O(n\log_2n)$ ；因为每一层排序最多需要请求 $n\over2$ 的空间，共 $\log_2n$ 层排序；所以实际上需要最多 ${n\log_2n}\over 2$ 的空间
稳定性：稳定，若左部分元素与右部分相同，则先取左部分。

统计：

数组大小	无序程度	千次平均耗时 $n(ms)$
$10^4$	0.5000	00.7566
$10^5$	0.5000	09.2090
$10^6$	0.5000	96.2454
$10^4$	0.6008	00.7228
$10^4$	0.7009	00.6623

$n\log_2n$	比 $10^4\log_210^4$	耗时	比 0.7566
132877‬	1	0.7566	1
1660960	12.4999	9.2090	12.1716
19931600	150.0004	96.2454	127.2078

终究无法到达 $O(n)$ 的复杂度。但我们依旧可以让它逼近甚至达到 $O(n)$ ，让每一层较大的归并排序都处于一个单独的线程/协程中！

缺陷：由于拆分和归并操作对于小数组而言步骤过多，因此归并排序在小规模排序中并不是速度的顶峰。
适用性分析：适用于无序程度高，需求稳定、快速的大规模排序

基数排序

思路：

对所有数据的各个位数使用容器进行归类，使数据从个位至高位逐渐有序化，低位完成归类后，对高位进行归类时，低位已自动有序化

演示：

基数排序

描述：

先初始化十个桶，因为十进制最多从 0 ~ 9；

根据个位填满这些桶，从第 0 个桶开始将所有元素取出，取出顺序由桶底至桶顶。

再根据十位、百位、千位… 直至最高位数；最后一次取出即完成排序。

实现：

void radixSort(int[] nums) {
    List<Queue<Integer>> buckets = new ArrayList<>(10);
    for (int i = 0; i < 10; i++) buckets.add(new LinkedList<>());
    int radix = 10, max = Integer.MIN_VALUE, index;
    for (int i = 0; i < radix; i++) {
        int mod = (int) Math.pow(10, i + 1), divisor = (int) Math.pow(10, i);
        // 入桶
        for (int num : nums) {
            if (i == 0) max = Math.max(num, max);
            buckets.get(num % mod / divisor).add(num);
        }
        // 出桶
        index = 0;
        for (Queue<Integer> integers : buckets)
            while (!integers.isEmpty()) nums[index++] = integers.poll();
        // 在排序个位数的时候，测出数组最大值的最高位。
        if (i == 0) {
            while (max / radix != 0) radix *= 10;
            radix = (int) Math.log10(radix);
        }
    }
}

分析：

时间复杂度：

遍历一次排序一位，设最高位为 radix，因此时间复杂度恒为 $O(n \times radix)$ 。
- 最好： $O(n \times radix)$ ；
- 最坏： $O(n \times radix)$ ；
- 平均： $O(n \times radix)$ ；
空间复杂度： $O(n)$ ，花费和数组相同大小的空间
稳定性：稳定，相同元素入桶顺序、出桶顺序与其在原数组中的顺序相同

统计：

数组大小	radix	无序程度	千次平均耗时 $n(ms)$
$10^4$	5	0.5000	000.8982
$10^5$	5	0.5000	018.1356
$10^5$	6	0.5000	022.8198
$10^5$	7	0.5000	026.4622
$10^6$	5	0.5000	209.5480
$10^4$	5	0.6004	001.4253
$10^4$	5	0.7006	001.8714

数组的无序程度会明显地对基数排序造成影响，因为会导致某些桶很臃肿而其他桶很小，数量的不平衡导致对速度造成影响。

$10^5\times radix$	比 50000	千次平均耗时 $n(ms)$	比 18.1356
50000	1	18.1356	1
60000	1.2	22.8198	1.2583
70000	1.4	26.4622	1.4591

可以看出其速度和待排序数组的最高位大小有明显的线性关系，由此可得相同规模的数组，位数越小越适合基数排序。或许你会发现，当位数仅有个位时，基数排序就变成了桶排序。

缺陷：对于极差极大的数组，应用基数排序后果是不可想象的，你会发现到最后所有数都装在 0 号桶中，严重影响性能！
适用性分析：无序程度低、最高位位数小的数组，与数组规模无关。

综合分析

按照方法分

使用比较方式进行排序的算法：

插入排序、希尔排序、堆排序、选择排序、冒泡排序、鸡尾酒排序、快速排序、归并排序
使用非比较方式进行排序的算法：

基数排序、桶排序
使用分治思想的算法：

快速排序、归并排序
借助树进行排序的算法：

堆排序

各速度比较

时空复杂度

排序算法	平均时间复杂度	空间复杂度	稳定性	逆序对数提升	数组规模提升
插入排序	$O(n^2)$	$O(1)$	稳定	表现差	无影响
希尔排序	$O(n^{1.3 \sim 2})$	$O(1)$	不稳定	表现优	无影响
选择排序	$O(n^2)$	$O(1)$	稳定	无影响	无影响
堆排序	$O(n\log_2n)$	$O(1)$	不稳定	表现优	表现优
冒泡排序	$O(n^2)$	$O(1)$	稳定	无影响	无影响
鸡尾酒排序	$O(n^2)$	$O(1)$	稳定	无影响	无影响
快速排序	$O(n\log_2n)$	$O(1)$	不稳定	表现差	表现差
归并排序	$O(n\log_2n)$	$O(n)$	稳定	无影响	表现优
基数排序	$O(n\times k)$	$O(n)$	不稳定	无影响	表现差

实验结果比较

排序算法	$10^4$	$2\times 10^4$	$10^5$	$10^6$
插入排序	42.1873	166.2370	3897.7656	-
希尔排序	6.3399	21.2429	391.8142	-
选择排序	12.5922	52.3975	1218.1501	-
堆排序	1.0899	-	11.3476	151.5535
冒泡排序	150.088	614.2909	15232.5307	-
鸡尾酒排序	89.9583	389.3415	9773.6557	-
快速排序	0.7552	-	8.6783	116.3201
归并排序	0.7566	-	9.2090	96.2454
基数排序	0.8982	-	18.1356	209.5480

算法解析

用途归纳

小规模数组：

快速排序、基数排序
中规模数组：

随机快速排序、堆排序、归并排序
大规模数组：

归并排序
思想借鉴：

希尔排序、堆排序、归并排序

在 Java 中，Arrays 的排序方法实现是这样的：判断数组规模，规模小使用随机快速排序，规模大则使用归并排序，时间复杂度都为 $O(n\log_2n)$

各大排序算法的比较、研究与实现

说明

算法操作对象与方式

元素交换方法

数组无序程度

数组混乱程度

插入排序

希尔排序

选择排序

堆排序

冒泡排序

鸡尾酒排序（双向冒泡排序）

快速排序

归并排序

基数排序

综合分析

按照方法分

各速度比较

时空复杂度

实验结果比较

算法解析

用途归纳

Search Articles

Wechat

Catalogue