目錄

引言

什么是侏儒排序（Gnome_sort）？

侏儒排序的排序原理：

演示侏儒排序的過程：

序列最開始的樣子：

第一趟排序：

第二趟排序：

第三趟排序：?

第四趟排序：?

第五趟排序：

第六趟排序：

第七趟排序：

第八趟排序：?

第九趟排序：

代碼實(shí)現(xiàn)：

---

引言

侏儒排序也叫地精排序，是我在一個(gè)算法可視化的視頻里非常巧合的遇到的一個(gè)有趣的算法，我感覺非常有意思，今天在地鐵上聽著歌沒事干，在手機(jī)備忘錄上對(duì)這個(gè)算法進(jìn)行了試數(shù)：???????

排序原理已經(jīng)基本清楚，這個(gè)算法個(gè)人認(rèn)為是一個(gè)介于冒泡排序和插入排序之間的一個(gè)算法，因?yàn)檫@個(gè)算法的最初版本就是冒泡排序再冒回去，結(jié)果比較像插入排序，但是過程卻和冒泡排序十分的相似。當(dāng)我們對(duì)這個(gè)算法進(jìn)行優(yōu)化，最后卻和插入排序幾乎一模一樣。廢話不多說，下面我們對(duì)這個(gè)算法進(jìn)行詳細(xì)的介紹并用代碼實(shí)現(xiàn)。

什么是侏儒排序（Gnome_sort）？

Gnome_sort，是一個(gè)和插入排序算法類似，但是過程又和冒泡排序十分相像的算法，這個(gè)算法和插入排序相似在兩者都是將元素移動(dòng)到合適的位置，并通過一系列交換完成。我覺得這個(gè)算法厲害在整個(gè)算法結(jié)構(gòu)只有一層循環(huán)，在大部分?jǐn)?shù)據(jù)都是有序的情況下，是可以在最大限度減少交換的回合數(shù)的。

侏儒排序的排序原理：

我們定義一個(gè)數(shù)組的指針?i?（i的默認(rèn)值為1）和序列的長度len，通過 i 對(duì)整個(gè)序列進(jìn)行遍歷。i的位置和大小在排序過程中是一直變化的，如果序列中相鄰的元素的大小關(guān)系不符合前小后大的關(guān)系，我們就要對(duì)元素的位置進(jìn)行調(diào)換，并且如果發(fā)生元素的調(diào)換，i就要向后挪一位，也就是（i--）反之如果元素之間沒有發(fā)生調(diào)換，i就要一直往前走，也就是（i++）直到i下標(biāo)不滿足i < len的條件時(shí)，排序已經(jīng)完成，跳出循環(huán)并打印數(shù)組。

演示侏儒排序的過程：

我在這里給一個(gè)隨機(jī)數(shù)組：

int arr[] = {9,7,6,8,5,3,4,1,2,10};

為了更直觀的體現(xiàn)排序過程，我們?cè)诋嫲迳线M(jìn)行演示：

序列最開始的樣子：

第一趟排序：

?

i 的默認(rèn)值為1,我們對(duì)9和7進(jìn)行比較，我們發(fā)現(xiàn)9 > 7不滿足升序序列的條件，所以我們將9和7的位置進(jìn)行調(diào)換，i--此時(shí)i的值為0

第二趟排序：

此時(shí)再次對(duì)比，指針i向后遷移一位到達(dá)7的位置，我們比較指針i所指的元素和它的后一位元素，7 < 9，所以i++，指針此時(shí)指向元素9，我們比較9和6，9 > 6，所以我們調(diào)換元素9和元素6的位置，i--，現(xiàn)在i指向元素7，但是調(diào)換了元素9和元素6之后，6是小于7的，于是我們進(jìn)行第二次調(diào)換，調(diào)換元素6和元素7，i--，再次向后移一位，序列中發(fā)生了兩次調(diào)換，現(xiàn)在i的值為0:

第三趟排序：?

此時(shí)i++，我們發(fā)現(xiàn)i = 1,i = 2，都是滿足條件的，直到i = 3時(shí)我們對(duì)9和8進(jìn)行對(duì)比，已不滿足條件，此時(shí)我們對(duì)元素9和元素8進(jìn)行位置調(diào)換，同時(shí)i的值減1，此時(shí)i指向元素7:

第四趟排序：?

同理，當(dāng)我們的指針i指向元素9時(shí)不滿足條件，我們對(duì)元素9和它后面的元素5進(jìn)行位置調(diào)換，同時(shí)我們發(fā)現(xiàn)5是小于前面每一個(gè)數(shù)的，所以我們將元素5挪到最前面并將所有的值向后遷移一位，那么每發(fā)生一次調(diào)換i的值就減一，所以i的值此時(shí)也變成0:

第五趟排序：

指針i繼續(xù)向后遷移，直到i= 5時(shí)，9和3不滿足規(guī)律，同樣元素3小于前面的每一個(gè)元素，于是我們?cè)俅我徊揭徊降剡M(jìn)行調(diào)換，i的值也隨著調(diào)換次數(shù)的增長而減小，將元素3換到最前面的時(shí)候，i的值也就變?yōu)榱?:

第六趟排序：

?同理，當(dāng)i = 6時(shí)，9和4不再滿足規(guī)律，同時(shí)我們發(fā)現(xiàn)4小于前面除了元素3以外的任何元素，于是我們一步一步地將元素4調(diào)換至元素3的后面，此時(shí)i指向元素3:

第七趟排序：

同上，i = 7時(shí)，9 > 1，我們發(fā)現(xiàn)1小于前面的任何一個(gè)元素，于是我們一步一步的進(jìn)行調(diào)換，直到將元素1放在序列的最前面：此時(shí)i = 0：

第八趟排序：?

同上，i = 8時(shí)，9和2不滿足條件，于是我們將9和2進(jìn)行調(diào)換，2小于前面除了元素1的任何一個(gè)數(shù)，于是我們將2放到1元素的后面，3元素的前面，此時(shí)i指向元素1:

第九趟排序：

我們此時(shí)比較i指向的元素1和它后面的元素2，滿足規(guī)律，i++，比較2和它后面的元素3，滿足規(guī)律，i++，比較3和它后面的元素，滿足規(guī)律，直到i = 9依然滿足規(guī)律，i++，i的值為10，此時(shí)已經(jīng)不滿足i < len的限定條件，說明此時(shí)已經(jīng)序列已經(jīng)排好序，我們此時(shí)跳出循環(huán)，并打印數(shù)據(jù)。

排序過程演示完成，我們下面嘗試用代碼實(shí)現(xiàn)侏儒排序：

代碼實(shí)現(xiàn)：

#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("原始數(shù)據(jù)為：\n");showar(ar,MAXSIZE);printf("\n經(jīng)過侏儒排序后的數(shù)據(jù)為：\n");Gnome_sort(ar,MAXSIZE);showar(ar,MAXSIZE); }

運(yùn)行結(jié)果：

如圖，成功的對(duì)系統(tǒng)隨機(jī)生成的11個(gè)數(shù)進(jìn)行了排序。?

后續(xù)我還會(huì)對(duì)侏儒排序算法的優(yōu)化進(jìn)行補(bǔ)充。

總結(jié)

以上是生活随笔為你收集整理的算法- C语言实现侏儒（地精）排序（Gnome_sort）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。