GnomeSort（侏儒排序）——C语言实现
前言：
这真是我写过最简单的排序了，比冒泡还简单，小小排序有趣有趣。
这个排序在数组基本有序的情况下，时间复杂度可以达到O（n），确实是厉害的，让我们看看怎么写
思路：
基本上，他看着旁边的花盆和前一个花盆; 如果他们按照正确的顺序，他会向前迈出一个底池，否则他会将它们交换掉，并向后踩一个底池（这是百度百科的解释哈哈哈，我觉得很形象）
就是只考虑两个位置的有序，如果有序，下标前进；如果无序，交换两个的位置，并且下标后退。只需要注意的是由于是比较前一个位置，容易下标越界。
既然思路如此简单，直接上代码：
void GnomeSort(int *a,int length) {int i = 1;while (i < length){if (a[i] >= a[i - 1] || i <= 0)i++;else{swap(&a[i], &a[i - 1]);i--;}} }这个算法虽说在最好情况下可以逼近O（n）的时间复杂度，但是在普遍情况下，i的回退其实就相当于第二层的循环，换句话说就是平常的时间复杂度是O（n^2）。而且这是低效的回退，因为每次回退只能回退1，我们当然可以利用一个数组来记录回退的位置（这和KMP算法是不是挺像的），但这样我们为什么不用直接插入排序呢？他有着同样的时间复杂度，并且效率很高。
借用一篇文章中的话：
插入排序遇到不匹配位置的新元素时，把前面的元素挨个后移，然后把新元素直接插入到合适位置（如果位置移动k位，则赋值k+1次）。而侏儒排序是把新元素逐个和前一个元素作交换，一路换位到合适位置，这是典型的冒泡做法（如果位置移动k位，则赋值3*k次）。
原文地址：只有一重循环的排序——侏儒排序（Gnome Sort） - 九德真君 - 博客园 (cnblogs.com)
因此，这个仅仅一重循环的排序算法还是有不少缺陷的，但是这丝毫不妨碍他作为一重循环的排序算法的伟大地位。
我的测试代码：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<time.h> #define N 30//之前写过了，就不再全写一遍了 void generate_random_number(int*, int, int); void swap(int*, int*);void GnomeSort(int *a,int length) {int i = 1;while (i < length){if (a[i] >= a[i - 1] || i <= 0)i++;else{swap(&a[i], &a[i - 1]);i--;}} }int main() {int arr[N + 10] = { 0 };generate_random_number(arr, 0, 1024);GnomeSort(arr,N);printf("排序后数列：\n");for (int i = 0; i < N; i++)printf("%d ", arr[i]);printf("\n");return 0; }测试结果：
至此，GnomeSort（侏儒排序）完成。
总结
以上是生活随笔为你收集整理的GnomeSort（侏儒排序）——C语言实现的全部内容，希望文章能够帮你解决所遇到的问题。
