算法-排序总结

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

• 递归性排序
  • 算法-归并排序 ：归并排序的主要思想是分治，也就是先把数组分成两部分，当两部分都有序时，然后再将两部分进行二路归并。需要注意的是归并排序的时间复杂度分析方法，就是画出\(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)\)	快速选择 Kth Largest Element 快排优化算法
插入、 选择、 冒泡、 希尔	\(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)\)	大数排序