排序算法

First Post:
Last Update:

序言

我们知道排序是算法入门基本功,排序算法有多重要想必也不需要我在这里说明了。因此这一篇就按着我的理解,聊一聊排序算法。

当然我不打算随便弄个什么十大排序算法或是经典排序总结之类响当当的名头,各个算法走马看花一样拉出来遛一遍,最后变得跟网上搜索到的其他讲排序的文章一样换汤不换药。你会发现这篇文章的结构跟在网上搜索到的任何讲排序的文章都有所不同:

在这篇文章里,你会发现你找不到冒泡排序——因为我认为冒泡排序只不过是一种低效率的选择排序。

你会发现堆排序被当成是选择排序的一种优化——因为我认为堆排序主要在于使用了堆这种数据结构,而总体思想与选择排序相比没有太大变化。

你还会找到其他与别的文章不一样的地方。因为这篇文章是我按照自己的理解来写的,我脑子里是这样想的,那文章里就是这样写的。我会按照我的理解,从纵向与横向两个维度,来理清楚各个排序算法的特性与异同。

整篇文章的要点

整篇文章以纵向——算法分类、以及横向——算法评价两个维度来进行组织。

排序算法可以按照以下方式来进行分类:

  • 基于比较的排序算法
    • 基于分治思想
      • 快速排序
      • 归并排序
    • 基于有序区域扩展
      • 插入排序
      • 选择排序
  • 不基于比较的排序算法
    • 计数排序
    • 桶排序
    • 基数排序

文章中还会讲一讲为什么会这么分,每种分类有什么共性,分类之间有什么差异。此外,在最后还会稍微提一提外部排序与适用于并行运算的排序等。

而对于纵向分类中的每一个端点,我们又会从以下五个方面,来对各个算法进行一个总体评价:

  • 时间复杂度(最坏,最好,平均※)
  • 空间复杂度
  • 是否原地排序
  • 是否稳定排序
  • 能否用于链表排序

而由于复杂度主要只关注数量级,因此在这篇文章里会在不影响计算结果的前提下对复杂度计算进行适当的近似与简化。

快排

思想

分治法:先把序列分为小的部分和大的部分,再将两部分分别排序。即:复杂分割,简单合并,主要操作在于分割。

要点

时间复杂度

推导式:T(n) = T(找) + T(左) + T(右) = O(n) + 两个子问题时间复杂度。

  • 最好时间复杂度为每次都正好找到最中间的一个数时时间复杂度为O(nlogn)。证明略。
  • 最坏时间复杂度为每次都正好找到最旁边的数时时间复杂度为O(n^2)。证明略。
  • 平均时间复杂度为O(nlogn),推导式如下:

    快速排序每一步中,将元素分为左右两边需要遍历整个列表,耗时T(n)。假设最后定位的元素为最终第i个元素,则两个子问题复杂度分别为T(i)和T(n-i-1)。

    则有:

    ,即有:

    错位相减:

    其中由于 ,因此

    则有:

额外空间复杂度

考虑栈深度,额外空间复杂度为O(logn)。由于快速排序主要步骤在于分,因此必须自上而下的进行递归,无法避免栈深度。

原地排序

虽然快速排序有额外空间复杂度,但并不妨碍它是一个原地排序。

不稳定

堆排序在分操作时将元素左右交换,会破坏稳定性。

链表形式特点

  • 时间复杂度不变
  • 空间复杂度不变
  • 变为稳定排序※

手写时的易错点

  • 分成左右子序列时最好完全分开(一边用<=一边用>),不然容易造成死循环。
  • 分左右子序列时仔细考虑最初下标位置与最终下标位置,以及对应位置的值的大小。
  • 不要忘记递归的结束条件。

归并排序

思想

分治法:先把两个子序列各自排好序,然后再合并两个子序列。即:简单分割,复杂合并。主要步骤在于合并。

要点

  • 时间复杂度推导式:T(n) = 2T(n/2) + T(合)
  • 平均、最好、最坏时间复杂度都是O(nlogn),推导过程略。
  • 额外空间复杂度为O(n),合并时必须准备额外空间。但由于主要步骤在于合并,可以自下而上地进行迭代合并,可以不使用栈。
  • 非原地排序
  • 稳定排序

链表形式

  • 时间复杂度不变
  • 额外空间复杂度变为O(1)※
  • 稳定排序
  • 只能使用迭代形式,不能使用递归形式

易错点

  • 合并时一边结束时另一边还未结束,需要把那一边也放入合并后序列中
  • 保持稳定排序:合并时左序列等于右序列时也采用左序列
  • 不要忘记递归结束条件
  • 不要忘记循环递进条件

进阶

  • 原地归并排序:时间复杂度为O(log^2n),牺牲合并的时间复杂度进行原地排序。
  • 多路归并排序:使用竞标树,多路归并,用于磁盘IO。

插入排序

思想

有序序列不断扩张,每次从无序序列中取出元素加入有序序列,直至长度为N则完成排序。

每次将无序序列当前元素插入有序序列,复杂度取决于有序序列。

要点

  • 最坏、平均时间复杂度:O(n2)
  • 最好时间复杂度:基本有序情况下,O(n)
  • 额外空间复杂度:O(1)
  • 原地排序
  • 稳定排序
  • 每次插入时都要移动序列,写次数较多
  • 若查找插入位置时使用二分法查找,则可加快时间。(但不足以对时间复杂度造成影响,且最好时间复杂度也会上升为O(nlogn))

链表形式

  • 最好,最坏,平均时间复杂度不变
  • 额外空间复杂度不变
  • 稳定排序
  • 插入时不再需要移动序列,但也不能使用二分法查找

进阶——希尔排序

  • 要点:

    插入排序的优点在于当序列基本有序时,时间复杂度可逼近为O(n)。

    但插入时移动有序序列中元素所耗时间较多,而每次只移动一步。但实际上当序列分布均匀时,有序序列中排靠后的元素在整个序列中也会排靠后。

    可以把序列分为几个大步长序列,在最初的几次插入放开移动步长,让大的元素直接移动到较后位置。再往后慢慢缩小步长,此时序列基本有序,可以利用基本有序时插入排序的优势。

  • 时间复杂度

    1. 当步长为2^i时,不能使时间复杂度缩短为O(nlogn)。因为一个子序列所有元素有可能比另一个子序列最大元素都要大,这时插入排序仍需进行约n^2次操作
    2. 当步长为2^i时效率较低,因为当步长为4已经有序时,步长为2再比较是无用比较。但由于1.的问题,不能节省比较时间。
    3. 当步长之间最小公约数较少,甚至互质时,无用比较次数会降低。
    4. 最坏时间复杂度下限为 (当步长采用 时),但一般希尔排序平均时间复杂度都为
  • 额外空间复杂度O(1)
  • 原地排序
  • 不稳定排序:希尔排序步长较大时会发生前后跳转。
  • 不能写为链表形式

选择排序

思想

有序序列不断扩张,每次从无序序列中取出元素加入有序序列,直至长度为N则完成排序。

每次将选无序序列中最小元素加到有序序列末尾,复杂度取决于无序序列。

要点

  • 最坏、平均时间复杂度:O(n2)
  • 最好时间复杂度:O(n2),如能保证无序部分的最小元素所在位置一定(堆排序),能降低时间复杂度
  • 额外空间复杂度:O(1)
  • 原地排序
  • 不稳定排序(采用元素交换策略时)
  • 每次找到最小元素后,只需交换一次位置即可,写次数较少。
  • 若找到最小元素后,不直接交换而是进行数组移动,则可进行稳定排序,但写次数变多,与插入排序相比没有优势,也不能使用二分查找进行简化。

链表形式

  • 最好,最坏,平均时间复杂度不变
  • 额外空间复杂度不变
  • 变为稳定排序※(因为链表不需要数组移动,稳定排序方式的缺点得以消除)

进阶——堆排序

  • 要点:

    选择排序中耗时最多的是取出无序序列中最小值的时间,需要遍历整个无序序列。

    但实际上我们只关心无序序列中的最小值,而不关心其他值的位置。通过将无序序列建为堆,减少选择时间,降低总的时间复杂度。

  • 时间复杂度O(nlogn)

  • 额外空间复杂度O(1)
  • 原地排序
  • 不稳定排序
  • 操作时间复杂度:每次向下比较关注一个节点与其左右子堆顶元素,每次向上比较只关注节点与其父元素(大顶堆,堆大小为n)

    • 下沉:向下比较,若顶元素不是最大,将顶元素与较大的子堆堆顶元素交换。递归处理该子堆顶元素,直到向下比较顶元素最大。

      最好时间复杂度O(1),最坏时间复杂度为O(h)=O(logn),平均O(logn)

    • 上浮:向上比较,若元素比其上层要大,交换该元素与其上层元素。递归处理其上层元素,直到向上比较不比上层要大。

      最好时间复杂度O(1),最坏时间复杂度O(h)=O(logn),平均O(logn)

    • 入堆:堆扩容一位,将新元素插到尾部,将该元素上浮,最坏、平均时间复杂度O(logn)

    • 出堆:取出堆顶元素,将尾部放到堆顶,将该元素下沉,最坏、平均时间复杂度O(logn)
    • 缺点:通常堆尾元素较小,出堆时将堆尾元素放到堆顶再下沉基本要沉到堆底,无用比较较多
  • 建堆时间复杂度O(n)

    • 策略1:从头开始建堆,逐个元素插入,时间复杂度取决于最后一层,时间复杂度为O(nlogn)

      • 每次将堆扩容一位,将末尾元素上浮。
      • 时间复杂度推导:

        每次插入时间:

        则有总时间:

        即时间复杂度为

    • 策略2:从后开始建堆,小堆合并(逐个元素下沉),时间复杂度为O(n)

      • 每次堆合并时,有三部分:左子堆,右子堆,顶元素。下沉顶元素。
      • 时间复杂度推导:

        第i个元素合并时,时间为:

        则有总时间:

        即时间复杂度为

      • 虽说每步是做一个小堆合并,但实际上从堆尾到堆头遍历,相当于仅关注元素没有稳定,相当于可以直接使用下沉操作。

基于比较的排序算法时间复杂度下限:逆序对思想

基于比较的排序算法可以看作序列逆序对的消除。完全随机序列逆序对数量为O(n^2),若一次元操作只消除一个逆序对,则时间复杂度不会低于O(n^2)。降低时间复杂度关键在于一次消除多个逆序对。

  1. 希尔排序通过增大最初的步长来企图一次消除多个逆序对。
  2. 归并排序消除逆序对最主要在于归并步骤。最后几次合并每个子步骤用O(1)时间消除O(n)个逆序对。
  3. 快速排序消除逆序对最主要在于划分步骤。每个划分步骤用O(n)时间消除O(n)+O(左长度×右长度)个逆序对。
  4. 堆排序逆序对消除方式比较Tricky,但可以看出消除逆序对大致在于出堆步骤,通过O(logn)时间复杂度消除O(n)个逆序对。(左小右大排序时需要建立左大右小的大顶堆,建堆时基本没有消除逆序对)

最后

这篇文章我们主要关注了排序算法中的大头——基于比较的排序算法。在下篇文章,我们再来看一下不基于比较的排序算法,以及外排序与并行排序。