基本思想

希爾排序（Shell's Sort），以發(fā)明人命名，又稱為縮小增量排序，也是一種插入排序算法。

主要思想：直接插入排序算法時(shí)間和待排數(shù)據(jù)有關(guān)，其平均復(fù)雜度是O(n^2)，但是在待排數(shù)據(jù)已經(jīng)有序的情況下，其復(fù)雜度可以達(dá)到O(n)，因?yàn)椴恍枰苿?dòng)數(shù)據(jù)。

希爾排序就是利用這種特點(diǎn)，先將整個(gè)待排數(shù)據(jù)記錄分割成若干個(gè)子待排數(shù)據(jù)記錄，然后分別進(jìn)行直接插入排序，當(dāng)整個(gè)待排數(shù)據(jù)記錄“基本有序”時(shí)，再對(duì)整個(gè)數(shù)據(jù)記錄進(jìn)行完整的一次直接插入排序。通俗地來說，先“跳著”給待排序列排序幾個(gè)數(shù)據(jù)，讓待排數(shù)據(jù)基本有序的情況，再直接插入排序。

舉例來說：

例如：給定10個(gè)整數(shù)：(4,3,1,2,6,5,0,9,8,7) 從小到大排序。

第一步：

假定先分成五個(gè)子序列，請(qǐng)注意增量分割，例如第1個(gè)元素和第6個(gè)元素是一個(gè)子序列，第2個(gè)元素和第7個(gè)元素是一個(gè)子序列。最終分成 (4,5)(3,0)(1,9)(2,8)(6,7)，對(duì)子序列分別排序，最終得到結(jié)果：

(4,0,1,2,6,5,3,9,8,7)，調(diào)整了(3,0)的位置。

第二步：

分成三個(gè)子序列，縮小增量，因此第1個(gè)元素和第4個(gè)元素、第7個(gè)元素、第10個(gè)元素是一個(gè)子序列。最終分成(4,2,3,7)(0,6,9)(1,5,8)，同樣對(duì)子序列的數(shù)據(jù)進(jìn)行排序，得到結(jié)果：(2,3,4,7)(0,6,9)(1,5,8)，最終得到：

(2,0,1,3,6,5,4,9,8,7)

第三步：

分成一個(gè)子序列，也就是增量為1，此時(shí)和直接插入排序一樣，對(duì)整個(gè)序列進(jìn)行直接插入排序即可。

算法有效的特征時(shí)：使用增量分割序列時(shí)，有可能會(huì)讓“亂序”的數(shù)據(jù)“跳躍到”前面，這樣不用移動(dòng)位置，從而減少移動(dòng)的次數(shù)。

希爾排序算法時(shí)間復(fù)雜度分析是個(gè)復(fù)雜的難題，其針對(duì)每個(gè)隊(duì)列的所選的增量序列不同，時(shí)間不同。增量序列的值應(yīng)滿足沒有除1以外的公因子，并且最后一個(gè)增量值為1，例如......11,9,5,3,2,1等。

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

希爾排序與直接插入排序相比：

1.需要進(jìn)行多次子排序過程，每次子排序也是直接插入排序。

2.需要一個(gè)增量序列，分割整個(gè)待排序列。

/* #include <stdio.h>// 對(duì)分割每個(gè)子序列進(jìn)行排序 // dk比較子序列增量 void shell_insert(int a[], int length, int dk) {int i,j,t;for(i=dk; i<length; i++){if(a[i] < a[i-dk] ){t = a[i];for(j=i-dk; j>=0 && t < a[j]; j=j-dk)a[j+dk] = a[j];a[j+dk] = t;}} }void shell_insert_sort(int a[], int length, int dk[], int dk_length) {int i;for(i=0; i<dk_length; i++){shell_insert(a, length, dk[i]);} } int main(void) {int a[10] = {4,3,1,2,6,5,0,9,8,7};int dk[3] = {5,3,1};shell_insert_sort(a,10,dk,3);int i;for(i=0; i<10; i++)printf("%d ", a[i]);return 0; }

其實(shí)做為一個(gè)學(xué)習(xí)者，有一個(gè)學(xué)習(xí)的氛圍跟一個(gè)交流圈子特別重要這里我推薦一個(gè)C/C++基礎(chǔ)交流583650410，不管你是小白還是轉(zhuǎn)行人士歡迎入駐，大家一起交流成長(zhǎng)。

總結(jié)

以上是生活随笔為你收集整理的9个元素换6次达到排序序列_C语言必学的12个排序算法：希尔排序（第3篇）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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