排序
冒泡
原地排序: 就是特指空间复杂度是 O (1) 的排序算法. 以下三个都是原地排序.
稳定性: 如果待排序的序列中存在值相等的元素, 经过排序之后, 相等元素之间原有的先后顺序不变.
- // 冒泡排序, a 表示数组, n 表示数组大小
- public void bubbleSort(int[] a, int n) {
- if (n <= 1) return;
- for (int i = 0; i <n; ++i) {
- // 提前退出冒泡循环的标志位
- boolean flag = false;
- for (int j = 0; j < n - i - 1; ++j) {
- if (a[j]> a[j+1]) { // 交换
- int tmp = a[j];
- a[j] = a[j+1];
- a[j+1] = tmp;
- flag = true; // 表示有数据交换
- }
- }
- if (!flag) break; // 没有数据交换, 提前退出
- }
- }
冒泡特色:
原地排序, 空间复杂度 O(1).
稳定的排序算法.
最好情况, 一次冒泡操作, 时间复杂度 O(n), 最坏 O(exp(n) .
分析排序复杂度的两个指标:
有序度: 是数组中具有有序关系的元素对的个数.
有序元素对: a[i] <= a[j], 如果 i <j.
对于一个倒序排列的数组, 比如 6,5,4,3,2,1, 有序度是 0; 对于一个完全有序的数组, 比如 1,2,3,4,5,6, 有序度就是 n*(n-1)/2, 也就是 15. 我们把这种完全有序的数组的有序度叫作满有序度.
逆序度: 与有序度相反, 逆序度 = 满有序度 - 有序度.
插排
将数组中的数据分为两个区间, 已排序区间和未排序区间.
需要将数据 a 插入到已排序区间时, 需要拿 a 与已排序区间的元素比较找到合适的插入位置.
- // 插入排序, a 表示数组, n 表示数组大小
- public void insertionSort(int[] a, int n) {
- if (n <= 1) return;
- for (int i = 1; i < n; ++i) {
- int value = a[i];
- int j = i - 1;
- // 查找插入的位置
- for (; j>= 0; --j) {
- if (a[j]> value) {
- a[j+1] = a[j]; // 数据移动
- } else {
- break;
- }
- }
- a[j+1] = value; // 插入数据
- }
- }
插排特点:
原地排序
稳定排序
同冒泡, 最好 O(n), 最坏 O(exp(n)), 平均 O(exp(n)).
选择排序
和插排有点类似, 也区分已排序区间和未排序区间. 选择排序每次会从未排序区间中找到最小的元素, 将其放到已排序区间的末尾.
选择排序特点:
原地排序
不稳定排序
同冒泡, 最好, 最坏, 平均都是 O(exp(n)).
插排比冒泡好的原因
从代码实现上来看, 冒泡排序的数据交换要比插入排序的数据移动要复杂, 冒泡排序需要 3 个赋值操作, 而插入排序只需要 1 个.
冒泡排序中数据的交换操作:
- if (a[j]> a[j+1]) { // 交换
- int tmp = a[j];
- a[j] = a[j+1];
- a[j+1] = tmp;
- flag = true;
- }
插入排序中数据的移动操作:
- if (a[j]> value) {
- a[j+1] = a[j]; // 数据移动
- } else {
- break;
- }
接下来是两种时间复杂度 O (nlogn)的排序算法: 归并排序和快速排序. 这两种适合大规模数据排序, 均用到了分治思想.
分治是一种解决问题的处理思想, 递归是一种编程技巧, 这两者并不冲突.
归并排序
递推公式:
merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))
终止条件:
p>= r 不用再继续分解
(实际上是分解成为单个元素然后有序合并)
伪代码:
- // 归并排序算法, A 是数组, n 表示数组大小
- merge_sort(A, n) {
- merge_sort_c(A, 0, n-1)
- }
- // 递归调用函数
- merge_sort_c(A, p, r) {
- // 递归终止条件
- if p>= r then return
- // 取 p 到 r 之间的中间位置 q
- q = (p+r) / 2
- // 分治递归
- merge_sort_c(A, p, q)
- merge_sort_c(A, q+1, r)
- // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
- merge(A[p...r], A[p...q], A[q+1...r])
- }
其中 merge()函数的伪代码:
- merge(A[p...r], A[p...q], A[q+1...r]) {
- var i := p,j := q+1,k := 0 // 初始化变量 i, j, k
- var tmp := new array[0...r-p] // 申请一个大小跟 A[p...r] 一样的临时数组
- while i<=q AND j<=r do {
- if A[i] <= A[j] {
- tmp[k++] = A[i++] // i++ 等于 i:=i+1
- } else {
- tmp[k++] = A[j++]
- }
- }
- // 判断哪个子数组中有剩余的数据
- var start := i,end := q
- if j<=r then start := j, end:=r
- // 将剩余的数据拷贝到临时数组 tmp
- while start <= end do {
- tmp[k++] = A[start++]
- }
- // 将 tmp 中的数组拷贝回 A[p...r]
- for i:=0 to r-p do {
- A[p+i] = tmp[i]
- }
- }
如果我们定义求解问题 a 的时间是 T (a), 求解问题 b,c 的时间分别是 T (b) 和 T ( c), 那我们就可得到递推关系式:
T(a) = T(b) + T(c) + K
K 是讲子问题 b,c 的结果合并成为问题 a 的结果所消耗的时间.
归并排序特点:
稳定的排序算法
时间复杂度 O (nlogn), 最好最坏平均都是此复杂度.
非原地排序, 空间复杂度 O (n)
快速排序
分区:
原地分区函数伪代码(空间复杂度 O(1)):
- partition(A, p, r) {
- pivot := A[r]
- i := p
- for j := p to r-1 do {
- if A[j] <pivot {
- swap A[i] with A[j]
- i := i+1
- }
- }
- swap A[i] with A[r]
- return i
快排特点:
非稳定排序
可以原地排序
递归实现, 时间复杂度, 最好 O(nlogn), 最坏 O(exp(n))
快排与归并的区别:
归并处理过程是由下到上, 先子问题, 再合并.
快排处理过程是由上到下, 先分区, 再子问题.
O(n)时间复杂度内求无序数组中的第 K 大元素
借鉴快排的分治和分区思想. 递归分区, 然后比较 pivot 的下标 p+1 与 K.
线性排序
接下来三种时间复杂度为 O(n)的排序算法: 桶排序, 计数排序, 基数排序. 因为复杂度是线性的, 所以叫做线性排序. 主要原因是: 不涉及元素间的比较操作.
对排序数据要求比较高, 比如给 100 万用户基于年龄排序.
桶排序
核心思想: 将数据分到几个有序的桶里, 每个桶里的数据再单独进行排序. 桶内排完序之后, 再把每个桶里的数据按照顺序依次取出, 可得有序序列.
数据有 n 个, 均匀划分到 m 个桶内. 每个桶 k=n/m 个元素, 桶内快排 O(k*logk). 桶排序的时间复杂度为
O (n*log (n/m)). 当桶的个数 m 接近数据个数 n 时, log(n/m)就是一个非常小的常量, 桶排序的时间复杂度接近 O(n). 空间复杂度为 O(1).
桶排序比较适合用在外部排序中: 数据比较大, 无法全部加载到内存中.
计数排序
一个理解: 计数排序可以作为桶排序的一种特殊情况
举例说明: 8 个考生, 成绩在 0 到 5 分之间, 放在数组 A[8]中, 分别是: 2,5,3,0,2,3,0,3.
考生的成缋从 0 到 5 分, 我们使用大小为 6 的数组 C[6]表示桶, 其中下标对应分数. 不过, C[6]内存储的并不是考生, 而是对应的考生个数. 像我刚刚举的那个例子, 我们只需要遍历一遍考生分数, 就可以得到 C[6]的值.
从图中可以看出, 分数为 3 的考生有 3 个, 小于 3 分的考生有 4 个, 所以, 成绩为 3 分的考生在排序之后的有序数组 R[8]中, 会保存下标 4,5,6 的位置.
思路如下: 对 C[6]数组顺序求和, C[k]存储小于等于分数 k 的考生个数.
我们从后到前依次扫描数组 A. 比如, 当扫描到 3 时, 我们可以从数组 C 中取出下标为 3 的值 7, 也就是说, 到目前为止, 包括自己在内, 分数小于等于 3 的考生有 7 个, 也就是说 3 是数组 R 中的第 7 个元素 (也就是数组 R 中下标为 6 的位置). 当 3 放入到数组 R 中后, 小于等于 3 的元素就只剩下了 6 个 了, 所以相应的 C[3] 要减 1, 变成 6.
以此类推, 当我们扫描到第 2 个分数为 3 的考生的时候, 就会把它放入数组 R 中的第 6 个元素的位置(也就是下标为 5 的位置). 当我们扫描完整个数组 A 后, 数组 R 内的数据就是按照分数从小到大有序排列的了.
- // 计数排序, a 是数组, n 是数组大小. 假设数组中存储的都是非负整数.
- public void countingSort(int[] a, int n) {
- if (n <= 1) return;
- // 查找数组中数据的范围
- int max = a[0];
- for (int i = 1; i < n; ++i) {
- if (max < a[i]) {
- max = a[i];
- }
- }
- int[] c = new int[max + 1]; // 申请一个计数数组 c, 下标大小 [0,max]
- for (int i = 0; i <= max; ++i) {
- c[i] = 0;
- }
- // 计算每个元素的个数, 放入 c 中
- for (int i = 0; i < n; ++i) {
- c[a[i]]++;
- }
- // 依次累加
- for (int i = 1; i <= max; ++i) {
- c[i] = c[i-1] + c[i];
- }
- // 临时数组 r, 存储排序之后的结果
- int[] r = new int[n];
- // 计算排序的关键步骤, 有点难理解
- for (int i = n - 1; i>= 0; --i) {
- int index = c[a[i]]-1;
- r[index] = a[i];
- c[a[i]]--;
- }
- // 将结果拷贝给 a 数组
- for (int i = 0; i < n; ++i) {
- a[i] = r[i];
- }
- }
计数排序特点:
数据范围不大的场景
只能给非负整数排序, 其他类型要转化为非负整数
只涉及扫描遍历操作, 时间复杂度是 O(n)
基数排序
十万个手机号排序, 桶排序和计数排序不适用.
一个思路: 假设比较 a,b 两个手机号码的大小, 如果前面几位 a 比 b 大, 则后面几位不用看了.
先排最后一位, 然后倒数第二位排序. 这样 11 次排序之后, 手机号码有序.
字符串举例:
这是稳定排序算法思路. 这样, 排序的数据有 k 位, 就需要 k 次桶排序或者计数排序, 总的时间复杂度是 O(k*n).
所以基数排序的时间复杂度近似于 O(n)
实际上有些时候数据不是等长的, 比如单词排序, 有长有短. 可以把所有单词补齐到相同长度, 位数不够的在后面补 0, 根据 ASCII 值, 所有字母大于 "0", 所以不会影响大小顺序.
总结:
基数排序对要排序的数据是有要求的, 需要可以分割出独立的 "位" 来比较, 而且位之间有递进的关系, 如果 a 数据的高位比 b 数据大, 那剰下的低位就不用比较了. 除此之外, 每一位的数据范围不能太大, 要可以用线性排序算法来排序(基数排序需要借助桶排序或者计数排序来完成每一位的排序工作), 否则, 基数排序的时间复杂度就无法做到O(n) 了.
解答开篇: 如何给 100 万用户基于年龄排序. 使用桶排序.
排序优化
常见几种排序算法的比较:
小规模数据可以选择时间复杂度为 O(exp(n))的算法, 如果对大规模数据排序, 时间复杂度 O(nlogn)更高效. 所以, 为了兼顾更多情况, 一般都会选择 O(nlogn)排序算法实现排序.
快速排序优化方式:
三数取中法
从区间的首, 尾, 中间, 分别取一个数, 然后找中间值作为分区点.
随机法
随机选择一个元素作为分区点.
避免递归过深而堆栈过小
限制递归深度, 过线则停止递归.
在堆上模拟实现一个函数调用栈, 没有了系统栈大小的限制.
因为有系数和常数因素, 小规模数据的排序, O(exp(n))的排序算法并不一定比 O(nlogn)排序算法执行的时间长. 所以会选择简单, 不需要递归的插入排序算法.
来源: http://www.bubuko.com/infodetail-3117183.html