简版速记

面试速记：十大经典排序算法的复杂度、稳定性与适用场景一览。

复杂度与稳定性速查表

排序	平均时间	最好	最坏	空间	稳定性	类型
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定	比较 / 交换
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	比较 / 选择
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定	比较 / 插入
希尔排序	O(n^1.3)	O(n)	O(n²)	O(1)	不稳定	比较 / 插入
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	比较 / 分治
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定	比较 / 分治
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	比较 / 选择
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	稳定	非比较
桶排序	O(n + k)	O(n)	O(n²)	O(n + k)	稳定	非比较
基数排序	O(n × k)	O(n × k)	O(n × k)	O(n + k)	稳定	非比较

核心结论（背这些）

• 基于比较的排序，时间复杂度下界是 O(n log n)；想突破必须用非比较排序（计数 / 桶 / 基数），但它们对数据范围 / 类型有限制。
• 三个 O(n log n) 主力：归并（稳定、需 O(n) 额外空间）、快排（原地、平均最快、最坏退化 O(n²)、不稳定）、堆排（原地、最坏也是 O(n log n)、不稳定）。
• 「稳定」= 相等元素的相对次序排序后不变。需要稳定就选：冒泡 / 插入 / 归并 / 计数 / 桶 / 基数。
• 小数组（几十个以内）插入排序常数小、对近似有序数据接近 O(n)，工程上常作为分治排序递归到小区间时的兜底。
• 快排最坏 O(n²) 出现在每次基准都取到极值（如已排序数组取首/尾为基准）；随机选基准或三数取中可规避。
• 计数 / 基数排序只能排整数（基数排序还要求非负，原文实现如此）；桶排序依赖映射函数把数据均匀分布。
• 非比较排序里的 k：计数排序是值域大小，基数排序是最大位数，桶排序是桶数量。值域极大时计数排序会很费空间。
• 选择排序无论数据如何都是 O(n²)、且不稳定，实战几乎不用，但「每轮选最值」的思路是堆排的基础。

补充(现代做法)：JS 中 Array.prototype.sort() 才是工程首选。ES2019 起规范要求 sort 稳定（V8、JavaScriptCore 等主流引擎已实现），底层多采用 TimSort（归并 + 插入的混合）或 introsort（快排 + 堆排 + 插入，避免最坏退化）。数字排序务必传比较器 arr.sort((a, b) => a - b)，否则默认按字符串 Unicode 码点排序（[1, 10, 2] 这类会出错）。手写排序基本只在面试 / 教学场景出现。

冒泡排序

通过相邻元素比较和交换，使得每一趟循环都能找到未排序的子数组。

实现

    function bubbleSort(list) {
      var n = list.length
      if(!n) return []
      
      for(var i = 0; i < n; i++) {
        for(var j = 0; j < n - i - 1; j++) {
          if(list[j] > list[j + 1]) {
            var temp = list[j + 1]
            list[j + 1] = list[j]
            list[j] = temp
          }
        }
      }
      return list
    }

优化

单向冒泡

标记在一轮比较过程中，如果没有需要交换的数据，说明数组已经是有序的，可以减少排序循环的次数。

    function bubbleSort(list) {
      var n = list.length
      if(!n) return []
      
      for(var i = 0; i < n; i++) {
        let mark = true // 如果在一轮比较中没有出现需要交换的数据，说明数组已经是有序的
        for(let j = 0; j < n - i - 1; j++) {
          if(list[j] > list[j + 1]) {
            var temp = list[j + 1]
            list[j + 1] = list[j]
            list[j] = temp
            mark = false
          }
        }
        if(mark) break 
      }
      
      return list
    }

双向冒泡

普通冒泡排序一轮只找到最大值或最小值其中之一，双向冒泡则多一轮筛选，既可以找到最大值，也可以找到最小值。

    function bubbleSort(list) {
      var low = 0
      var high = list.length - 1
      while(low < high) {
        var mark = true
        // 找到最大值放在右边
        for(var i = low; i < high; i++) {
          if(list[i] > list[i + 1]) {
            var temp = list[i + 1]
            list[i + 1] = list[i]
            list[i] = temp
            mark = false
          }
        }
        high--
        // 找到最小值放在左边
        for(var j = high; j > low; j--) {
          if(list[j] < list[j - 1]) {
            var temp = list[j - 1]
            list[j - 1] = list[j]
            list[j] = temp
            mark = false
          }
        }
        low++
        if(mark) break
      }
      return list
    }

选择排序

依次找到剩余元素的最小值或者最大值，放置末尾或者开头。

实现

    function selectSort(list) {
      var n = list.length
      var minIndex
      
      for(var i = 0; i < n - 1; i++) {
        minIndex = i
        for(var j = i + 1; j < n; j++) {
          if(list[j] < list[minIndex]) {
            minIndex = j
          }
        }
        var temp = list[i]
        list[i] = list[minIndex]
        list[minIndex] = temp
      }
      return list
    }

插入排序

以第一个元素为有序数组，其后的元素通过在这个已有序的数组中找到合适的元素并插入。

实现

    function insertSort(list) {
      var n = list.length
      var preIndex
      var current
      
      for(var i = 1; i < n; i++) {
        preIndex = i - 1
        current = list[i]
        
        while(preIndex >=0 && list[preIndex] > current) {
          list[preIndex + 1] = list[preIndex]
          preIndex--
        }
        list[preIndex + 1] = current
      }
      return list
    }

优化

拆半插入

    function insertSort(list) {
      var low
      var high
      var j
      var temp
      for (var i = 1; i < list.length; i++) {
        if (list[i] < list[i - 1]) {
          temp = list[i]
          low = 0
          high = i - 1
          while (low <= high) {
            let mid = Math.floor((low + high) / 2)
            if (temp > list[mid]) {
              low = mid + 1
            } else {
              high = mid - 1
            }
          }
          for (j = i; j > low; --j) {
            list[j] = list[j - 1]
          }
          list[j] = temp
        }
      }
      return list
    }

希尔排序

通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap。

    function shellSort(list) {
      var n = list.length
      var gap = parseInt(n / 2) // 初始化步数
      while(gap) { // 逐步缩小步数
        for(var i = gap; i < n; i++) {
          // 逐步和前面其他成员比较交换
          for(var j = i - gap; j >=0; j -= gap) {
            if(list[j] > list[j + gap]) {
              var temp = list[j + gap]
              list[j + gap] = list[j]
              list[j] = temp
            } else {
              break
            }
          }
        }
        gap = parseInt(gap / 2)
      }
    }

归并排序

递归将数组分成两个序列，有序合并这两个序列。作为一种典型的分治法思想算法应用，归并排序的实现有两种方法：

• 自上而下的递归
• 自下而上的迭代

    function mergeSort(list) {
      var n = list.length
      if(n < 2) return list
      
      var mid = Math.floor(n / 2)
      var left = list.slice(0, mid)
      var right = list.slice(mid)
      
      return merge(mergeSort(left), mergeSort(right))
    }
    
    function merge(left, right) {
      var result = []
      while(left.length && right.length) {
        if(left[0] <= right[0]) {
          result.push(left.shift())
        } else {
          result.push(right.shift())
        }
      }
      while(left.length) {
        result.push(left.shift())
      }
      while(right.length) {
        result.push(right.shift())
      }
      return result
    }

补充(现代做法)：上面的 merge 用 shift() 从数组头部取元素，每次都是 O(n) 移动，整体常数偏大。生产代码更常用双指针 i / j 配合下标读取，避免数组重排：

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

比较时用 <=（而非 <）保证相等元素保持原相对顺序，这正是归并排序「稳定」的关键。

快速排序

选择一个元素作为基数，把比基数小的元素放在它左边，比它大的放在右边（相当于二分），再不断递归基数左右的序列。快速排序是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，它是处理大数据最快的排序算法之一。

实现一

    function quickSort(arr) {
      if (arr.length <= 1) {
        return arr;
      }
      var baseIndex = Math.floor(arr.length / 2); // 向下取整，选取基准点
      var base = arr.splice(baseIndex, 1)[0]; // 取出基准点的值
      // splice 通过删除或替换现有元素或者原地添加新的元素来修改数组，并以数组形式返回被修改的内容。此方法会改变原数组。
      // slice 方法返回一个新的数组对象，不会更改原数组
      // 这里不能直接 base = arr[baseIndex]，因为 base 代表的是每次都删除的那个数
      var left = [];
      var right = [];
      for (var i = 0; i < arr.length; i++) {
        // 这里的 length 是变化的，因为 splice 会改变原数组
        if (arr[i] < base) {
          left.push(arr[i]); // 比基准点小的放在左边数组
        } else {
          right.push(arr[i]); // 比基准点大的放在右边数组
        }
      }
      return quickSort(left).concat([base], quickSort(right));
    }

补充(说明 / bug 修复)：原文实现一里 }else{ 写在了 for 循环外面（紧跟在 if 块的右括号之后却又脱离循环体），这是语法/逻辑错误，会导致只有比基准小的元素被收集、比基准大的元素全部丢失。上面已将 else 修正回 for 循环内部，与 if 配对。

实现二

    function quickSort(list, left = 0, right = list.length - 1) {
      var n = list.length
      if(left < right) {
        var index = left - 1
        for(var i = left; i <= right; i++) {
          if(list[i] <= list[right]) {
            index++
            var temp = list[index]
            list[index] = list[i]
            list[i] = temp
          }
        }
        quickSort(list, left, index - 1)
        quickSort(list, index + 1, right)
      }
      
      return list
    }

补充(现代做法)：实现二固定取 list[right] 作为基准，遇到「已经有序」的输入会退化到 O(n²)。工程上常用「随机基准」或「三数取中」（取首、中、尾的中位数）来规避最坏情况；数据量大时还会在递归到小区间时切换为插入排序，这正是 introsort / TimSort 的思路。

堆排序

说到堆排序，首先需要了解一种数据结构--堆。堆是一种完全二叉树，这种结构通常可以用数组表示。在实际应用中，堆又可以分为最小堆和最大堆，两者区别如下：

• -max-heap property：对于所有除了根节点的节点i，A[Parent(i)] >= A[i]
• -min-heap property：对于除了根节点的节点i，A[Parent(i)] <= A[i]

堆排序可以说是一种利用堆的概念来排序的选择排序，分为两种方法：

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排序；
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排序。

实现

    function heapSort(nums) {
      buildHeap(nums)
      // 循环 n-1 次，每次循环后交换堆顶元素和堆底元素并重新调整堆结构
      for(var i = nums.length - 1; i > 0; i--) {
        [nums[i], nums[0]] = [nums[0], nums[i]]
        adjustHeap(nums, 0, i)
      }
      return nums
    }
    
    function buildHeap(nums) {
      // 注意这里的头节点是从0开始的，所以最后一个非叶子节点结果是 parseInt(nums.length / 2) - 1
      var start = parseInt(nums.length / 2) - 1
      var size = nums.length
      // 从最后一个非叶子节点开始调整，直至堆顶
      for(var i = start; i >= 0; i--) {
        adjustHeap(nums, i, size)
      }
    }
    
    function adjustHeap(nums, index, size) {
      // 交换后可能会破坏堆结构，需要循环使得每一个父节点都大于左右节点
      while(true) {
        var max = index
        var left = index * 2 + 1 // 左节点
        var right = index * 2 + 2 // 右节点
        if(left < size && nums[max] < nums[left]) max = left
        if(right < size && nums[max] < nums[right]) max = right
        // 如果左右节点大于当前节点则交换，并再循环一遍判断交换后是否破坏堆结构
        if(index !== max) {
          [nums[index], nums[max]] = [nums[max], nums[index]]
          index = max
        } else {
          break
        }
      }
    }

补充(bug 修复)：原文 heapSort 形参叫 list，函数体里却用了未声明的 nums，调用时会因变量不一致出错；同时返回的也应是被原地排序的数组本身。上面已统一成 nums。另外把注释里的「大雨当前节点」改为「大于当前节点」。

计数排序

以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。因为 JS 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但是不可以排列小数。

注：原文这句「可以排列负数」需谨慎理解——下面的实现以元素值直接作为数组下标，负数会落到负索引上，依赖 min/max 区间遍历才能还原，工程上通常做 值 - min 的偏移处理更稳妥。

实现

    function countingSort(nums) {
      var list = []
      var max = Math.max(...nums)
      var min = Math.min(...nums)
      
      for(var i = 0; i < nums.length; i++) {
        var temp = nums[i]
        list[temp] = list[temp] + 1 || 1
      }
      
      var index = 0
      for(var i = min; i <= max; i++) {
        while(list[i] > 0) {
          nums[index++] = i
          list[i]--
        }
      }
      
      return nums
    }

补充(bug 修复)：原文 countingSort 最后 return list 返回的是计数用的临时数组（里面是各值的出现次数），而真正排好序的是被原地写回的 nums。上面已改为 return nums。

桶排序

取 n 个桶，根据数组的最大值和最小值确认每个桶存放的数的区间，将元素插入到相应的桶里，最后再合并各个桶。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。 为了使桶排序更加高效，我们需要做到这两点：

• 在额外空间充足的情况下，尽量增大桶的数量。
• 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中。

    function bucketSort(nums) {
      // 桶的个数，只要是正数都行
      var num = 5
      var max = Math.max(...nums)
      var min = Math.min(...nums)
      // 计算每个桶存放的数值范围，至少为 1
      var range = Math.ceil((max - min) / num) || 1
      // 创建二维数组，第一维表示第几个桶，第二维表示桶里放的数
      var arr = Array.from(Array(num)).map(() => Array().fill(0))
      nums.forEach(val => {
        // 计算元素应该分布在哪个桶
        let index = parseInt((val - min) / range);
        // 防止 index 越界，例如当 [5,1,1,2,0,0] 时 index 会出现 5
        index = index >= num ? num - 1 : index;
        let temp = arr[index];
        // 插入排序，将元素有序插入到桶中
        let j = temp.length - 1;
        while (j >= 0 && val < temp[j]) {
          temp[j + 1] = temp[j];
          j--;
        }
        temp[j + 1] = val;
      });
      // 修改回原数组
      var res = [].concat.apply([], arr);
      nums.forEach((val, i) => {
        nums[i] = res[i];
      });
      return nums;
    }

基数排序

使用十个桶 0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环最大值的位数次。但只能排列正整数，因为遇到负号和小数点无法进行比较。

基数排序有两种方法：

• MSD 从高位开始进行排序
• LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶
• 计数排序：每个桶只存储单一键值
• 桶排序：每个桶存储一定范围的数值

    function radixSort(nums) {
      // 计算位数
      function getDigits(n) {
        var sum = 0;
        while (n) {
          sum++;
          n = parseInt(n / 10);
        }
        return sum;
      }
      // 第一维表示位数即0-9，第二维表示里面存放的值
      var arr = Array.from(Array(10)).map(() => Array());
      var max = Math.max(...nums);
      var maxDigits = getDigits(max);
      for (var i = 0, len = nums.length; i < len; i++) {
        // 用0把每一个数都填充成相同的位数
        nums[i] = (nums[i] + '').padStart(maxDigits, 0);
        // 先根据个位数把每一个数放到相应的桶里
        var temp = nums[i][nums[i].length - 1];
        arr[temp].push(nums[i]);
      }
      // 循环判断每个位数
      for (var i = maxDigits - 2; i >= 0; i--) {
        // 循环每一个桶
        for (var j = 0; j <= 9; j++) {
          var temp = arr[j]
          var len = temp.length;
          // 根据当前的位数 i 把桶里的数放到相应的桶里
          while (len--) {
            var str = temp[0];
            temp.shift();
            arr[str[i]].push(str);
          }
        }
      }
      // 修改回原数组
      var res = [].concat.apply([], arr);
      nums.forEach((val, index) => {
        nums[index] = +res[index];
      });
      return nums;
    }

阅读全文