希爾排序算法介紹

希爾排序是D.LShell 與1957年提出來的一種排序算法，在這之前排序算法的時間復雜度都是O(n^2),希爾排序算法是突破這個時間復雜度的第一批算法之一。我們知道直接插入排序算法（不知道的請看：排序算法：直接插入排序算法實現及分析），在某些情況下的效率是很很高的，1.當我們的記錄本身就是基本有序（小的關鍵字基本在前面，大的基本在后面）的，我們只需要少量的插入操作，就可以完成排序。2.還有就是記錄數比較少時，直接插入的優勢也是比較明顯的。希爾排序可以說就是直接插入排序的升級版，希爾排序通過構造上面的2個條件 使排序更快的實現。希爾排序是怎樣來構造這2個條件的呢？這里采用跳躍分割的策略：將相距某個“增量”的記錄組成一個子序列，這樣才能保證子序列內分別進行直接插入排序后得到的結果是基本有序而不是局部有序。

希爾排序算法實現

//希爾排序 升序 //根據插入排序的原理，將原來的一個大組，采用間隔的形式分成很多小組，分別進行插入排序 //每一輪結束后 繼續分成更小的組進行 插入排序，直到分成的小組長度為1，說明插入排序完畢 void ShellSort_Up(int* arr,int length) {int increase = length;int i, j, k, temp;do{increase = increase / 3 + 1;//每個小組的長度，也就是增量//每個小組的第0個元素for (i = 0; i < increase; i++){//對每個小組進行插入排序，因為是間隔的形式分組，每個小組的下一個元素為 j+=incresefor (j = i + increase; j < length; j += increase){temp = arr[j];//待插入元素for (k = j - increase; k >= 0 && temp < arr[k]; k -= increase){arr[k + increase] = arr[k];}arr[k + increase] = temp;}}} while (increase>1); }

希爾排序算法復雜度分析

希爾排序的關鍵并不是隨便分組后各自排序，而是將相隔某個“增量”的記錄組成一個字序列，實現跳躍式的移動，使得排序的效率提高。這的“增量”選取就非常關鍵了。我們采用的是increase/3+1的方式選取。可究竟選取一個什么樣的值，最好呢？目前還是數學難題，不過科學研究表明，當增量序列為dlta[k] = 2^（t-k+1） - 1 ，0 <=k<=t<=log2(n+1)時，可以獲得不錯的效率，其時間復雜度為O(n^(3/2))，要好于O(n^2)。

完整代碼

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/timeb.h> #define MAXSIZE 10 //交換值 void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp; } //直接插入排序 升序 void InsertSort_Up(int* arr, int length) {//假定第0個元素是有序表，從第1個元素開始往有序表中插入數據for (int i = 1; i < length; i++){int temp = arr[i];int j;for (j = i - 1; j >= 0 && arr[j] > temp; j--){arr[j + 1] = arr[j];//往前挪}arr[j + 1] = temp;}return; } //希爾排序 升序 //根據插入排序的原理，將原來的一個大組，采用間隔的形式分成很多小組，分別進行插入排序 //每一輪結束后 繼續分成更小的組進行 插入排序，直到分成的小組長度為1，說明插入排序完畢 void ShellSort_Up(int* arr,int length) {int increase = length;int i, j, k, temp;do{increase = increase / 3 + 1;//每個小組的長度//每個小組的第0個元素for (i = 0; i < increase; i++){//對每個小組進行插入排序，因為是間隔的形式分組，每個小組下一個元素為 j+=incresefor (j = i + increase; j < length; j += increase){temp = arr[j];//待插入元素for (k = j - increase; k >= 0 && temp < arr[k]; k -= increase){arr[k + increase] = arr[k];}arr[k + increase] = temp;}}} while (increase>1); } //希爾排序 降序 void ShellSort_Down(int* arr, int length) {int increase = length;int i, j, k, temp;do{increase = increase / 3 + 1;//每個小組的長度//每個小組的第0個元素for (i = 0; i < increase; i++){//對每個小組進行插入排序，因為是間隔的形式分組，每個小組下一個元素為 j+=incresefor (j = i + increase; j < length; j += increase){temp = arr[j];//待插入元素for (k = j - increase; k >= 0 && temp > arr[k]; k -= increase){arr[k + increase] = arr[k];}arr[k + increase] = temp;}}} while (increase>1); }//打印數組元素 void PrintArr(int* arr, int length) {for (int i = 0; i < length; i++){printf("%d ", arr[i]);}printf("\n");return; } long GetSysTime() {struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm; }int main(int argc, char *argv[]) {srand((size_t)time(NULL));//設置隨機種子int arr[MAXSIZE] = { 0 };int arr2[MAXSIZE] = { 0 };//給每個元素設置一個隨機值for (int i = 0; i < MAXSIZE; i++){int num = rand() % MAXSIZE;arr[i] = num;arr2[i] = num;}printf("排序前:\n");PrintArr(arr, MAXSIZE);printf("希爾排序升序:\n");ShellSort_Up(arr, MAXSIZE);PrintArr(arr, MAXSIZE);printf("希爾排序降序:\n");ShellSort_Down(arr, MAXSIZE);PrintArr(arr, MAXSIZE);//long start1 = GetSysTime();//InsertSort_Up(arr, MAXSIZE);//long end1 = GetSysTime();//long start2 = GetSysTime();//ShellSort_Up(arr2, MAXSIZE);//long end2 = GetSysTime();//printf("直接排序%d個數據 耗費時間%d毫秒\n", MAXSIZE, end1 - start1);//printf("希爾排序%d個數據 耗費時間%d毫秒\n", MAXSIZE, end2 - start2);return 0; }

運行結果檢測

希爾排序正確性校驗

直接插入排序和希爾排序比較

測試10萬個數據，直接插入排序和希爾排序的效率

總結

以上是生活随笔為你收集整理的排序算法：希尔排序算法实现及分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。