抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

比较排序

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

渐进时间复杂度

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

在一个长度为 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! 种不同的排列

因此可以列出不等式

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

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

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

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

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

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

线性时间排序

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

计数排序

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

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

数值 次数
3 2
4 1
5 0
6 2
7 2

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

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

基数排序

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

原数组 第一次 第二次 第三次
539 681 539 288
681 642 642 396
865 764 764 539
764 865 865 642
396 396 681 681
288 288 288 764
642 539 396 865

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

评论