十大常见排序算法简介和代码实现-Java版

总结了一下常见的十种内部排序算法，相关知识已经很熟悉了，主要是代码实现

各种排序算法，根据元素是否完全在内存中，可以分为内部排序和外部排序。外部排序基于归并，多了一些文件操作。本博客接下来提到的排序算法，默认是内部排序算法。

排序算法可以分为两大类，一种是基于比较的，例如熟悉的快排、归并、直插等，另一种是桶排、计数排序这种不基于比较的

本博文中

排序顺序默认是从小到大

数组默认是按照顺序存储(可随机读写)的32位int整型数组

基于比较操作的排序算法

基于比较和移动的排序算法，时间复杂度最优为 $\Omicron(n\log_2{n})$

首先是插入排序，每一趟将一个待排序的元素插入到已经有序的子数组中的相应位置，直至有序的子数组包含全部元素

直接插入排序

插入排序的最简单实现，每趟排序都将一个待排序元素插入到有序部分，直至没有带排序的元素

代码实现

public static void insertSort(int[] q) {
    int n = q.length;
    for (int i = 1; i < n; ++i) {
        int cur = q[i];
        int j = i - 1;
        while (j >= 0 && cur < q[j]) {
            q[j + 1] = q[j];
            j--;
        }
        if (j + 1 != i) q[j + 1] = cur;
    }
}

时间复杂度 $\Omicron(n^2)$

空间复杂度 $\Omicron(1)$ ，不使用额外空间

其中，寻找当前元素 cur 插入位置的操作可以通过二分查找，将时间复杂度减少到 $\Omicron(\log_2 n)$ ，但是 「移动」 操作仍然是 $\Omicron(n)$ 的，整体复杂度不会减少，一般不这么写

直接插入排序算法，是稳定的

当初始数组基本有序时，直接插入算法是很高效的，近乎 $\Omicron(n)$ 的复杂度，因为对于每个待排序元素，一旦找到其插入位置，本躺排序就结束了。这点和简单选择排序有很大区别

希尔排序

希尔排序是对直接插入排序的一种优化，最早由D.L.Shell于1959年提出。

主要是将元素按照下标以一定增量进行分组，每一趟排序，对一组内的元素使用直插进行排序，增量逐渐减少，直至为1，所有的元素都在一组

例如，nums = [5,7,5,8,6,9,1,4,3], n = 9，增量为step=3时

第一组：[5, 8, 1] nums[0],nums[3],nums[6]

第二组：[7, 6, 4] nums[1],nums[4],nums[7]

第三组：[5, 9, 3] nums[2],nums[5],nums[8]

希尔排序的复杂度跟选取的增量序列(wiki上称作步长序列)有关

之所以性能优于直接插入排序，就是因为其元素每次移动step个距离，而不是仅移动一位

希尔本人提出的增量序列，$step_0 = n/2, step_{i+1} = step_i / 2$

public static void shellSort(int[] q) {
    int n = q.length;
    int cur;

    for (int step = n / 2; step >= 1; step /= 2) {
        for (int i = step; i < n; ++i) {
            cur = q[i];
            int j = i - step;
            while (j >= 0 && cur < q[j]) {
                q[j + step] = q[j];
                j -= step;
            }
            if (j + step != i) q[j + step] = cur;
        }
    }
}

其他性能更优的增量序列，参照希尔排序-步长序列|维基百科

希尔排序是不稳定的

在对包含十万个随机数字的数组排序的过程中，实测，采用最优增量序列的希尔排序是所有算法中(包括计数排序等妖怪)最快的

---

然后是交换排序，其主要思想是：根据两个元素的比较结果，交换其位置

冒泡排序

冒泡排序是交换排序中最简单的一种实现，每一趟排序中，如果 nums[i-1] > nums[i] ，则交换俩元素位置，这样本躺排序结束时，都会将当前最小的元素交换到待排序子数组的起始位置

实现细节上，可以设置一个布尔型变量，如果当前躺排序没有发生任何交换，说明全部元素均已经有序，可以直接返回。如此这般，对于基本有序的初始数组来说，冒泡排序很高效

代码

public static void bubbleSort(int[] q) {
    boolean flag;
    int n = q.length;
    int temp;
    for (int i = 0; i < n; ++i) {
        flag = false;
        for (int j = n - 1; j > i; --j) {
            if (q[j] < q[j - 1]) {
                flag = true;
                temp = q[j];
                q[j] = q[j - 1];
                q[j - 1] = temp;
            }
        }
        if (!flag) break;
    }
    return;
}

时间复杂度 $\Omicron(n^2)$ ，最理想情况(初始数组基本有序)下，时间复杂度为 $\Omicron(n)$

空间复杂度 $\Omicron(1)$ ，不使用额外空间

快速排序

快速排序，已经很熟悉了，不再赘述

快排基于分治的思想，每一趟排序，选定一个枢轴元素pivot，通过交换，使得待排序数组分成左右两部分，左边数组的元素均小于pivot，右边数组元素均大于pivot，那么pivot其实就已经在其最终位置上了。然后再分别递归处理左右数组，直至所有元素均处于其最终位置

代码实现

public static void quickSort(int[] q, int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {
        while (q[++i] < x) ;
        while (q[--j] > x) ;
        if (i < j) {
            int temp = q[i];
            q[i] = q[j];
            q[j] = temp;
        }
    }
    quickSort(q, l, j);
    quickSort(q, j + 1, r);
}

最理想情况下，每次划分数组，都根据pivot将数组切成等长的两半，这样划分次数也就是排序的趟数是 $\Omicron(\log_2{n})$ 的，每一趟排序，比较和交换操作的复杂度是 $\Omicron(n)$ 的，这样整体复杂度为 $\Omicron(n\log_2{n})$

PS：由于代码实现是用递归实现的，这里的「一趟排序」指的是，在递归调用树上，处于同一树层的，比较和交换的过程

当然，最坏情况下，如果每次选取的pivot恰好是数组的端点，这样划分次数是 $\Omicron(n)$ 的，整体时间复杂度退化为 $\Omicron(n^2)$ 。由于递归需要借助栈，空间复杂度此时也退化为了 $\Omicron(n)$

因此，每趟划分，pivot的选取很关键，一般来说是用随机数好一点，或者选中点

平均情况下，时间复杂度为 $\Omicron(n\log_2{n})$ ，空间复杂度为 $\Omicron(\log_2{n})$

快速排序是所有内部排序算法中平均性能最优的

快速排序是不稳定的

---

接下来是选择排序，每一趟排序，都会在待排序子数组中选取最小的元素放置在已有序子数组的末尾，直至没有待排序元素

简单选择排序

简单选择排序是选择排序的最直观的实现方式，直接看代码

public static void selectInsert(int[] q) {
    int n = q.length;
    for (int i = 0; i < n; ++i) {
        int curMin = q[i];
        int curMinIdx = i;
        for (int j = i + 1; j < n; ++j) {
            if (curMin > q[i]) {
                curMin = q[i];
                curMinIdx = i;
            }
        }
        if (curMinIdx != i) {
            int temp = q[i];
            q[i] = q[curMinIdx];
            q[curMinIdx] = temp;
        }
    }
}

简单选择排序最大的问题是，无论初始数组的有序程度如何，每一趟排序都会遍历一遍，因此最理想、最坏和平均情况下的时间复杂度都是 $\Omicron(n^2)$ 的，比较次数和初始状态无关

简单选择排序是不稳定的

堆排序

堆排序属于选择排序的一种，利用小根堆，将每一趟排序「选取待排序子数组中最小的元素」这一操作的时间复杂度优化至 $\Omicron(\log_2{n})$ ，由于固定地需要进行 $n$ 趟排序，因此整体时间复杂度为 $\Omicron(n\log_2{n})$

关于堆这种数据结构，已经很熟悉了，这里不再赘述

堆的五种常用操作，参见本博客文章手写堆

堆排序，只用到了向下调整

/**
* 向下调整
*
* @param u
*/
public static void down(int u) {
    int p = u;
    if (2 * u <= cnt && h[2 * u] < h[u]) p = 2 * u;
    if (2 * u + 1 <= cnt && h[2 * u + 1] < h[p]) p = 2 * u + 1;
    if (p != u) {
        int temp = h[u];
        h[u] = h[p];
        h[p] = temp;
        down(p);
    }
}

/**
* 堆排序
*
* @param q
*/
public static void heapSort(int[] q) {
    int n = q.length;
    // h从1开始，方便编号
    // 这样一个节点的左孩子编号为 2 * i， 右孩子为 2 * i + 1
    System.arraycopy(q, 0, h, 1, n);
    // 建立堆
    cnt = n;
    for (int i = n / 2; i >= 1; --i) down(i);
    int idx = 0;
    while (n-- > 0) {
        q[idx++] = h[1];
        // 输出当前最小的之后，向下调整
        h[1] = h[cnt--];
        down(1);
    }
}

堆排序的时间复杂度为 $\Omicron(n\log_2{n})$ 的

空间复杂度为 $\Omicron(1)$ 的，如果数组下标从1开始存储元素。空间占用上是几个 $n\log_2{n}$ 算法中最优的

归并排序

「归并」操作，就是将两个有序数组合并成一个有序数组

归并排序，每一趟，先将当前数组划分成等长的两部分，然后对这两部分递归调用排序算法，最后「归并」已经有序的两部分

递归调用树的叶子节点是什么情况？或者说程序的退出条件

「当前数组只有一个元素或者为空，是肯定有序的。」此时无需再划分后进一步递归执行归并操作

递归实现的代码是基于分治思想的，也可以看作是「自顶向下」

public static void mergeSort(int[] q, int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    mergeSort(q, l, mid);
    mergeSort(q, mid + 1, r);

    // 需要借助一个辅助数组
    int[] temp = new int[r - l + 1];
    int i, j, k;
    // 「归并操作」
    for (i = l, j = mid + 1, k = 0; i <= mid && j <= r; ) {
        if (q[i] < q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];

    System.arraycopy(temp, 0, q, l, r - l + 1);
}

归并排序也可以不用递归实现，采用「自底向上」的思路，先每2个元素(每个单一元素可看作一个有序子数组)合并，然后每4个、8个…，直到全部有序

public int[] mergeSort(int[] nums) {
    // 自底向上
    int n = nums.length;
    int[] tmp = new int[n];
    int start, mid, end, i, j, k;
    for (int len = 1; len < n; len = 2 * len) {
        for (start = 0; start < n; start = start + 2 * len) {
            mid = start + len - 1;
            end = Math.min(start + 2 * len - 1, n - 1);
            if (mid > end) mid = start + end >> 1; // 长度不够len的区间，有可能mid会大于end，超出合法范围
            i = start; j = mid + 1; k = 0;
            // 正常合并
            while (i <= mid && j <= end) {
                if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
                else tmp[k++] = nums[j++];
            }
            while (i <= mid) tmp[k++] = nums[i++];
            while (j <= end) tmp[k++] = nums[j++];

            for (i = start, j = 0; i <= end; ++i, ++j) nums[i] = tmp[j];
        }
    }
    return nums;
}

从自底向上写法中能更直观地看出归并排序的复杂度是 $\Omicron(n\log_2{n})$ 的，由于需要借助一个辅助数组，空间复杂度是 $\Omicron(n)$

归并排序是稳定的

不基于比较的排序算法

这类算法常见的有计数排序、桶排序、基数排序，不借助「比较」操作

桶排序

摘自维基百科，桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 $\Omicron(n)$ 。但桶排序并不是比较排序，他不受到 $\Omicron(n\log_2{n})$ 下限的影响。

算法流程

• 先确定初始数组的元素大小范围，然后设定桶的数量和每个桶的容量；
• 遍历初始数组，根据元素大小分配到相应桶中
• 依次遍历所有非空桶，将桶内元素排序，放到到初始数组相应位置

代码实现

public static void bucketSort(int[] q) {
    int bucketNum = 10000;
    int maxVal = Integer.MIN_VALUE, minVal = Integer.MAX_VALUE;
    for (int x : q) {
        maxVal = Math.max(maxVal, x);
        minVal = Math.min(minVal, x);
    }
    List<Integer>[] buckets = new ArrayList[bucketNum];
    for (int i = 0; i < bucketNum; ++i) buckets[i] = new ArrayList<>();
    int bucketCapacity = (maxVal - minVal) / bucketNum + 1;
    // 放入桶中
    for (int num : q) {
        int bucketIndex = (int) Math.floor((num - minVal) / bucketCapacity);
        buckets[bucketIndex].add(num);
    }
    int idx = 0;
    for (int i = 0; i < bucketNum; ++i) {
        if (buckets[i].size() < 1) continue;
        // 桶内排序
        // 一般也可以用直接插入排序
        Collections.sort(buckets[i]);
        for (Integer num : buckets[i]) {
            q[idx++] = num;
        }
    }
}

不难想到，当所有元素均匀分入各个桶中时，桶排序的效率很高。最坏情况就是几乎所有的元素分入同一个桶。

图片来自Wiki

平均时间复杂度为 $\Omicron(n+k)$ ，最坏时间复杂度为 $\Omicron(n^2)$

空间复杂度为 $\Omicron(n)$ ，其中 $k$ 为桶的个数

计数排序

计数排序是稳定的线性时间排序算法，维持一个频次数组 cnt[N + 1] ，其中N为初始数组的最大值，频次数组 $cnt$ 中 $i$ 位置的值 $cnt[i]$ ，代表着初始数组 $nums$ 中值为 $i$ 的元素的 出现次数，生成频次数组后，再据此将初始数组的元素放到正确位置

个人感觉计数排序就是桶排序下，桶的容量为1的特殊情况

代码实现

public static void countSort(int[] q) {
    // 计算出最大值
    int maxVal = Integer.MIN_VALUE;
    for (int x : q) maxVal = Math.max(maxVal, x);
    int[] cnt = new int[maxVal + 1];
    for (int num : q) cnt[num]++; // 统计频率
    int idx = 0;
    for (int num = 0; num <= maxVal; ++num) {
        // 对于q中出现多次的元素，全部加入结果集
        while (cnt[num]-- > 0) {
            q[idx++] = num;
        }
    }
}

可以优化一下空间占用，令频次数组的起始下标(为0)代表着初始数组的最小值

public static void countExSort(int[] q) {
    int maxVal = Integer.MIN_VALUE, minVal = Integer.MAX_VALUE;
    for (int x : q) {
        maxVal = Math.max(maxVal, x);
        minVal = Math.min(minVal, x);
    }
    int[] cnt = new int[maxVal - minVal + 1];
    for (int num : q) cnt[num - minVal]++;
    int idx = 0;
    for (int i = 0; i < cnt.length; ++i) {
        int num = i + minVal;
        while (cnt[i]-- > 0) {
            q[idx++] = num;
        }
    }
}

注意：以上实现的计数排序是不稳定的

稳定的计数排序实现请参照维基百科

计数排序的最优、平均和最坏时间复杂度均是 $\Omicron(n+(\text{maxVal}-\text{minVal}))$

空间复杂度为 $\Omicron(\text{maxVal}-\text{minVal})$

计数排序对于元素的分布有要求，当元素集中在一定范围时，效率很高，如果分布很分散，不仅效率低，还会造成很大的空间浪费

例如 nums = [1,10001,10002,10003...,10010] 只有11个元素，但是运行时间和空间占用都是 $10^4$ 级别的

基数排序

基数排序采取的是「多关键字排序」思想，将元素每个数位的值都作为关键字。数位从低到高，依次对所有元素进行排序，最终得到一个有序数组。这里默认是LSD（低位优先）排序

排序趟数跟最大元素的最高数位有关，例如：$nums$ 数组中最大的元素为 4321 ，则最高数位为第四位（从右往左），$d = 4$

每一趟排序中，包含「分配」和「收集」两个过程，分配过程是按照当前数位的值，将元素分到对应的桶中；收集则是按照桶的顺序，依次将元素放到初始数组中去。经过 $d$ 趟，初始数组的元素所有数位依次排好序了，则整体有序

代码如下

public static void radixSort(int[] q) {
    // 计算最高数位
    int maxVal = Integer.MIN_VALUE;
    for (int x : q) maxVal = Math.max(maxVal, x);
    int highestDigit = 0;
    for (int t = maxVal; t != 0; t /= 10) highestDigit++;

    // 10进制下，创建10个桶
    // 代表当前数位的值为 0,1,2,3...,9
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < 10; ++i) buckets.add(new ArrayList<>());

    int mod = 10, lastMod = 1;
    // 按照从低位到高位依次排序
    for (int digit = 0; digit < highestDigit; ++digit, mod *= 10, lastMod *= 10) {
        // 分配 O(n)
        for (int num : q) {
            int bucketIndex = (num % mod) / lastMod;
            buckets.get(bucketIndex).add(num);
        }
        // 收集 O(n+r)
        int idx = 0;
        for (int i = 0; i < 10; ++i) {
            for (Integer x : buckets.get(i)) {
                q[idx++] = x;
            }
            buckets.get(i).clear(); // 置空
        }
    }
}

不难想到，若是从大到小排序，则是最高位优先(MSD)

复杂度分析

记 $d=\lceil\log_{10}{\text{maxVal}}\rceil$ ，表示最大值的最高数位，是从右往左第几位

$r = 10$ 表示当前是10进制

由于每一趟包括分配 $\Omicron(n)$ 和收集 $\Omicron(n+r)$ ，则整体时间复杂度为 $\Omicron(d(n+r))$

创建了 $r$ 个桶，则空间复杂度为 $\Omicron(r + n)$

基数排序是稳定的

总结

计数排序的 $N=\text{maxValue-minValue}$ 为数组元素的取值范围

基数排序中，$d = \lceil\log_{10}{\text{maxValue}}\rceil$ 为最大值的位数，$r$ 表示进制

希尔排序的时间复杂度取决于增量序列的选择[1]

快速排序的空间复杂度 $\Omicron(\log_2{n})$ 是指的占用「虚拟机栈」的空间，并且最坏能达到 $\Omicron(n)$

排序算法	稳定性	最优	平均时间复杂度	最坏	空间复杂度
直接插入排序	稳定	$\Omicron(n)$	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(1)$
希尔排序	不稳定	-	-	-	$\Omicron(1)$
冒泡排序	稳定	$\Omicron(n)$	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(1)$
快速排序	不稳定	$\Omicron(n\log_2{n})$	$\Omicron(n\log_2{n})$	$\Omicron(n^2)$	$\Omicron(\log_2{n})^*$
简单选择排序	不稳定	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(1)$
堆排序	不稳定	$\Omicron(n\log_2{n})$	$\Omicron(n\log_2{n})$	$\Omicron(n\log_2{n})$	$\Omicron(1)$
归并排序	稳定	$\Omicron(n\log_2{n})$	$\Omicron(n\log_2{n})$	$\Omicron(n\log_2{n})$	$\Omicron(n)$
桶排序	稳定	$\Omicron(n+k)$	$\Omicron(n+k)$	$\Omicron(n^2)$	$\Omicron(n)$
计数排序	可以稳定	$\Omicron(n+\text{N})$	$\Omicron(n+\text{N})$	$\Omicron(n+\text{N})$	$\Omicron(N)$
基数排序	稳定	$\Omicron(d(n+r))$	$\Omicron(d(n+r))$	$\Omicron(d(n+r))$	$\Omicron(r + n)$

选择适当的排序算法，需要考虑元素的数目，元素的大小，元素的分布，稳定性的要求，存储结构(Ex：顺序存储、链式存储)

如何根据元素数目选择，可以参考JDK自带的Arrays.sort()方法

• 当元素个数小于47，使用直接插入排序
• 当元素个数大于或等于286，使用归并排序
• $47\leq n < 286$ ，使用快速排序

如果初始数组基本有序，则选择直接插入排序或者冒泡排序

如果元素比较大，应避免大量移动的排序算法(Ex：冒泡排序)，可考虑采取链式存储

对于三种常用的 $\Omicron(n\log_2{n})$ 级别的排序算法

• 快速排序的平均性能最优
• 堆排序空间占用最优
• 归并排序是稳定的

参考

1. 希尔排序–步长序列｜维基百科
2. 桶排序｜维基百科
3. 计数排序｜维基百科