介绍

Bogo 排序（bogo-sort）是个非常低效率的排序算法，通常用在教学或测试。其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。

原理

以下是伪代码：

function bogosort(arr)
  while arr is not ordered
      arr := 隨機排列(arr)

其平均时间复杂度是 O (n × n!)，在最坏情况所需时间是无限。它并非一个稳定的算法。

实现

JavaScript

/**
 * Checks whether the given array is sorted in ascending order.
 */
export function isSorted (array) {
  const length = array.length
  for (let i = 0; i < length - 1; i++) {
    if (array[i] > array[i + 1]) {
      return false
    }
  }
  return true
}

/**
 * Shuffles the given array randomly in place.
 */
function shuffle (array) {
  for (let i = array.length - 1; i; i--) {
    const m = Math.floor(Math.random() * i)
    const n = array[i - 1]
    array[i - 1] = array[m]
    array[m] = n
  }
}

/**
 * Implementation of the bogoSort algorithm.
 *
 * This sorting algorithm randomly rearranges the array until it is sorted.
 *
 * For more information see: https://en.wikipedia.org/wiki/Bogosort
 */
export function bogoSort (items) {
  while (!isSorted(items)) {
    shuffle(items)
  }
  return items
}

参考

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