排序算法——侏儒排序（Gnome sort）【代码实现】

伪代码

function gnomeSort(a[0..size-1])i := 1j := 2while i < size doif a[i-1] <= a[i] then// for descending sort, use >= for comparisoni := jj := j + 1 elseswap a[i-1] and a[i]i := i - 1if i = 0 theni := jj := j + 1endifendifdone

ActionScript

function gnomeSort(array:Array)
{var pos:uint = 0;while(pos < array.length){if(pos == 0 || array[pos] >= array[pos-1])pos++;else{var tmp = array[pos];array[pos] = array[pos-1];array[pos-1] = tmp;pos--;}}return array;
}

C

void gnome_sort(int *a, int n)
{
    int i=1, j=2, t;
# define swap(i, j) { t = a[i]; a[i] = a[j]; a[j] = t; } while(i < n) {
    if (a[i - 1] > a[i]) {
    swap(i - 1, i);if (--i) continue;}i = j++;}
# undef swap
}

C++

#include <algorithm>
#include <iterator>
#include <iostream>template<typename RandomAccessIterator>
void gnome_sort(RandomAccessIterator begin, RandomAccessIterator end) {
    auto i = begin + 1;auto j = begin + 2;while (i < end) {
    if (!(*i < *(i - 1))) {
    i = j;++j;} else {
    std::iter_swap(i - 1, i);--i;if (i == begin) {
    i = j;++j;}}}
}int main() {
    int a[] = {
    100, 2, 56, 200, -52, 3, 99, 33, 177, -199};gnome_sort(std::begin(a), std::end(a));copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));std::cout << "\n";
}

C#

public static void gnomeSort(int[] anArray)
{
    int first = 1;int second = 2;while (first < anArray.Length){
    if (anArray[first - 1] <= anArray[first]){
    first = second;second++;}else{
    int tmp = anArray[first - 1];anArray[first - 1] = anArray[first];anArray[first] = tmp;first -= 1;if (first == 0){
    first = 1;second = 2;}}}
}

Go

package mainimport "fmt"func main() {
    a := []int{
    170, 45, 75, -90, -802, 24, 2, 66}fmt.Println("before:", a)gnomeSort(a)fmt.Println("after: ", a)
}func gnomeSort(a []int) {
    for i, j := 1, 2; i < len(a); {
    if a[i-1] > a[i] {
    a[i-1], a[i] = a[i], a[i-1]i--if i > 0 {
    continue}}i = jj++}
}

Java

public static void gnomeSort(int[] a)
{
    int i=1;int j=2;while(i < a.length) {
    if ( a[i-1] <= a[i] ) {
    i = j; j++;} else {
    int tmp = a[i-1];a[i-1] = a[i];a[i--] = tmp;i = (i==0) ? j++ : i;}}
}

JavaScript

function gnomeSort(a) {
    function moveBack(i) {
    for( ; i > 0 && a[i-1] > a[i]; i--) {
    var t = a[i];a[i] = a[i-1];a[i-1] = t;}}for (var i = 1; i < a.length; i++) {
    if (a[i-1] > a[i]) moveBack(i);}return a;
}

Kotlin

// version 1.1.0fun <T: Comparable<T>> gnomeSort(a: Array<T>, ascending: Boolean = true) {
    var i = 1var j = 2while (i < a.size) if (ascending && (a[i - 1] <= a[i]) ||!ascending && (a[i - 1] >= a[i]))i = j++else {
    val temp = a[i - 1]a[i - 1] = a[i]a[i--] = tempif (i == 0) i = j++}
} fun main(args: Array<String>) {
    val array = arrayOf(100, 2, 56, 200, -52, 3, 99, 33, 177, -199)println("Original : ${
      array.asList()}")gnomeSort(array)println("Sorted (asc) : ${
      array.asList()}")gnomeSort(array, false)println("Sorted (desc) : ${
      array.asList()}")
}

Perl 6

sub gnome_sort (@a) {
    my ($i, $j) = 1, 2;while $i < @a {
    if @a[$i - 1] <= @a[$i] {
    ($i, $j) = $j, $j + 1;}else {
    (@a[$i - 1], @a[$i]) = @a[$i], @a[$i - 1];$i--;($i, $j) = $j, $j + 1 if $i == 0;}}
}

PHP

function gnomeSort($arr){
    $i = 1;$j = 2;while($i < count($arr)){
    if ($arr[$i-1] <= $arr[$i]){
    $i = $j;$j++;}else{
    list($arr[$i],$arr[$i-1]) = array($arr[$i-1],$arr[$i]);$i--;if($i == 0){
    $i = $j;$j++;}}}return $arr;
}
$arr = array(3,1,6,2,9,4,7,8,5);
echo implode(',',gnomeSort($arr));

PowerShell

function gnomesort($a) {
       $size, $i, $j = $a.Count, 1, 2while($i -lt $size) {
    if ($a[$i-1] -le $a[$i]) {
    $i = $j$j++}else {
    $a[$i-1], $a[$i] = $a[$i], $a[$i-1]$i--if($i -eq 0) {
    $i = $j$j++}}}$a
}
$array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11)
"$(gnomesort $array)"

Python

>>> def gnomesort(a):i,j,size = 1,2,len(a)while i < size:if a[i-1] <= a[i]:i,j = j, j+1else:a[i-1],a[i] = a[i],a[i-1]i -= 1if i == 0:i,j = j, j+1return a>>> gnomesort([3,4,2,5,1,6])
[1, 2, 3, 4, 5, 6]
>>>

Ruby

class Arraydef gnomesort!i, j = 1, 2while i < lengthif self[i-1] <= self[i]i, j = j, j+1elseself[i-1], self[i] = self[i], self[i-1]i -= 1if i == 0i, j = j, j+1endendendselfend
end
ary = [7,6,5,9,8,4,3,1,2,0]
ary.gnomesort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

更多代码，持续更新！
整理自网络。