常见排序算法回顾及总结

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

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

  • 比较类排序:通过比较来决定元素间的相对顺序,由于其时间复杂度不能突破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 < i; j++) {
      if (list[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 < list.length; i++) {
    const curr = list[i]
    for (let j = i; j > 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 < n; i++) {
      const temp = list[i]
      let j
      for (let j = i - step; j >= 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.length; j++) {
      if (min > 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 < right && list[right] >= 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)
稳定性 不稳定

堆排序

总结堆排序之前,我们需要先回顾一下 这种数据结构。

堆是一个可以被看成一颗完全二叉树的数组对象。堆总是满足以下性质:

  • 堆总是一颗完全二叉树
  • 堆中某个节点的值总是不大于(或不小于)其父节点的值

接下来是 堆排序

利用大跟堆(或小跟堆)的特性,每次将堆顶元素和最后一个元素交换后重新构建大跟堆直到排序完成

算法流程

  1. 将待排序序列构建成大跟堆(或小跟堆)[R1, …, Rn],作为初始的无序区
  2. 将堆顶元素 R1 与 最后一个元素 Rn 交换位置,得到新的无序区 [R1, …, Rn-1] 和 新的有序区 [Rn]
  3. 交换后堆顶 R1 可能不符合大跟堆性质,对当前无序区重新调整为新堆
  4. 重复 2 ~ 3 步骤,直到有序区个数为 n - 1,排序完成

图解

堆排序图解

算法实现

function HeapSort (list) {
  buildMaxHeap(list)
  let len = list.length
  for (let i = len - 1; i > 0; i--) {
    swap(list, 0, i)
    len--
    heapify(list, 0, len)
  }
  return list
}

function swap (list, i, j) {
  const a = list[j]
  list[j] = list[i]
  list[i] = a
}

function heapify (list, i, len) {
  let left = 2 * i + 1
  let right = 2 * i + 2
  let root = i
  if (left < len && list[left] > list[root]) {
    root = left
  }
  if (right < len && list[right] > list[root]) {
    root = right
  }
  if (root !== i) {
    swap(list, i, root)
    heapify(list, root, len)
  }
}

function buildMaxHeap (list) {
  for (let i = Math.floor(list.length / 2); i >= 0; i--) {
    heapify(list, i, list.length)
  }
}

算法性能

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

计数排序

计数排序不是基于比较的排序算法,核心思想在于将序列转化为键存储在额外开辟的数组空间中,序列必须是有确定范围的整数

算法流程

  1. 找出序列中的最大和最小值
  2. 统计序列中每个值为 i 的元素出现次数,存入数组 C 的第 i 项
  3. 累加数组 C 得到计数和 count,声明一个大小为 count 的目标数组 R
  4. 遍历数组 C,当元素 C[m] 值为 n 时,向目标数组 R 添加 n 个 m,直到遍历完成

图解

counting-sort

算法实现

// 一般情况下 js 中不需要考虑数组的空间大小
function CountingSort (list) {
  const counting = []
  for (let i = 0; i < list.length; i++) {
        if (!counting[list[i]]) {
      counting[list[i]] = 0
    }
    counting[list[i]]++
  }
  const result = []
  for (let i = 0; i < counting.length; i++) {
    while (counting[i]) {
      result.push(i)
      counting[i]--
    }
  }
  return result
}

算法性能

假设输入的n个值取值范围为 [0, k]

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

算法分析

计数排序有一定的局限性,序列需是一定范围内的正整数,且范围不能太大,否则空间复杂度会很高。在满足条件的情况下,计数排序的速度比任何比较排序都要快,当 k 不大且元素比较集中时,计数排序是个非常适合且高效的排序算法。

桶排序

桶排序是计数排序的优化版,利用函数的映射关系来分配元素到对应的桶中,再分别对桶中的元素进行排序(可能采用其他排序算法,也可以递归采用桶排序),映射函数决定了排序的效率。

算法流程

假设排序的序列取值范围为 [0, 99],我们选定十位数作为桶的映射函数

  1. 声明 0~9 共十个桶
  2. 遍历序列将元素按照十位数放进对应的桶中,保持桶中有序
  3. 遍历十个桶将元素按顺序重新放回序列

图解

桶排序图解

算法实现

function BucketSort (list) {
  const buckets = []
  for (let i = 0; i < list.length; i++) {
    const digit = parseInt(list[i] / 10)
    if (!buckets[digit]) {
      buckets[digit] = []
    }
    insert(buckets[digit], list[i])
  }
  let p = 0
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i]) {
      while (buckets[i].length) {
        list[p++] = buckets[i].shift()
      }
    }
  }
  return list
}
function insert (list, n) {
  let i = list.length
  for (; i > 0; i--) {
    if (list[i - 1] > n) {
      list[i] = list[i - 1]
    } else {
      break
    }
  }
  list[i] = n
}

算法性能

假设使用了 k 个桶

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

基数排序

基数排序,又称 “桶子排序”。依次通过元素与排序相关的特征,将要排序的元素分配到特定的桶中,最终达到排序的目的。

算法流程

以排序整数序列为例

  1. 取得数组中的最大值,新建 0~9 总共 10 个桶
  2. 从最低位开始直到最高位,假设当前位数为 i
  3. 遍历序列,当前元素的 i 位为 n,则分配到 第 n 个桶中
  4. 将桶中元素按顺序重新构成序列
  5. 重复步骤 3~4,直到处理完最高位

图解

radix-sort.gif

算法实现

// 省略获取位数的步骤,直接传参
function RadixSort (list, maxDigit) {
  const counter = []
    for (let digit = 0, mod = 10; digit < maxDigit; digit++, mod *= 10) {
    for (let i = 0; i < list.length; i++) {
      const radix = parseInt((list[i] % mod) / (mod / 10))
      if (!counter[radix]) {
        counter[radix] = []
      }
      counter[radix].push(list[i])
    }
    let p = 0
    for (let i = 0; i < counter.length; i++) {
      if (counter[i]) {
        while (counter[i].length) {
          list[p++] = counter[i].shift()
        }
      }
    }
  }
  return list
}

算法性能

假设桶的数量为k

选项
时间复杂度(平均) O(n * k)
时间复杂度(最坏) O(n * k)
时间复杂度(最好) O(n * k)
空间复杂度 O(n + k)
稳定性 稳定
0%