算法导论知识梳理(二):比较排序算法及其下限

2,969 阅读9分钟

排序算法简介

常见的排序算法大概有十种,而这些排序算法大致可以分为两类:基于比较的排序算法和非基于比较的排序算法。基于比较的排序算法包括:冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序、快速排序;非基于比较的排序包括:计数排序、基数排序、桶排序。本文主要介绍基于比较的排序算法中的一部分,包括:冒泡排序、选择排序、插入排序、归并排序和快速排序。前三个主要是提供算法优化的思路,后二个主要是为了巩固分治法这一思想。同时在最后也会介绍为什么基于比较的排序算法在最坏情况下,时间复杂度最快也只能达到O(nlogn)。

交换函数

首先先写一个通用的交换函数,用在下面的这些算法中

function exchange(arr, i, j) {
  const tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp; 
}

优化算法:冒泡排序、选择排序、插入排序

这三个排序因为比较简单,也都是比较容易想到的,所以并不打算写,相信大家应该也都是知道的怎么写的。这三种排序都是不需要另外开辟一块跟n相关的内存空间用以存储排序过程中的变量,即不占用额外内存或只占用常数内存。另一方面,这三种排序算法也都有改进空间。下面主要讲的就是这些算法的优化算法,主要是为了提供一些算法优化的思路。

优化的冒泡排序

通过引入一个标志位isExchange,对上一轮冒泡的结果进行校验,如果上一轮没发生冒泡,则说明结果已经是有序的,即可提前退出循环。

function BubbleSort(arr) {
  let isExchange = false;
  for(let i = 0; i < arr.length; i++) {
    isExchange = false;
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[i] > arr[j]) {
        exchange(arr, i, j);
        isExchange = true;
      }
    }
    // 若上一轮未交换位置,则提前退出循环
    if(!isExchange) break;
  }
  return arr;
}

优化的选择排序

在每一次循环中,相比于原来的每次只找一个最大或最小值,可以通过同时找到最大值和最小值的方式来缩短一半的时间。

function SelectionSort(arr) {
  let maxIndex, minIndex;
  for(let i = 0; i < arr.length / 2; i++) {
    maxIndex = minIndex = i;
    // 找到未排序部分中的最大、最小值
    for(let j = i + 1; j < arr.length - i; j++) {
      if(arr[maxIndex] < arr[j]) maxIndex = j;
      else if(arr[minIndex] > arr[j]) minIndex = j; 
    }
    // 交换未排序部分中的最小值和第一位数
    if(minIndex !== i) {
      exchange(arr, i, minIndex);
      // 如果最大值是i,因为上面这一过程中交换了i和minIndex,所以要修正maxIndex的指向
      if(maxIndex === i) maxIndex = minIndex;
    }
    // 交换未排序部分中的最大值和最后一位数
    if(maxIndex !== arr.length - 1 - i) exchange(arr, arr.length - 1 - i, maxIndex);
  }
  return arr;
}

优化的插入排序

在每次选择插入点时,原来的方法时从头开始匹配,这种方法在数据量大时及其费时,其实可以通过二分查找法选择插入点。

function InsertSort(arr) {
  let maxIndex, minIndex;
  for(let i = 1; i < arr.length; i++) {
    const tmp = arr[i];
    if(tmp < arr[i - 1]) {
      const searchIndex = BinarySearch(arr, 0, i - 1, arr[i]);
      // 将待插入下标之后的项全部右移一单位
      for(let j = i; j > searchIndex; j--) {
        arr[j] = arr[j - 1];
      }
      // 插入待插入项
      arr[searchIndex] = tmp;
    }
  }
  return arr;
}
/**
 * 二分查找
 * lowIndex 查找项的最左侧下标
 * highIndex 查找项的最右侧下标
 * target 待查找的目标项
 * */
function BinarySearch(arr, lowIndex, highIndex, target) {
  while(lowIndex < highIndex) {
    const halfIndex = Math.floor((highIndex + lowIndex) / 2);
    if(arr[halfIndex] > target) {
      highIndex = halfIndex;
    } else {
      lowIndex = halfIndex + 1;
    }
  }
  return lowIndex;
}

总结

以上优化算法都是对原算法的扩展,但是其时间复杂度依旧为O(n2),优化的内容无非就是这两块内容:

  1. 某些特殊情况下的时间复杂度,如:优化的冒泡排序
  2. 其时间复杂度函数T(n)的高阶项的系数或者低阶项,如:另外两个

分治法的应用:归并排序、快速排序

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 --百度百科

归并排序可以分为以下步骤:

  1. 将数组分为2部分,将这两部分进行归并,并将归并结果合并
  2. 合并过程:从前往后分别对比这两部分数组,小项优先于大项插入到新的数组
  3. 重复上诉步骤
function MergeSort(arr) {
  if(arr.length < 2) return arr;
  const midIndex = Math.floor(arr.length / 2);
  const left = MergeSort(arr.slice(0, midIndex));
  const right = MergeSort(arr.slice(midIndex, arr.length));
  return Merge(left, right);
}
function Merge(left, right) {
  let result = [];
  let i = j = 0;
  while(i < left.length && j < right.length) {
    if(left[i] < right[j])
      result.push(left[i++]);
    else
      result.push(right[j++]);
  }
  if(i === left.length) result = result.concat(right.slice(j));
  if(j === right.length) result = result.concat(left.slice(i));
  return result;
}

快速排序

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 --百度百科

快速排序就像它的名字一样,在基于比较的排序算法中,其排序速度是最快的。因为随着数据规模的变大,其时间复杂度是近似线性增长。

快速排序可分为以下步骤:

  1. 随机选取某个数组中的值,一般取位于中间的值
  2. 将小于这个值的数放在左边数组,大于这个值的数放在右边数组
  3. 分别对左边数组和右边数组执行上述操作
function QuickSort(arr) {
  if(arr.length <= 1) return arr;
  const midIndex = Math.floor(arr.length / 2);
  const left = [];
  const right = [];
  for(let i = 0; i < arr.length; i++) {
    if(i === midIndex) continue;

    if(arr[i] < arr[midIndex]) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return QuickSort(left).concat([arr[midIndex]], QuickSort(right));
}

决策树模型

比较排序可以被抽象为一棵决策树,决策树是一棵完全二叉树,它可以表示在给定的输入规模情况下,某一特定排序算法对所有元素的比较操作。其中控制、数据移动等其他操作都被忽略。

见下图:

在决策树中,从根结点到任意一个可达叶结点之间的最长简单路径的长度,表示的是对应的排序算法中最坏情况下的比较次数。因此,一个比较排序算法中的最坏情况比较次数就等于其决策树的高度。

书上这里为什么说的是最坏情况?这是因为只有在最坏情况下,即对任意两个数之间都进行了一次比较操作,比较次数才会是从根结点出发到某一个具体叶结点。然而在大多数情况下,我们为了提升算法性能,会通过类似上面提过的一些优化手段来提前结束比较。

对于一棵每个排列都是可达叶结点的决策树来说,树的高度完全可以被确定。假设一棵这种决策树的高度为h,叶结点总数为l,对应于对n个元素所做的比较排序,那么我们可以轻易得到n! <= l,又因为,对于任意一棵二叉树而言,其叶结点数 l <= 2^h,满二叉树的叶结点数为2^h。

所以得到n! <= l <= 2^h

两边同时取对数,得到 h >= log(n!)

又因为log(n!) = Θ(nlogn)(这是一个定理)

所以能得到h >= Ω(nlogn)

即在最坏的情况下,任何比较排序都需要做Ω(nlogn)次比较。

证明log(n!) = Θ(nlogn)

log(n!) = log1 + log2 + ... + logn <= logn + logn + ... + logn <= nlogn

得到log(n!) = O(nlogn)

然后取n!的后一半,即n/2...n

log(n!) = log1 + log2 + ... + logn >= log(n/2 + 1) + log(n/2 + 2) + ... + log(n - 1) + logn >= log(n/2) + log(n/2) + ... log(n/2) + log(n/2) >= n/2log(n/2)

得到log(n!) = Ω(nlogn)

所以log(n!) = Θ(nlogn)

总结

上诉结论翻译成大白话就是:在基于对任意的两个数都进行过比较的情况下(即不提前结束排序算法,比如优化后的冒泡排序就是提前结束的,这种情况映射到决策树模型上就是取的是从跟节点出发到某一个叶结点之间的路径下的某一段路径,而不是整段路径),任何基于比较的排序,至少都需要进行nlogn次比较。

而从这一定理出发,可以得到:堆排序和归并排序其实是渐进最优的比较排序算法。因为这两者在最好、最坏、平均情况下的时间复杂度都为O(nlogn),即它们的运行时间上界达到了O(nlogn)。而快速排序在最坏情况下,即划分极不平衡的情况下,即用来比较用的中间值刚好是最大/最小值,其就退化为插入排序。但为什么实际情况中往往快排的使用率更高?一、快排可以做到基于原数组进行排序,不产生额外的内存开销;二、快排的高阶项的系数较低,貌似是1.38,有兴趣的可以自己去查查资料。在实际情况下,往往是通过多种排序算法的结合来完成我们所需要的排序算法。例如:js中的sort方法就是对小数组插入排序,对大数组使用快速排序;内省排序是从快排开始,当递归深度超过一定深度后转为堆排序。

本章内容到这里就结束了,下一节内容:基本数据结构。