常见排序算法回顾及总结

从大学时期学习《数据结构与算法》第一次接触排序算法到现在已经过去四年的时间,这周开发任务基本已经完成,利用空闲时间回忆了一下。其中的一些排序算法记得还算牢固,但也有一些略显生疏、不够熟练,所以回顾并总结一下这些常见的排序算法。

常见的排序算法有十种,可以对应的分为两大类:

  • 比较类排序 :通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为 非线性时间比较类排序
  • 非比较类排序 :不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为 线性时间非比较类排序

冒泡排序

遍历数组,依次对比相邻的两个数,如果两个数的顺序错误则交换位置,直到整个序列顺序正确。因为越小(或越大)的元素会通过交换慢慢的 “浮动” 到顶端(或末端)而得名冒泡排序。

算法流程

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数
  3. 针对未排序的元素重复以上的步骤
  4. 重复步骤1~3,直到排序完成

图解

代码实现

function BubbleSort (list) {
  for (let i = list.length; i > 0; i--) {
    let flag = 0
    for (let j = 0; j  list[j + 1]) {
        const temp = list[j]
        list[j] = list[j + 1]
        list[j + 1] = temp
        flag = 1
      }
    }
    if (!flag) break // 一个小优化,如果未发生交换说明已排序完成,可以直接退出
  }
  return list
}

算法性能

选项
时间复杂度(平均) O(n²)
时间复杂度(最坏) O(n²)
时间复杂度(最好) O(n)
空间复杂度 O(1)
稳定性 稳定

插入排序

插入排序是比较符合人类直觉的排序方法,循环遍历数组,每一趟将一个待排序元素插入到有序队列的正确位置中,直到元素全部插入完成

算法流程

  1. 将第一个元素视为有序队列
  2. 取出下一个元素,在有序队列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置构成新的有序队列
  6. 重复 2 ~ 5 直到排序完成

图解

代码实现

function InsertionSort (list) {
  for (let i = 1; i  0; j--) {
      if (curr < list[j - 1]) {
        list[j] = list[j - 1]
      } else {
        list[j] = curr
        break
      }
    }
  }
}

算法性能

选项
时间复杂度(平均) O(n²)
时间复杂度(最坏) O(n²)
时间复杂度(最好) O(n)
空间复杂度 O(1)
稳定性 稳定

特点

插入排序的特点是

  • 队列越小,执行效率越高
  • 队列的排序程度越好,执行效率越高

Google 的 V8 引擎实现的 Array.sort() 方法在数据量小于10时,使用的就是 插入排序

希尔排序

希尔排序于1959年由 Shell 发明,是第一个突破 O(n²) 的排序算法,基于插入排序改进而来,和插入排序的不同之处在于,它会使用间隔序列优先比较距离教员的元素,又叫 缩小增量排序

希尔排序的核心思想是:将记录按照间隔分组,对每组记录采用直接插入排序方法进行排序,然后逐渐缩小间隔排序,直到间隔缩小为1排序后即完成最终排序。

前面我们已经提到, 插入排序 在队列排序程度越好的情况下,执行效率越高,希尔排序就是利用这个特点优化的。

算法发明者 Donald Shell 最初建议采用 n/2, n/4, … , 1 这样的间隔序列,更深入的研究表明(由 Sedgewick 提出),最好的间隔序列为:1, 5, 19, 41, 109, …

算法流程

  1. 选择一个间隔序列 t1,t2,…,tk,其中 ti > tj,tk=1
  2. 按间隔序列个数 k 对序列进行 k 趟排序
  3. 每趟排序,根据间隔 ti 将序列分为若干长度的的子序列,分别对子序列进行 插入排序
  4. 当 tk = 1 时排序完成后,排序结束

图解

代码实现

function ShellSort (list) {
  const n = list.length
  for (let step = Math.floor(n / 2); step > 0; step = Math.floor(step / 2)) {
    for (let i = step; i = 0; j -= step) {
        if (temp < list[j]) {
          list[j + step] = list[j]
        } else {
          beak
        }
      }
      list[j + step] = temp
    }
  }
}

算法性能

选项
时间复杂度(平均) O(nlogn)
时间复杂度(最坏) O(n^1.5)
时间复杂度(最好) O(n)
空间复杂度 O(1)
稳定性 不稳定

选择排序

选择排序是一种非常简单直观的排序算法,循环遍历为排序序列,找出当中最小(或最大)的元素,放在已排序序列的顶端(或末端),直到元素全部排序完成。

算法流程

  1. 初始状态下,无序区为 [1, n], 有序区为空
  2. 第 i (i = 1, 2, …, n – 1)趟遍历开始时,有序区为 [1, i – 1],无序区为 [i, n],从无序区中遍历找到最小值(或最大)x,将它与无序区第一个元素交换,有序区更新为 [1, i],无序区更新为 [i + 1, n]
  3. 重复步骤 2,直到第 n – 1 趟结束

图解

代码实现

function SelectionSort (list) {
  for (let i = 0; i < list.lenght - 1; i++) {
    let min = i
    for (let j = i; j  list[j]) {
        min = j
      }
    }
    const temp = list[min]
    list[min] = list[i]
    list[i] = temp
  }
}

算法性能

选项
时间复杂度(平均) O(n²)
时间复杂度(最坏) O(n²)
时间复杂度(最好) O(n²)
空间复杂度 O(1)
稳定性 不稳定

归并排序

归并排序的核心思想是 分治法(Divide and Conquer) ,递归分割子序列进行归并操作,先使每个子序列有序,再使子序列段间有序。将两个有序表合并成一个有序表,称为二路归并。

算法流程

  1. 将长度为 n 的序列对半分为左右两个子序列
  2. 对两个子序列分别采用归并排序
  3. 将排好序的子序列合并为最终的序列

图解

代码实现

function MergeSort (list) {
  if (list.length < 2) return list
  const middle = Math.floor(list.length / 2)
  const left = list.slice(0, middle)
  const right = list.slice(middle)
  return merge(MergeSort(left), MergeSort(right))
}

function merge (left, right) {
  let result = []
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  if (left.length) {
    result = result.concat(left)
  }
  if (right.length) {
    result = result.concat(right)
  }
  return result
}

算法性能

选项
时间复杂度(平均) O(nlogn)
时间复杂度(最坏) O(nlogn)
时间复杂度(最好) O(nlogn)
空间复杂度 O(n)
稳定性 稳定

快速排序

快速排序也是建立在分治法上,在序列中选择一个元素作为基准,将序列分为比基准小和比基准大的两个子序列,递归对子序列进行相同操作,直到整个序列有序

算法流程

  1. 在序列中选择一个元素作为基准 (pivot)
  2. 对序列进行重排列,比基准小的放在基准前,比基准大的放到基准后
  3. 递归的对前后子序列重复步骤 1~2,直到排序完成

图解

代码实现

function QuickSort (list, left, right) {
  const len = list.length
  if (typeof left !== 'number') left = 0
  if (typeof right !== 'number') right = len - 1
  let pivot
  if (left < right) {
    pivot = partition(list, left, right)
    QuickSort(list, left, pivot - 1)
    QuickSort(list, pivot + 1, right)
  }
  return list
}
function partition (list, left, right) {
  let pivot = list[left]
  while (left < right) {
    while (left = pivot) {
      right--
    }
    list[left] = list[right]
    while (left < right && list[left] <= pivot) {
      left++
    }
    list[right] = list[left]
  }
  list[left] = pivot
  return left
}
function swap (list, i, j) {
  const temp = list[i]
  list[i] = list[j]
  list[j] = temp
}

算法性能

选项
时间复杂度(平均) O(nlogn)
时间复杂度(最坏) O(n²)
时间复杂度(最好) O(nlogn)
空间复杂度 O(nlogn)
稳定性 不稳定

未完待续