數(shù)據(jù)結(jié)構(gòu)與算法篇-希爾排序
01
—
希爾排序算法思想
希爾排序也是一種插入排序，是簡(jiǎn)單插入排序改進(jìn)后的一個(gè)更高效版本，同時(shí)也是首批突破O(n^2)算法之一。
希爾排序算法思想：希爾排序是按照下標(biāo)增量進(jìn)行分組，對(duì)每組使用插入排序算法進(jìn)行排序，隨著增量減少，每組包含的關(guān)鍵字越來(lái)越多，增量減到1時(shí)，整個(gè)序列被分為一組，算法終止。
增量gap = 4分組圖
增量gap = 4排序結(jié)果圖
增量gap = 2排序結(jié)果圖
增量gap = 1分組圖
增量gap = 1排序結(jié)果圖
—
希爾排序算法實(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)在寫(xiě)一個(gè)小程序驗(yàn)證算法的正確性，代碼如下：
#include <stdio.h>
#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算法完全正確！
評(píng)論
圖片
表情