目录

引言

什么是侏儒排序（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<stdio.h> #include<iostream> #include<stdlib.h> #include<assert.h> #include<time.h> 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个数进行了排序。 

后续我还会对侏儒排序算法的优化进行补充。

总结

以上是生活随笔为你收集整理的算法- C语言实现侏儒（地精）排序（Gnome_sort）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。