數(shù)據(jù)結(jié)構(gòu)與算法篇-希爾排序
時(shí)間：2021-09-10 16:31:49
手機(jī)看文章
掃描二維碼
隨時(shí)隨地手機(jī)看文章
[導(dǎo)讀]01—希爾排序算法思想希爾排序也是一種插入排序，是簡(jiǎn)單插入排序改進(jìn)后的一個(gè)更高效版本，同時(shí)也是首批突破O(n^2)算法之一。希爾排序算法思想：希爾排序是按照下標(biāo)增量進(jìn)行分組，對(duì)每組使用插入排序算法進(jìn)行排序，隨著增量減少，每組包含的關(guān)鍵字越來(lái)越多，增量減到1時(shí)，整個(gè)序列被分為一組，...
01—希爾排序算法思想
希爾排序也是一種插入排序，是簡(jiǎn)單插入排序改進(jìn)后的一個(gè)更高效版本，同時(shí)也是首批突破O(n^2)算法之一。希爾排序算法思想：希爾排序是按照下標(biāo)增量進(jìn)行分組，對(duì)每組使用插入排序算法進(jìn)行排序，隨著增量減少，每組包含的關(guān)鍵字越來(lái)越多，增量減到1時(shí)，整個(gè)序列被分為一組，算法終止。我們以增序排序?yàn)槔柵判蚧静襟E：選擇初始增量gap = length / 2，縮小增量繼續(xù)以gap = gap / 2的方式進(jìn)行，直到增量gap = 1為止，增量的每次變化都會(huì)將原始序列劃分為若干組，分別對(duì)每一組進(jìn)行插入排序，每一次通過增量劃分組進(jìn)行插入排序宏觀上小的數(shù)移到了前面，大的數(shù)移到了后面，最后增量gap = 1進(jìn)行插入排序后就是最終的有序序列。本文會(huì)以圖解的方式詳細(xì)介紹希爾排序算法的整個(gè)工作過程。原始序列
增量gap =?4分組圖
增量gap = 4排序結(jié)果圖
增量gap = 2分組圖增量gap = 2排序結(jié)果圖
增量gap = 1分組圖
增量gap = 1排序結(jié)果圖
02—希爾排序算法實(shí)現(xiàn)希爾排序完整源碼如下：
//插入排序
void?insert_sort(int?*arr, int?length, int?start, int?gap){
????if(arr == NULL || length <= 0?|| start < 0?|| gap <= 0){
????????return;
????}
????int?i = 0, j = 0;
????int?value?= 0;
????for(i = start; i < length - gap; i = gap){
????????value?= arr[i gap];
????????for(j = i; j >= start; j -= gap){
????????????if(value?< arr[j]){
????????????????arr[j gap] = arr[j];
????????????}else{
????????????????break;
????????????}
????????}
????????arr[j gap] = value;
????}
}
//希爾排序
void?shell_sort(int?*arr, int?length){
????if(arr == NULL || length <= 0){
????????return;
????}
????int?gap = 0, start = 0;
????int?count = 0;
????for(gap = length / 2; gap > 0; gap /= 2){
????????start = 0;
????????for(count = 0; count < length / gap; count ){
????????????insert_sort(arr, length, start, gap);
????????????start ;
????????}
????}
}現(xiàn)在寫一個(gè)小程序驗(yàn)證算法的正確性，代碼如下：#include?
#include?"shell_sort.h"
int?main()?{
????int?i = 0;
????printf("希爾排序結(jié)果\n");
????int?arr[7] = {8, 23, 64, 12, 0, 5, 6};
????shell_sort(arr, 7);
????for(i = 0; i < 7; i ){
????????printf("%d ", arr[i]);
????}
????printf("\n");
????return?0;
}編譯運(yùn)行輸出如下：
希爾排序結(jié)果
0 5 6 8 12 23 64算法完全正確！
版權(quán)申明：內(nèi)容來(lái)源網(wǎng)絡(luò)，版權(quán)歸原創(chuàng)者所有。除非無(wú)法確認(rèn)，都會(huì)標(biāo)明作者及出處，如有侵權(quán)煩請(qǐng)告知，我們會(huì)立即刪除并致歉。謝謝!
下載文檔
