算法基础-排序方法

比较排序

顾名思义，比较排序就是通过比较数组里的每个数来排序的算法的统称，经典的比较排序有：冒泡排序，插入排序，快速排序等。它们都是通过逐一比较各个元素，从而得知每个元素应该待的位置。

渐进时间复杂度

为了寻找最佳比较排序算法，我们需要得知比较排序的渐进时间复杂度。但是实际上排序算法通常会受到数组的实际值的影响，因此这里我们先考虑最坏情况。

在一个长度为 n 的数组 A 里，欲得知 A[0] 应该待的位置，就需要知道 A[0] 是第几小的数，如果它是第3小的数字，那么他就应该出现在第3个位置。

只需要知道比较的次数，就能求出算法的时间复杂度。

设总共需要比较 x 次，每次比较可以得到两种不同的可能的排列。

例如数组 [a,b,c]，比较 b 和 c ，则可能对应以下两种排列

• [a,b,c]
• [a,c,b]

所以，根据比较的次数就可以得到所有排列的个数，一次比较会产生 2 个不同的排列，那么 x 次比较就会产生 2^x 个不同的排列。但是我们知道数组的长度为 n ，所以最多只有 n! 种不同的排列

因此可以列出不等式

DearXuan

也就是说，任何基于比较的排序算法，它的时间复杂度至少应该是 O(logn!)

阶乘符号让这个复杂度看起来非常难受，因此我们把阶乘展开

DearXuan

所以比较排序的时间复杂度至少应该是 O(nlogn)

在最坏情况下，堆排序和归并排序的时间复杂度都是O(nlogn)，因此这两种排序方法比起其它比较排序更优

线性时间排序

线性时间排序是指时间复杂度为 O(n) 的排序方法，无论是什么情况，线性时间排序总会比比较排序更快速，但是它们只适用于数值分布较小的情况

计数排序

计数排序先计算每个数字出现的次数，然后再按照大小关系逐一输出。

例如数组 [6,6,3,4,7,7,3]，首先计算出每个数字出现的次数

所以最终结果是 [3,3,4,6,6,7,7]

这种排序方法只需要遍历一次数组就可以得到所有数字出现的次数，最终直接根据次数来输出，但是弊端也非常明显，如果数字范围过大，或者出现小数，那么所列出的表格也会非常大，甚至根本就无法列出表格

基数排序

基数排序可以看成改进版的计数排序。对于范围在0~999以内的整数，先将它们按照个位数排序，然后按照十位数(如果没有就是0)排序，最后再按照百位数排序

每次排序时若遇到相同的数字，则会保持位置不变，等待下一轮排序，因此基数排序是稳定的，但也与计数排序类似，对数值分布的要求很高，对于小数或者字符串，要重新设计分割方法