介绍

Gnome 算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。它的平均运行时间是 O (n2)，如果列表已经排序好则只需 O (n) 的运行时间。

原理

伪代码

procedure gnomeSort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1

复杂度

• 平均时间复杂度 $O(n^{2})$
• 最坏时间复杂度 $O(n^{2})$
• 最优时间复杂度 ${\displaystyle \Omega (n)}$
• 空间复杂度 $O(1)$ 辅助空间

实现

JavaScript

/*
 * Gnome sort is a sort algorithm that moving an element to its proper place is accomplished by a series of swap
 * more information: https://en.wikipedia.org/wiki/Gnome_sort
 *
 */
function gnomeSort (items) {
  if (items.length <= 1) {
    return
  }

  let i = 1

  while (i < items.length) {
    if (items[i - 1] <= items[i]) {
      i++
    } else {
      [items[i], items[i - 1]] = [items[i - 1], items[i]]

      i = Math.max(1, i - 1)
    }
  }
  return items
}

参考

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