算法基础-排序方法

比较排序

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

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

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

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

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

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

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

因此可以列出不等式

2^x \geq n! \rightarrow x \geq \ln(n!)

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

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

n! = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 1 \leq n^n

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

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

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

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

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

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

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

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

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