C語言算法：希爾排序，圖解

時間：2021-07-13 23:55:06

關(guān)鍵字：代碼希爾排序

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]C語言算法圖解

來源：嵌入式linux | 排版：玩轉(zhuǎn)嵌入式
希爾排序和插入排序很相似，有點像插入排序的升級版本。
希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進(jìn)之后的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一。
希爾排序也是一種插入排序算法，只不過在插入排序上突破了結(jié)界，達(dá)到了另一種頂峰的存在，這種頂峰使得時間復(fù)雜度變成「O(nLogn)~O(n^2)」。

假設(shè)，我們需要給下面的數(shù)據(jù)進(jìn)行排序：

結(jié)合之前的文章，我們知道兩個數(shù)據(jù)的插入排序就是比較兩個數(shù)據(jù)的大小，然后進(jìn)行排列。
希爾排序是通過分組插入。
首先，我們排序的數(shù)量是8個，我們需要把數(shù)據(jù)分成8/2=4組，如下圖所示：

對上面4組的數(shù)據(jù)進(jìn)行插入排序后得到：

然后，再繼續(xù)分組8?2?2=2分成2組：

這兩組數(shù)據(jù)再進(jìn)行插入排序，如下圖所示：

這樣之后，整個數(shù)據(jù)的排序就差不多完成了。
我們在這個基礎(chǔ)上再對整個隊列執(zhí)行一次插入排序，就會完成了整個隊列的排序，因為之前已經(jīng)對數(shù)據(jù)進(jìn)行過排序，再進(jìn)行插入排序的時候，效率會明顯得到提升。

整個過程可以觀看動態(tài)圖片：

代碼實現(xiàn)看看：
#include
#include
#include

int shell_sort(int arr[],int n)
{
register int i, j, tmp;
int step;

for(step = n/2; step > 0;step /= 2)/*增量步長*/
{
/*step = 4 2 1*/
for(i = step; i < n; i )
{
tmp = arr[i];
j = i - step;
for(;j >= 0