介绍

圈排序是一种比较排序算法，它强制将数组分解为圈数，其中每个圈可以旋转以生成排序数组。它在理论上是最优的，它减少了对原始数组的写入次数。

原理

考虑一组 n 个不同的元素。 给出元素 a，可以通过计算小于 a 的元素的数量来计算 a 的索引。

• 如果找到元素处于正确的位置，只需保持原样。
• 否则，通过计算小于 a 的元素总数来找到 a 的正确位置。它必须出现在排序数组中。被替换的另一个元素 b 将被移动到其正确的位置。 这个过程一直持续到在 a 的原始位置得到一个元素。所示过程构成一个循环圈，为列表的每个元素重复此循环。 结果列表将被排序。

复杂度

• Worst-case performance: Θ(n^2)
• Best-case performance: Θ(n^2)
• Average performance: Θ(n^2)
• Worst-case space: Θ(n) total, Θ(1)

实现

JavaScript

/**
 * Cycle sort is an in-place, unstable sorting algorithm,
 * a comparison sort that is theoretically optimal in terms of the total
 * number of writes to the original array, unlike any other in-place sorting
 * algorithm. It is based on the idea that the permutation(置换) to be sorted can
 * be factored into cycles, which can individually be rotated to give a sorted result.
 *
 * Wikipedia: https://en.wikipedia.org/wiki/Cycle_sort
 */

/**
 * cycleSort takes an input array of numbers and returns the array sorted in increasing order.
 *
 * @param {number[]} list An array of numbers to be sorted.
 * @return {number[]} An array of numbers sorted in increasing order.
 */
function cycleSort (list) {
  for (let cycleStart = 0; cycleStart < list.length; cycleStart++) {
    let value = list[cycleStart]
    let position = cycleStart

    // search position
    for (let i = cycleStart + 1; i < list.length; i++) {
      if (list[i] < value) {
        position++
      }
    }
    // if it is the same, continue
    if (position === cycleStart) {
      continue
    }
    while (value === list[position]) {
      position++
    }

    const oldValue = list[position]
    list[position] = value
    value = oldValue

    // rotate the rest
    while (position !== cycleStart) {
      position = cycleStart
      for (let i = cycleStart + 1; i < list.length; i++) {
        if (list[i] < value) {
          position++
        }
      }
      while (value === list[position]) {
        position++
      }
      const oldValueCycle = list[position]
      list[position] = value
      value = oldValueCycle
    }
  }
  return list
}

参考

• Cycle sort - Wikipedia (opens new window)