排序算法

稳定性概念

排序前后大小相同元素的序列顺序是否改变，不发生改变则为稳定。

种类

1 选择排序

原理

每次找出第 i 小的元素，将该元素与第 i 位元素交换。

性能

稳定性：不稳定。交换元素时会打破稳定性。
时间复杂度： O(n²)。
空间复杂度：O(1)。

原地算法概念：不需要增加数量级的额外空间复杂度的算法。选择排序为原地算法。

2 冒泡排序

原理

每次检查相邻的元素，并根据条件判断是否交换。

性能

稳定性：稳定。
时间复杂度：最优时间复杂度为O(n)，最坏时间复杂度为O(n²)，平均时间复杂度为O(n²)。
空间复杂度：O(1)。

3 插入排序

原理

将元素分为已排序和未排序两部分。每次从未排序的元素中选出一个插入已排序序列。
通常已排序部分为第 0 ~ i-1 位，插入元素为第 i 位。

性能

稳定性：稳定。
时间复杂度：最优时间复杂度为O(n)，最坏时间复杂度为O(n²)，平均时间复杂度为O(n²)。
空间复杂度：O(1)。

4 计数排序

原理

根据元素取值范围设置一个额外数组 numCount ，元素值上下界的差为数组的宽度。计算取值范围内每个值出现的次数，再计算 numCount 的前缀和。利用前缀和从又至左确定元素排名。
例如元素取值范围为1~100，则定义 vector< int> numCount(100); ，其中若17出现4次，则numCount[16] = 4; 。

性能

稳定性：稳定。
时间复杂度：O(n + w)，其中w为取值范围。
空间复杂度：O(n + w)。

适用场景

数据取值范围较小的时候。

5 基数排序

原理

将待排序元素分为k个关键字，按顺序对每一个关键字进行排序。关键字内排序可以使用计数排序。
例如对长度为 m 的 string 类型按字典序进行排序，从第 m-1 位到第 0 位依次进行排序。
对于整型数据可以从个位到最高位进行排序，不足位数添加前导零即可。

性能

稳定性：稳定。
时间复杂度：关键字内部使用计数排序时，时间复杂度为O(nm + ∑wi)，其中m为关键字个数，w为取值范围。关键字内部使用O(nlogn)排序方法时，时间复杂度为O(mnlogn)。
空间复杂度：O(n + k)。

6 快速排序

原理

快速排序运用了递归的思想。随机选取一个数，把比它大的数和比它小的数分到两边，再用同样的方式处理两边的数组。

性能

稳定性：不稳定。
时间复杂度：最优时间复杂度和平均时间复杂度为O(nlogn) ，最坏时间复杂度为 O(n²)。
空间复杂度：O(logn) ~ O(n)。

内省排序

内省排序是快排和堆排的结合，是对快排的一种优化。内省将快排的最大递归深度限制在O(logn)，超过该深度时改用堆排。algorithm 库中 sort 函数使用的是内省排序。

7 归并排序

原理

采用分治思想，二分数组递归排序。

性能

稳定性：稳定。
时间复杂度：O(nlogn) 。
空间复杂度：O(n)。

8 堆排序

原理

利用二叉树的性质，第 i 位的元素，第 i2+1 位和第 i2+2 位为其儿子元素。先建立大根堆或小根堆，再从最后一个叶子结点往前进行处理。

性能

稳定性：不稳定。
时间复杂度：O(nlogn) 。
空间复杂度：O(1)。

9 桶排序

原理

桶排序和计数排序类似，按取值范围均分为m段，把元素放到每一段（桶）里，再对每一段（每个桶）进行排序。

性能

稳定性：桶内部使用插入排序时稳定。
时间复杂度：桶内部使用插入排序时，平均时间复杂度时间复杂度为O(n + n²/m + m) ，最坏时间复杂度为O(n²)。
空间复杂度：O(n)。

适用场景

数据分布均匀的时候。

10 希尔排序

原理

希尔排序是对插入排序的优化。把数组中的元素看作是一个矩阵，分成m列，逐列进行插入排序排序，m从某个整数逐渐减为1。

性能

稳定性：不稳定。
时间复杂度：平均时间复杂度和最坏时间复杂度和m减小的方式有关系，例如 m=m/3，则时间复杂度为O(n^(3/2))。
空间复杂度：O(1)。