圖解，C語(yǔ)言希爾排序
希爾排序和插入排序很相似，有點(diǎn)像插入排序的升級(jí)版本。
希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡(jiǎn)單插入排序經(jīng)過改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序，同時(shí)該算法是沖破O(n2）的第一批算法之一。
希爾排序也是一種插入排序算法，只不過在插入排序上突破了結(jié)界，達(dá)到了另一種頂峰的存在，這種頂峰使得時(shí)間復(fù)雜度變成「O(nLogn)~O(n^2)」。
假設(shè)我們需要給下面的數(shù)據(jù)進(jìn)行排序
結(jié)合之前的文章，我們知道兩個(gè)數(shù)據(jù)的插入排序就是比較兩個(gè)數(shù)據(jù)的大小，然后進(jìn)行排列。
希爾排序是通過分組+插入
首先我們排序的數(shù)量是 8 個(gè)，我們需要把數(shù)據(jù)分成 8/2 = 4組。
如下圖
對(duì)上面4組的數(shù)據(jù)進(jìn)行插入排序后得到
然后再繼續(xù)分組 8?2?2 = 2 分成 2組
這兩組數(shù)據(jù)再進(jìn)行插入排序
如下圖
這樣之后，整個(gè)數(shù)據(jù)的排序差不多完成
我們?cè)谶@個(gè)基礎(chǔ)上再對(duì)整個(gè)隊(duì)列執(zhí)行一次插入排序，就會(huì)完成了整個(gè)隊(duì)列的排序，因?yàn)橹耙呀?jīng)對(duì)數(shù)據(jù)進(jìn)行過排序，再進(jìn)行插入排序的時(shí)候，效率會(huì)明顯得到提升。
整個(gè)過程可以觀看動(dòng)態(tài)圖片
代碼實(shí)現(xiàn)看看
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int shell_sort(int arr[],int n)
{
register int i, j, tmp;
int step;
for(step = n/2; step > 0;step /= 2)/*增量步長(zhǎng)*/
{
/*step = 4 2 1*/
for(i = step; i < n; i++)
{
tmp = arr[i];
j = i - step;
for(;j >= 0 && tmp < arr[j];)
{
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = tmp;
}
}
}
#define LENGTH 8
int main( int argc, int *argv[])
{
int i;
int arr[LENGTH] = {6,5,3,1,8,7,2,4};
for(i=0;i<LENGTH;i++)
printf("%d ",arr[i]);printf("\n");
shell_sort(arr,LENGTH);
for(i = 0;i < LENGTH;i++)
printf("%d ", arr[i]);printf("\n");
}
代碼輸出
6 5 3 1 8 7 2 4
1 2 3 4 5 6 7 8
代碼圖片解析
步長(zhǎng)等于4的時(shí)候，先進(jìn)行第一次插入排序
步長(zhǎng)等于2的時(shí)候，先進(jìn)行第二次插入排序
步長(zhǎng)等于1的時(shí)候，先進(jìn)行第三次插入排序
具體過程可以查看插入排序的文章
最后一次進(jìn)行插入排序之后，就會(huì)得到排序完成后的數(shù)列
