介绍

梳排序是改良自冒泡排序和快速排序，其要旨在于消除乌龟，亦即在数组尾部的小数值，这些数值是造成冒泡排序缓慢的主因。相对地，兔子，亦即在数组前端的大数值，不影响冒泡排序的性能。

原理

在冒泡排序中，只比较数组中相邻的二项，即比较的二项的间距（Gap）是 1，梳排序提出此间距其实可大于 1，改自插入排序的希尔排序同样提出相同观点。梳排序中，开始时的间距设置为数组长度，并在循环中以固定比率递减，通常递减率设置为 1.3。在一次循环中，梳排序如同冒泡排序一样把数组从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于 1。如果间距递减至 1，梳排序假定输入数组大致排序好，并以冒泡排序作最后检查及修正。

递减率

递减率的设置影响着梳排序的效率，原作者以随机数作实验，得到最有效递减率为 1.3 的。如果此比率太小，则导致一循环中有过多的比较，如果比率太大，则未能有效消除数组中的乌龟。

复杂度

• 平均时间复杂度 ${\displaystyle \Omega (n^{2}/2^{p})}$，其中 p 表示增量。
• 最坏时间复杂度$\Omega (n^{2})$。
• 最优时间复杂度$O(n\log n)$。
• 空间复杂度$O(1)$。

实现

JavaScript

/**
 * Comb sort improves on bubble sort.
 *
 * The basic idea is to eliminate turtles, or small values
 * near the end of the list, since in a bubble sort these slow the sorting
 * down tremendously. Rabbits, large values around the beginning of the list,
 * do not pose a problem in bubble sort.
 *
 * In bubble sort, when any two elements are compared, they always have a
 * gap (distance from each other) of 1. The basic idea of comb sort is
 * that the gap can be much more than 1. The inner loop of bubble sort,
 * which does the actual swap, is modified such that gap between swapped
 * elements goes down (for each iteration of outer loop) in steps of
 * a "shrink factor" k: [ n/k, n/k2, n/k3, ..., 1 ].
 *
 * Wikipedia: https://en.wikipedia.org/wiki/Comb_sort
 */

/**
 * combSort returns an array of numbers sorted in increasing order.
 *
 * @param {number[]} list The array of numbers to sort.
 * @return {number[]} The array of numbers sorted in increasing order.
 */
function combSort (list) {
  if (list.length === 0) {
    return list
  }
  const shrink = 1.3
  let gap = list.length
  let isSwapped = true
  let i = 0

  while (gap > 1 || isSwapped) {
    // Update the gap value for a next comb
    gap = parseInt(parseFloat(gap) / shrink, 10)

    isSwapped = false
    i = 0

    while (gap + i < list.length) {
      if (list[i] > list[i + gap]) {
        [list[i], list[i + gap]] = [list[i + gap], list[i]]
        isSwapped = true
      }
      i += 1
    }
  }
  return list
}

参考

• 梳排序 - 维基百科，自由的百科全书 (opens new window)