排序算法
This is a page about »排序算法«.
十大排序算法
总结
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔 | O(nlog(n)) | O(nlog^2(n)) | O(nlog^2(n)) | O(1) | 不稳定 |
| 归并 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) | 稳定 |
| 快速 | O(nlog(n)) | O(nlog(n)) | O(n^2) | O(log(n)) | 不稳定 |
| 堆排序 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(1) | 不稳定 |
| 计数 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 |
| 桶 | O(n + k) | O(n + k) | O(n^2) | O(n + k) | 稳定 |
| 基数 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | 稳定 |
这十大排序其实，硬记是不大好的，应该巧记，以及熟悉它的思维，我想这才是重点，因为很多高级语言都已经可以直接调用封装的排序库
-
首先，冒泡排序是，最容易死记硬背的。两轮循环，稳定。
-
接着选择排序，[ 左 (i)|(i+1) 右 ]，在进行便利的时候，左边是已经有序， 在遍历 i 将后面的未排列的元素中与当前的元素vec[i] 比较，完成当轮循环，确定 […i] 是有序的
注意：选择排序是不稳定的，(相同元素的相对位置在排序的过程中可能发生变化)，举例说明，[5a, 8, 5b, 2, 9] 为了标识，两个元素 5,左边的标记为5a，右边的标记为5b在第一次排序的时候，会变成 [2, 8, 5b, 5a, 9] (循环i = 0) 两个5 的相对位置发生了改变由原来的 [5a … 5b] 改编成 [5b … 5a] (后面选择排序的依次是 [2, 5b, 8, 5a, 9] (循环i = 1) -> [2, 5b, 5a, 8, 9] (循环i = 2) -> [2, 5b, 5a, 8, 9] (循环i = 3)) -
接着是插入排序，有 n - 1 次主循环(0~n-2) 然后计算后面的元素 i+1 ，把它插入前面[0 ~ i] 合适的位置 注意是稳定的
-
再接着是希尔排序，采用 gap 划分 [ gap -> gap/=2 -> gap >0] 然后用 插入排序的 伪代码逻辑 tmp = vec[i]; j = i - gap; while(j >= 0 && vec[j] > tmp){vec[j+ gap] = vec[j]; j = j - gap;} vec[j + gap] = tmp; 注意：希尔排序是不稳定的
-
然后归并排序，把 vec 采用递归的思路，一分为二，然后把这两部分排序，拼装，返回。完成上一层的迭代语句，最后，就是一个完整的有序的vec 注意：归并是稳定的
归并排序的思想，迭代、一分为二，一直细分最后只剩一个或两个元素 所以是一个二叉树的结构 -
快排，xxx
-
堆排，xxx
-
计数，统计元素出现次数，然后采用前缀和逻辑 返回output
-
桶，分桶再用稳定的排序对桶内元素排序，所以可以用插入排序，进而是稳定的。注意里也用到了前缀和逻辑
-
基数，比如都是两位数的元素，先按照个位排序，再按照十位排序，进而完成排序，适合整数、char类型排序，是稳定的排序，也用到了前缀和逻辑。
一点认识
计数排序的局限性很高，范围太大的排序(离散)、非整数的排序不是不符合要求的
本质是通过计数 比如 2 2 5 1 3 1 4 1 4 5
经过统计后 1 1 1 2 2 3 4 4 5 5
这样就是排序后的结果，只是 output[count[arr[i] - 1]] = arr[i]; count[arr[i]]–;
采用前缀和 的方式处理 比如 1 1 1 (待排序) ==> 1 1 (待排序)
最开始 采用 count 统计值 x 的个数 y , 储存方式 count[x] = y;
把所有的 x1, x2, x3,...xn 储存，可以按照 min --> max 进行前缀求和 相同的元素(从右往左 依次削掉，就可以把前缀元素全部移入output)
code
我的代码仓库(ten sorts code)
支持泛化排序， 不过特定的比如基数排序支持 char、int
动态排序 code
堆排序
快速排序
end
有几块要注意的，一个是由冒泡到选择。由选择到插入。 插入到希尔。 引入了 gap 归并 引入分治 堆、计数、基数、桶 引入分治 + 前缀和。注意：桶 是 分治再用线程的排序对桶内元素排序，所以稳定性就有保证