排序算法
十大排序算法
总结
排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡 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
end
有几块要注意的，一个是由冒泡到选择。由选择到插入。 插入到希尔。 引入了 gap 归并 引入分治 堆、计数、基数、桶 引入分治 + 前缀和。注意：桶 是 分治再用线程的排序对桶内元素排序，所以稳定性就有保证