排序算法终极大总结

发表于 | 浏览 次
字数统计: 740 | 阅读时长 ≈ 3

常见的排序算法有以下几种：

  • 递归性排序
    • 归并排序：归并排序的主要思想是分治，也就是先把数组分成两部分，当两部分都有序时，然后再将两部分进行二路归并。需要注意的是归并排序的时间复杂度分析方法，就是画出$T(n) = 2T(n/2) + cn$ 的递归树，并计算最终时间复杂度。但是要注意的是，归并排序在进行二路归并时，可能会产生额外的空间复杂度。
    • ：快速排序的思路也是分治，但分治之前需要选择一个主元作为基准，将主元放在应该在的位置，并且数组左边比主元小，右边比主元大。这样如果当左边有序和右边有序时，整个数组就有序了。假设主元位置为i，快速排序复杂度为$T(n) = T(i) + T(n - i - 1) + cn$ 。由于i的不确定性导致快速排序的最坏情况下时间复杂度为$T(n) = T(n-1) + T(0) + cn = O(n^2)$ ，而平均情况下是$T(n) = 2T(\frac{n-1}{2}) +cn = nlogn$。 快速排序不需要额外的空间。
  • 非递归型排序
    • 插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
    • 选择排序：每次从无序区选择一个最小的放大有序区的最后
    • 冒泡排序：依次比较相邻的两个数据，如果前面的比后面的大，就将其交换；这样交换一轮之后，整个序列中最大的就“沉”到了最后面的位置；重复上述过程，依次把第二大、第三大…的数字放到后面的位置。
    • 希尔排序：分组插入排序
  • 非比较排序：非比较排序的时间复杂度可以达到$O(n)$ 。
    • 计数排序、基数排序、桶排序
      • 计数排序：已知最大值K。利用数组int[K] 统计每个数字的小于等于它的个数，将这个个数作为这个数字的idx
      • 基数排序：分别对数字的个位、十位、…、d位依次进行计数排序
      • 桶排序：将数字分别放入桶里。

因此我们做出如下总结：

排序方法 平均时间复杂度 最坏时间复杂度 空间复杂度 其它要点
归并 $O(nlogn)$ $O(nlogn)$ $O(n)$ 递归树
快排 $O(nlogn)$ $O(n^2)$ $O(1)$ 快速选择【九章算法强化班】两指针
快排优化算法：随机选择pivot
插入、
选择、
冒泡、
希尔		 $O(n^2)$ $O(n^2)$ $O(1)$
计数排序 $O(n)$ $O(n)$ $O(K)$ 已知数组最大值K
基数排序 $O(d(n+10))$ $O(d(n+10))$ $O(10)$
桶排序 $O(n)$ $O(n)$ 大数排序