十大排序算法 | Ziuch の Blog

type

status

date

slug

summary

0 本节习题一览

排序例题：912. 排序数组

归并排序习题1：剑指 Offer 51. 数组中的逆序对

归并排序习题2：315. 计算右侧小于当前元素的个数

快速排序习题：215. 数组中的第K个最大元素

1 冒泡排序 O()

💡

排序最多进行n-1轮，每一轮都是在消除逆序，最终结果是把最值搬运到无序序列的末端

💡

如果在某一轮未进行交换(无逆序)，说明此时已经完成排序

适用场景：

💡

冒泡排序思路简单，代码也简单，特别适合小数据的排序。

代码实现：

2 选择排序 O()

💡

排序进行n-1轮，每一轮找到最值的下标与无序序列的末端下标进行交换

💡

当需要交换的下标相同时，无需进行交换

适用场景：

💡

选择排序实现简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。

代码实现：

3 插入排序 O()

💡

类似打牌的时候整理牌型，每次从未排序序列中取出一个数比较大小之后插入排序序列内

适用场景：

💡

在数据较大的时候不适用。但是，在数据比较少可以做为快速排序的扩充。

代码实现：

4 希尔排序 O()

💡

是插入排序的改进，只不过每次增量不是1，可以看作是增量逐渐减小至1的插入排序

💡

增量序列的设置是影响希尔排序效率的重要因素，可以简单地取2^k-1

适用场景：

💡

希尔排序虽然快，但是毕竟是插入排序，其并没有O(nlogn)的算法快。在大量数据面前，希尔排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。

代码实现：

5 归并排序 O(nlogn)

💡

先分治到每一份只包含一个数(一个数一定是有序的)，再依次将两个有序序列合并

适用场景：

💡

归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度O(n)使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。

代码实现：

归并排序习题1：剑指 Offer 51. 数组中的逆序对

归并排序习题2：315. 计算右侧小于当前元素的个数

6 快速排序 O(nlogn)

💡

随机选出一个数x，利用双指针将序列划分为三段，小于x，等于x，大于x。再递归地对小于/大于x的序列继续做，直到序列的长度为1

适用场景：

💡

快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。

代码实现：

快速排序习题：215. 数组中的第K个最大元素

7 堆排序 O(nlogn)

💡

利用堆的形状，依次弹出n次堆顶即可得到有序序列

适用场景：

💡

堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。

代码实现：

8 计数排序 O(n + k)

💡

空间换时间，利用数字天然有序的特点，先存后取

适用场景：

💡

排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用0-800就OK啦；又比如一群人的年龄，用个0-150应该就可以了，再不济就用0-200喽。另外，计数排序需要占用大量空间，它比较适用于数据比较集中的情况。

代码实现：

9 桶排序 O(n + k)

💡

利用分治的思想，先尽量均匀的把数分成n份，随后分别对这n份进行排序，最后再合并

适用场景：

💡

桶排序可用于最大最小值相差较大的数据情况，但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。

代码实现：

10 基数排序 O(n * k)

💡

依次对每个数的个位十位百位等进行计数排序，直到最高数位，注意数字先进先出

适用场景：

💡

基数排序要求较高，元素必须是整数，整数时长度10W以上，最大值100W以下效率较好，但是基数排序比其他排序好在可以适用字符串，或者其他需要根据多个条件进行排序的场景，例如日期，先排序日，再排序月，最后排序年，其它排序算法可是做不了的。

💡

如果正数负数都存在，可分开进行两次基数排序再合并

代码实现：