目录
引言
什么是侏儒排序（Gnome_sort）？
侏儒排序的排序原理：
演示侏儒排序的过程：
序列最开始的样子：
第一趟排序：
第二趟排序：
第三趟排序：
第四趟排序：
第五趟排序：
第六趟排序：
第七趟排序：
第八趟排序：
第九趟排序：
代码实现：
引言
侏儒排序也叫地精排序，是我在一个算法可视化的视频里非常巧合的遇到的一个有趣的算法，我感觉非常有意思，今天在地铁上听着歌没事干，在手机备忘录上对这个算法进行了试数：
排序原理已经基本清楚，这个算法个人认为是一个介于冒泡排序和插入排序之间的一个算法，因为这个算法的最初版本就是冒泡排序再冒回去，结果比较像插入排序，但是过程却和冒泡排序十分的相似。当我们对这个算法进行优化，最后却和插入排序几乎一模一样。废话不多说，下面我们对这个算法进行详细的介绍并用代码实现。
什么是侏儒排序（Gnome_sort）？
Gnome_sort，是一个和插入排序算法类似，但是过程又和冒泡排序十分相像的算法，这个算法和插入排序相似在两者都是将元素移动到合适的位置，并通过一系列交换完成。我觉得这个算法厉害在整个算法结构只有一层循环，在大部分数据都是有序的情况下，是可以在最大限度减少交换的回合数的。
侏儒排序的排序原理：
我们定义一个数组的指针 i （i的默认值为1）和序列的长度len，通过 i 对整个序列进行遍历。i的位置和大小在排序过程中是一直变化的，如果序列中相邻的元素的大小关系不符合前小后大的关系，我们就要对元素的位置进行调换，并且如果发生元素的调换，i就要向后挪一位，也就是（i--）反之如果元素之间没有发生调换，i就要一直往前走，也就是（i++）直到i下标不满足i < len的条件时，排序已经完成，跳出循环并打印数组。
演示侏儒排序的过程：
我在这里给一个随机数组：
int arr[] = {9,7,6,8,5,3,4,1,2,10};
为了更直观的体现排序过程，我们在画板上进行演示：
序列最开始的样子：
第一趟排序：
i 的默认值为1,我们对9和7进行比较，我们发现9 > 7不满足升序序列的条件，所以我们将9和7的位置进行调换，i--此时i的值为0
第二趟排序：
此时再次对比，指针i向后迁移一位到达7的位置，我们比较指针i所指的元素和它的后一位元素，7 < 9，所以i++，指针此时指向元素9，我们比较9和6，9 > 6，所以我们调换元素9和元素6的位置，i--，现在i指向元素7，但是调换了元素9和元素6之后，6是小于7的，于是我们进行第二次调换，调换元素6和元素7，i--，再次向后移一位，序列中发生了两次调换，现在i的值为0:
第三趟排序：
此时i++，我们发现i = 1,i = 2，都是满足条件的，直到i = 3时我们对9和8进行对比，已不满足条件，此时我们对元素9和元素8进行位置调换，同时i的值减1，此时i指向元素7:
第四趟排序：
同理，当我们的指针i指向元素9时不满足条件，我们对元素9和它后面的元素5进行位置调换，同时我们发现5是小于前面每一个数的，所以我们将元素5挪到最前面并将所有的值向后迁移一位，那么每发生一次调换i的值就减一，所以i的值此时也变成0:
第五趟排序：
指针i继续向后迁移，直到i= 5时，9和3不满足规律，同样元素3小于前面的每一个元素，于是我们再次一步一步地进行调换，i的值也随着调换次数的增长而减小，将元素3换到最前面的时候，i的值也就变为了0:
第六趟排序：
同理，当i = 6时，9和4不再满足规律，同时我们发现4小于前面除了元素3以外的任何元素，于是我们一步一步地将元素4调换至元素3的后面，此时i指向元素3:
第七趟排序：
同上，i = 7时，9 > 1，我们发现1小于前面的任何一个元素，于是我们一步一步的进行调换，直到将元素1放在序列的最前面：此时i = 0：
第八趟排序：
同上，i = 8时，9和2不满足条件，于是我们将9和2进行调换，2小于前面除了元素1的任何一个数，于是我们将2放到1元素的后面，3元素的前面，此时i指向元素1:
第九趟排序：
我们此时比较i指向的元素1和它后面的元素2，满足规律，i++，比较2和它后面的元素3，满足规律，i++，比较3和它后面的元素，满足规律，直到i = 9依然满足规律，i++，i的值为10，此时已经不满足i < len的限定条件，说明此时已经序列已经排好序，我们此时跳出循环，并打印数据。
排序过程演示完成，我们下面尝试用代码实现侏儒排序：
代码实现：
#define MAXSIZE 11
#include
#include
#include
#include
#include
void initar(int *ar,int len)
{
assert(ar != nullptr);
for(int i = 0;i < len;i++){
ar[i] = rand() % 30;
}
}
void showar(int *ar,int len)
{
assert(ar != nullptr);
for(int i = 0;i < len;i++){
printf("%d ",ar[i]);
}
printf("n--------------------------n");
}
void swap(int *ar,int index1,int index2)
{
int temp = ar[index1];
ar[index1] = ar[index2];
ar[index2] = temp;
}
void Gnome_sort(int *ar,int len)//侏儒排序算法
{
assert(ar != nullptr && len >= 0);
int i = 0;
while(i < len){
if(i == 0 || ar[i - 1] <= ar[i])
i++;
else{
swap(ar,i,i - 1);
i--;
}
}
}
int main()
{
srand((unsigned int)time(NULL));
int ar[MAXSIZE];
initar(ar,MAXSIZE);
printf("原始数据为：n");
showar(ar,MAXSIZE);
printf("n经过侏儒排序后的数据为：n");
Gnome_sort(ar,MAXSIZE);
showar(ar,MAXSIZE);
}
运行结果：
如图，成功的对系统随机生成的11个数进行了排序。
后续我还会对侏儒排序算法的优化进行补充。
