希爾排序，或稱為縮小增量排序。它通過多次直接插入排序來提高算法的效率，時間復(fù)雜度約為O()，空間復(fù)雜度為o（1）。

下面是進行升序排序的完整示例：

增量用數(shù)組dk來表示，依次通過增量5，3，1對數(shù)據(jù)進行直接插入排序，3次之后原數(shù)據(jù)便排好序了。其中insertSort函數(shù)是對直接插入排序算法的簡單修改，供shellSort函數(shù)進行調(diào)用，整體結(jié)構(gòu)一目了然。關(guān)于增量如何取值可以自行百度。

希爾排序是不穩(wěn)定的，這與所取的增量有關(guān)。如 1，3，3，2四個數(shù)，取增量為2，排完序之后為1，2，3，3。再取增量為1，排序結(jié)果為1，2，3，3。所以希爾排序是不穩(wěn)定的。

#include<iostream>void insertSort(int* arr, int num,int d);void shellSort(int* arr, int num,int* dk,int n);//希爾排序int main(){int a[20] = { 3, 2, 4, 6, 7, 5, 18, 9, 0, 1,16, 8, 20, 33, 28, 64, 19, 31, 30, 25 };for (int i = 0; i < 20; i++){std::cout << a[i] << " ";}std::cout << '\n';int dk[3] = { 5, 3, 1 };//增量依次取5，3，1。shellSort(a, 20,dk,3);//進行希爾排序for (int i = 0; i < 20; i++){std::cout << a[i] << " ";}return 0;}void shellSort(int* arr, int num, int* dk,int n){for (int i = 0; i < n; i++)insertSort(arr, num, dk[i]);}void insertSort(int* arr, int num, int d){int temp, i, j;//temp保存每一次的新數(shù)，因為數(shù)組元素的移動會覆蓋掉新數(shù)for (i = d; i < num; ++i)//所謂外循環(huán)，每次放一個新數(shù)進去參與排序{if (arr[i] < arr[i - d])//若下標(biāo)i以前的數(shù)不是有序的，執(zhí)行if語句內(nèi)容//此時的無序指的是下標(biāo)0~i-1是有序的，需要將下標(biāo)i中的數(shù)重新插入，使其變得有序{temp = arr[i];//保存每次的新數(shù)for (j = i - d; arr[j] > temp&&j >= 0; j-=d)arr[j + d] = arr[j];arr[j + d] = temp;}}}

?

總結(jié)

以上是生活随笔為你收集整理的插入排序之——希尔排序（c/c++）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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