学步园

1. Gnome排序 是插入排序的变形，唯一的区别在于它是使用类似冒泡排序的Swap方法将选择出来的元素移动到合适的位置。也因此它是Stable的排序算法。
其思想如下：
Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden 
gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are 
in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: 
if there is no previous pot, he steps forwards; if there is no pot next to him, he is done. 

其代码仅五行：

void gnomesort(int n, int ar[]) {
 int i = 0;
 while (i < n) {
  if (i == 0 || ar[i-1] <= ar[i]) i++;
  else {int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
 }
}

时间复杂度为O(n^2)，空间复杂度为O(1)。

2. Comb Sort，梳排序或者梳子排序，就像梳子那样有间隔地比较两个数，很形象，O(n*logn)时间复杂度，O(1)空间复杂度，属于不稳定的排序算法。算法的思想是使逆序的元素尽可能快地移动到最终的位置，而不是像冒泡排序那样每次交换只移动一个位置。

void combsort(int *arr, int size) {
  float shrink_factor = 1.247330950103979;
  int gap = size, swapped = 1, swap, i;
 
  while ((gap > 1) || swapped) {
    if (gap > 1) gap = gap / shrink_factor;
 
    swapped = 0; 
    i = 0;
 
    while ((gap + i) < size) {
      if (arr[i] - arr[i + gap] > 0) {
        swap = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = swap;
        swapped = 1;
      }
      ++i;
    }
  }
}

例

假设输入为

8 4 3 7 6 5 2 1

目标为将之变成递增排序。 因为输入长度=8，开始时设定间距为8÷1.3≒6， 则比较8和2、4和1，并作交换两次。

8 4 3 7 6 5 2 1

2 4 3 7 6 5 8 1

2 1 3 7 6 5 8 4

第二次循环，更新间距为6÷1.3≒4。比较2和6、1和5，直至7和4，此循环中只须交换一次。

2 1 3 7 6 5 8 4

2 1 3 4 6 5 8 7

接下来的每次循环，间距依次递减为3 → 2 → 1，

间距=3时，不须交换

2 1 3 4 6 5 8 7

间距=2时，不须交换

2 1 3 4 6 5 8 7

间距h=1时，交换三次

2 1 3 4 6 5 8 7

1 2 3 4 6 5 8 7

1 2 3 4 5 6 8 7

1 2 3 4 5 6 7 8

上例中，共作了六次交换以完成排序。

#include "ds.h"

#define 	MAX_LENGTH 	8
//#define		GNOMESORT


void print_array(int *a, int n) {  
    int i;  
    for ( i = 0; i < MAX_LENGTH; i++ ) {  
        printf("%d ", a[i]);  
    }  
    printf("\n");  
}  


void gnomesort(int ar[],int n) {
 int i = 0;
 while (i < n) {
  if (i == 0 || ar[i-1] <= ar[i]) i++;
  else {int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
 }
}

void combsort(int *arr, int size) {
 
  float shrink_factor = 1.247330950103979;
  int gap = size, swapped = 1, swap, i;
 
  while ((gap > 1) || swapped) {
    if (gap > 1) gap = gap / shrink_factor;
 
    swapped = 0; 
    i = 0;
 
    while ((gap + i) < size) {
      if (arr[i] - arr[i + gap] > 0) {
        swap = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = swap;
        swapped = 1;
      }
      ++i;
    }
  }
}

int main(void) {  
int a[MAX_LENGTH] = {8, 4, 3, 7, 6, 5, 2, 1};
    printf("before sorting:\n");  
    print_array(a, MAX_LENGTH);
#ifdef GNOMESORT
	gnomesort(a, MAX_LENGTH);
#else
    combsort(a, MAX_LENGTH);  
#endif
   	printf("after sorting:\n");  
    print_array(a, MAX_LENGTH);  
    return 0;  
}