跳至主要內容

排序算法

俞文健大约 1 分钟

排序方式时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性
插入排序O(n2)O(n^2)O(n2)O(n^2)O(n)O(n)O(1)O(1)稳定
希尔排序O(n1.3)O(n^{1.3})O(n2)O(n^2)O(n)O(n)O(1)O(1)不稳定
选择排序O(n2)O(n^2)O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)不稳定
堆排序O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog_2n)O(1)O(1)不稳定
冒泡排序O(n2)O(n^2)O(n2)O(n^2)O(n)O(n)O(1)O(1)稳定
快速排序O(nlog2n)O(nlog_2n)O(n2)O(n^2)O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog_2n)不稳定
归并排序O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog_2n)O(n)O(n)稳定
计数排序O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)稳定
桶排序O(n+k)O(n+k)O(n2)O(n^2)O(n)O(n)O(n+k)O(n+k)稳定
基数排序O(nk)O(n*k)O(nk)O(n*k)O(nk)O(n*k)O(n+k)O(n+k)稳定

冒泡排序

TS
ArrayList.prototype.bubbleSort = function () {
  let flag = true
  for (let i = 0; i < this.val.length - 1; i++) {
    for (let j = 1; j < this.val.length - i; j++) {
      if (this.val[j - 1] > this.val[j]) {
        [this.val[j - 1], this.val[j]] = [this.val[j], this.val[j - 1]]
        flag = false
      }
    }
    if (flag) break
  }
}

选择排序

插入排序

快速排序

希尔排序