目錄

插入排序

直接插入排序

希爾排序

希爾排序基本思路解析

希爾排序優(yōu)化思路解析

完整希爾排序文件

---

插入排序

直接插入排序

所謂直接插入排序，即每插入一個(gè)數(shù)據(jù)和之前的數(shù)據(jù)進(jìn)行大小比較，如果較大放置在后面，較小放置在前面，具體思路分析如下：

//以下面的數(shù)組為例
int data[] = { 23,34,84,99,67,26,21,89 };

參考代碼

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>void DirectInsert_sort(int* data, int sz)
{// 遍歷數(shù)組for (int i = 1; i < sz; i++){int tmp = data[i];//獲取數(shù)組的當(dāng)前元素int end = i - 1;//獲取數(shù)組的當(dāng)前元素的上一個(gè)元素//當(dāng)遇到比tmp大數(shù)值時(shí)，挪動數(shù)據(jù)，直到遇到比當(dāng)前數(shù)據(jù)小的數(shù)據(jù)時(shí)跳出循環(huán)while (end >= 0){if (data[end] > tmp){data[end + 1] = data[end];end--;}else{break;}}//在end的后一個(gè)位置插入數(shù)據(jù)，插入完畢后直接更新i和end繼續(xù)比較data[end + 1] = tmp;}
}int main()
{int data[] = { 23,34,84,99,67,26,21,89 };int sz = sizeof(data) / sizeof(int);DirectInsert_sort(data, sz);//打印排序后的數(shù)組for (int i = 0; i < sz; i++){printf("%d ", data[i]);}return 0;
}
輸出結(jié)果：
21 23 26 34 67 84 89 99

通過分析可以得出直接插入排序在最壞的情況下（數(shù)據(jù)為完全逆序的狀態(tài)）時(shí)間復(fù)雜度為O(N2)，而在最好的情況下（已經(jīng)為有序狀態(tài)，只需要遍歷一遍數(shù)據(jù)即可），時(shí)間復(fù)雜度為O(N)

希爾排序

希爾排序基本思路解析

希爾排序的基本思路是將一組數(shù)據(jù)按照間隔值gap分成gap組，對各組進(jìn)行插入排序，這一步被稱作預(yù)排序，接著再使用直接插入排序?qū)φw再進(jìn)行一次排序，具體過程如下

//希爾排序基礎(chǔ)思路
void ShellSort(int* data, int sz)
{int gap = 3;//首先進(jìn)行三組預(yù)排序for (int i = 0; i < gap; i++){//每一組的排序for (int j = gap + i; j < sz; j += gap){int end = j - gap;int tmp = data[j];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end -= gap;}else{break;}}data[end + gap] = tmp;}}//最后進(jìn)行整體插入排序gap = 1;for (int i = gap; i < sz; i += gap){int end = i - 1;int tmp = data[i];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end--;}else{break;}}data[end + gap] = tmp;}
}

希爾排序優(yōu)化思路解析

以上思路只是簡單的分析，接下來對細(xì)節(jié)進(jìn)行分析優(yōu)化，具體思路如下

首先是間隔值gap，gap決定了分組的數(shù)量，也間接決定了最大值走到最后需要的次數(shù)，當(dāng)gap特別大時(shí)，最大值很快就會到數(shù)據(jù)的最末尾，但是同時(shí)整體越不接近需要的升序；相反，當(dāng)gap特別小時(shí)，最大值到數(shù)據(jù)末尾的次數(shù)變多，同時(shí)整體越接近有序，所以gap數(shù)值不容易確定，但是一般取gap為整體的1/3或者取1/2，即gap = size / 3或gap = size / 2 (size是數(shù)組長度)

第二個(gè)問題，如果將預(yù)排序和最后的插入排序分開寫，那么需要寫五個(gè)循環(huán)，三層循環(huán)解決預(yù)排序，兩層循環(huán)解決最后的插入排序，所以可以考慮將預(yù)排序與直接插入排序放在一起，達(dá)到在同一個(gè)循環(huán)中解決問題

可以考慮將每一次循環(huán)變量移動的位置改為移動一位，代替原來的一次移動gap位，如下圖所示

而改進(jìn)后的思路與原來的思路對比：原來的思路是先排一組，排完一組后再排第二組，而改進(jìn)后的思路是遇到i當(dāng)前位置是哪一組的就排哪一組的數(shù)據(jù)，但是需要注意的是，當(dāng)前的tmp所在位置為下一個(gè)相差gap的位置，該位置需要有確切的數(shù)值可以與end進(jìn)行比較，所以tmp不能越界，假設(shè)當(dāng)前tmp為3，數(shù)組最大下標(biāo)為7，也就是tmp所在的下標(biāo)最大只能為7，即i + gap不能超過7，故i最大只能為4，所以i不能超過5

接下來是如何處理預(yù)排序和之后的直接排序放在一起的問題，對于這個(gè)問題，首先就是gap不能為一個(gè)固定值，如果gap為固定的某一個(gè)數(shù)值，例如3，那么預(yù)排序和直接插入排序還是需要兩組循環(huán)才能解決，鑒于gap最后需要回到1，可以考慮從gap/3分組開始，當(dāng)預(yù)排序完gap為3的一組時(shí)，接下來排gap為2的一組，最后著排gap為1的一組，因?yàn)榈谝淮?code>gap為3時(shí)已經(jīng)將數(shù)據(jù)處理了一遍，而gap數(shù)值越小，就會使預(yù)排序的結(jié)果更接近預(yù)期的排序結(jié)果，所以可以考慮gap = gap / 3，每執(zhí)行完一次預(yù)排序就更換一次gap間隔值，從而達(dá)到預(yù)排序與最后的直接插入排序放在一起，因?yàn)楫?dāng)gap為1時(shí)也可以滿足預(yù)排序的思路，故放在一起也不會有任何沖突，只是間隔值從3變成了1,但是需要注意一個(gè)問題，當(dāng)gap小于3時(shí)，gap最后的商為0，導(dǎo)致gap無法取到1，所以需要寫成gap = gap / 3 + 1

//希爾排序優(yōu)化思路
void ShellSort_modified(int* data, int sz)
{int gap = sz;while (gap > 1){gap = gap / 3 + 1;// 此處加1是為了確保最后一個(gè)gap一定為1，因?yàn)樽詈蟮闹苯硬迦肱判蚴钦w各自比較for (int i = 0; i < sz - gap; i++){int end = i;int tmp = data[i + gap];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end -= gap;}else{break;}}data[end + gap] = tmp;}}    
}

完整希爾排序文件

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>//希爾排序優(yōu)化思路
void ShellSort_modified(int* data, int sz)
{int gap = sz;while (gap > 1){gap = gap / 3 + 1;// 此處加1是為了確保最后一個(gè)gap一定為1，因?yàn)樽詈蟮闹苯硬迦肱判蚴钦w各自比較for (int i = 0; i < sz - gap; i++){int end = i;int tmp = data[i + gap];while (end >= 0){if (data[end] > tmp){data[end + gap] = data[end];end -= gap;}else{break;}}data[end + gap] = tmp;}}    
}int main()
{int data[] = { 23,34,84,99,67,26,21,89 };int sz = sizeof(data) / sizeof(int);ShellSort_modified(data, sz);for (int i = 0; i < sz; i++){printf("%d ", data[i]);}return 0;
}
輸出結(jié)果：
21 23 26 34 67 84 89 99

希爾排序總結(jié)：

1. 希爾排序是對直接插入排序的優(yōu)化
2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測試的對比
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)?code>gap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定