算法实现/排序/Gnome 排序
void gnome_sort(int *array, int size){
int i, tmp;
for(i=1; i<size; ){
if(array[i-1] <= array[i])
++i;
else{
tmp = array[i];
array[i] = array[i-1];
array[i-1] = tmp;
--i;
if(i == 0)
i = 1;
}
}
}
#include <algorithm> // for std::swap
void gnomeSort( int *array, int size )
{
for ( int i = 1; i < size; ) {
if ( array[i-1] <= array[i] ) {
++i;
}
else {
std::swap( array[i-1], array[i] );
--i;
if ( i == 0 ) {
i = 1;
}
}
}
}
#include <algorithm> // for std::iter_swap
template <typename Iterator>
void gnome_sort(Iterator begin, Iterator end)
{
Iterator current = begin;
Iterator before_current;
while (current != end)
{
if (current == begin || *before_current <= *current)
{
++current;
}
else
{
std::iter_swap(before_current, current);
--current;
}
before_current = current;
--before_current;
}
}
#include <algorithm> // for std::iter_swap
#include <iterator> // for std::advance
template <typename Iterator>
void gnome_sort(Iterator begin, Iterator end)
{
Iterator current = begin;
Iterator before_current;
size_t step = 1;
while (current != end)
{
if (current == begin || *before_current <= *current)
{
std::advance(current, step); // possible leap optimization
step = 1;
}
else
{
std::iter_swap(before_current, current);
--current;
++step;
}
before_current = current;
--before_current;
}
}
优化版本让“侏儒”（这里用 'current' 迭代器表示）跳回右侧，即跳到它在目前最远到达的位置交换花盆的位置。这也避免了冗余比较。平均而言，优化可以使现代 x86 机器上的时间缩短三分之一。（一个明智的侏儒排序？:). 然而，优化在迭代器是随机访问迭代器的情况下效果最佳。否则，算法的工作方式几乎与非优化版本相同 - 尽管它仍然避免了冗余比较。
void GnomeSort( int[] array )
{
for ( int i = 1, temp_value; i < array.Length; )
{
if ( array[i-1] <= array[i] )
i += 1;
else
{
temp_value = array[i-1];
array[i-1] = array[i];
array[i] = temp_value;
i -= 1;
if ( i == 0 )
i = 1;
}
}
}
这是使用 Rust 编码的带有跳跃/跳跃优化的 Gnome 排序的优化版本。
fn skipping_gnome_sort(arr: &mut Vec<i32>)
{
let mut i: usize = 0;
let mut n: usize = arr.len();
let mut prev: usize = 0;
while i < n
{
if i == 0 || arr[i] >= arr[i - 1]
{
if prev != 0 { i += prev; prev = 0; }
i += 1;
}
else
{
arr.swap(i, i - 1);
prev += 1;
i -= 1;
}
}
}
SUBROUTINE gnome_sort(LIST, LENGTH)
INTEGER LIST, LENGTH, I, TEMP
DIMENSION LIST(LENGTH)
I = 2
DO WHILE (I .LE. LENGTH)
IF ((I .EQ. 1) .OR. (LIST(I-1) .LE. LIST(I))) THEN
I = I + 1
ELSE
TEMP = LIST(I)
LIST(I) = LIST(I-1)
LIST(I-1) = TEMP
I = I - 1
IF (I .EQ. 1) THEN
I = 2
END IF
END IF
END DO
END
public class GnomeSort {
static void gnomeSort( int[] theArray ) {
for ( int index = 1; index < theArray.length; ) {
if ( theArray[index - 1] <= theArray[index] ) {
++index;
} else {
int tempVal = theArray[index];
theArray[index] = theArray[index - 1];
theArray[index - 1] = tempVal;
--index;
if ( index == 0 ) {
index = 1;
}
}
}
}
这种 Gnome 排序变体允许排序算法在将 n 放到正确位置后快速恢复排序过程，通过完全跳过已排序的部分，而不是循环遍历它，从而减少了比较次数。
public static int[] jumpingGnomeSort(int[] arr)
{
int n = arr.length;
int i = 0;
int prev = 0;
while (i < n)
{
if (i == 0 || arr[i] >= arr[i - 1])
{
if (prev != 0) { i += prev; prev = 0; }
++i;
}
else
{
int temp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = temp;
++prev; --i;
}
}
return arr;
}
JavaScript
[编辑 | 编辑源代码]function gnomeSort(sortMe) {
i=0;
while (i < sortMe.length) {
if (i==0||sortMe[i-1] <= sortMe[i]) {
i++;
} else {
tmp=sortMe[i];
sortMe[i]=sortMe[i-1];
sortMe[--i]=tmp;
}
}
}
LavishScript
[编辑 | 编辑源代码]这会按变量名传入的范围可访问索引：objectype（IndexName）进行排序，按 MemberName 进行排序，MemberName 应该是 objectype 的数字成员。
method Gnomesort(string IndexName, string MemberName)
{
variable int i = 1
while ${i} <= ${${IndexName}.Used}
{
if ( ${i} == 1 ) || ${${IndexName}[${Math.Calc[${i}-1]}].${MemberName}} <= ${${IndexName}[${i}].${MemberName}}
{
i:Inc
}
else
{
${IndexName}:Swap[${i}, ${Math.Calc[${i}-1]}]
i:Dec
}
}
}
sub gnome_sort(@) {
my @list = @_;
my $size = scalar(@list);
my $right = 1;
while ( $right < $size ) {
my $left = $right - 1;
if ( $list[$left] <= $list[$right] ) {
$right++;
}
else {
@list[ $left, $right ] = @list[ $right, $left ];
$right-- if $right > 1;
}
}
return @list;
}
function gnomeSort(sequence s)
integer i = 1, j = 2
while i<length(s) do
if s[i]<=s[i+1] then
i = j
j += 1
else
{s[i],s[i+1]} = {s[i+1],s[i]}
i -= 1
if i = 0 then
i = j
j += 1
end if
end if
end while
return s
end function
<?php
function gnome_sort($list)
{
for ($i = 1; $i < count($list);)
{
if ($list[$i-1] <= $list[$i]) {$i++;}
else
{
$temp = $list[$i];
$list[$i] = $list[$i-1];
$list[$i-1] = $temp;
$i--;
if ($i == 0) {$i = 1;}
}
}
return $list;
}
?>
def gnomeSort(items):
i = 0
n = len(items)
while i < n:
if i and items[i] < items[i-1]:
items[i], items[i-1] = items[i-1], items[i]
i -= 1
else:
i += 1
return items
def teleportingGnomeSort(items):
i = j = 0
n = len(items)
while i < n:
if i and items[i] < items[i-1]:
items[i], items[i-1] = items[i-1], items[i]
i -= 1
else:
if i < j: # teleport!
i = j
j = i = i+1
return items
module GnomeSort
def self.sort(keys)
sort!(keys.clone)
end
def self.sort!(keys)
i, j = 1, 2
while i < keys.size
if keys[i-1] <= keys[i]
i, j = j, j+1
else
keys[i-1], keys[i] = keys[i], keys[i-1]
i -= 1 if i > 1
end
end
keys
end
end