目錄
一、常見的排序算法分類
二、常見排序算法的實現?
2.1插入排序
2.1.1基本思想
2.1.2直接插入排序
思路
step1.單趟控制
step2.總體控制?
代碼實現
測試
特性總結
2.1.3 希爾排序( 縮小增量排序 )
基本思想
思路演進
🌈1.代碼實現單組排序（以紅色組為例）
🌈2.加入控制多組排序的代碼
🌈3.對上面代碼修改 ，一組一組排 改為 多組并排！！！
🌈4.最后考慮，如何控制gap?
最終代碼實現
測試
特性總結
三、結語
一、常見的排序算法分類
二、常見排序算法的實現?
2.1插入排序
2.1.1基本思想
直接插入排序是一種簡單的插入排序法，其基本思想是：
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為 止，得到一個新的有序序列 。
?2.1.2直接插入排序
思路
step1.單趟控制
先考慮單趟排序，暫時不考慮區間到底是從哪到哪 ，先抽象為[0,end]
假設[0,end]是有序的區間 a[end+1] 插入到?[0,end]中
?具體如何插入：
下標是end+1的元素依次跟[0,end]區間中的元素作比較：
end+1先跟end比 再跟 end-1比較......依次往下
①如果a[end+1]<a[end] 以排升序為例子 ，那么a[end]就往后挪動 也就是往后覆蓋
②如果a[end+1]>a[end] ,那么就停止比較 ，a[end+1] 插入到?[0,end]中
?思路落實到代碼：
用臨時變量tmp 先保存a[end+1]，最終插入的位置也是a[end+1]
step2.總體控制?
接下來考慮如何控制[0,end]區間大小的變化：
?執行過程描述：
初始時 區間元素個數肯定只有一個，
也就是end =?0 ，區間[0,0]有序，只有一個元素a[0],然后a[1]往里插入，
完成后，end = 1，區間[0,1]有序，有兩個元素，a[2]往里插入...
直到整個數組元素都有序，排序完成。
?思路落實到代碼：
執行過程中，我們發現，end的值是不斷變化的，所以加入外層循環變量i控制即可！
代碼實現
void InsertSort(int* a, int n)
{//外層循環 控制 多趟[0,end]for (int i = 0; i < n-1; i++){//單趟//[0,end] end+1 插入 [0,end]int end = i;int tmp = a[end + 1];while (end >= 0){//升序if (tmp < a[end]){//end 往后覆蓋 end+1a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}測試
特性總結
1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩定的排序算法
4. 穩定性：穩定
?2.1.3 希爾排序( 縮小增量排序 )
基本思想
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：
先選定一個整數gap，把待排序文件中所有記錄分成多個組，所有距離為gap的記錄分在同一組內，并對每一組內的記錄進行排序。然后，再往后依次取 間隔為gap的記錄，重復上述分組和排序的工作。當gap==1時，所有記錄在統一組內排好序。
思路演進
總體思路：
1、預排序：分別對每個分組進行插入排序
2、直接插入排序 ：保證最終結果是有序的
先選定一個整數 ，先假設 gap = 3.? 圖解
🌈1.代碼實現單組排序（以紅色組為例）
🌈2.加入控制多組排序的代碼
總體有gap組 排完紅色組 接著排 藍色組、綠色組 則需要再加入一層循環控制
j==0 紅色組 插入排序
j==1?藍色組 插入排序
j==2?綠色組 插入排序
🌈3.對上面代碼修改 ，一組一組排 改為 多組并排！！！
上面代碼是 ：?紅色組排完 排綠色組? 綠色排完 排藍色組
下面代碼是 ：?紅色組第一個位置排好,
? ? ? ? ? ? ? ? ? ? ? ? i++ 排藍色組第一個位置 ,
? ? ? ? ? ? ? ? ? ? ? ?再 i++ 排綠色組第一個位置，
? ? ? ? ? ? ? ? ? ? ? ?以此類推......
?實現多組并排：
🌈4.最后考慮，如何控制gap?
gap越大：小的值更快調到前面，大的值更快調到后面
gap越小：調得越慢 但 越接近有序
gap==1 ：就是直接插入排序
所以我們再加入一層循環 控制gap
最終代碼實現
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 2 ;for (int i = 0; i < n - gap; i ++){//單趟//[0,end] end+gap 插入 [0,end]int end = i;int tmp = a[end + gap];while (end >= 0){//升序if (tmp < a[end]){//end 往后覆蓋a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}測試
特性總結
1. 希爾排序是對直接插入排序的優化。
2. 當gap > 1時都是預排序，目的是讓數組接近于有序。
? ? 當gap == 1時，數組已經是接近有序，再進行直接插入排序，目的是讓數組有序。
? ? 這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定。平均時間復雜度O（N^1.3）
三、結語
插入排序就先講到這里，后面滴選擇、交換、歸并排序，都會快快更新滴~
)
)
