前情回顧：直接插入排序（對插入排序不熟悉的建議先閱讀此文）
一天，一塵拿著撲克自己在那玩，剛被師傅看見了
首先它把較大的資料集合分割成若干個小組（邏輯上分組），然后對每一個小組分別進行插入排序，此時，插入排序所作用的資料量比較小（每一個小組），插入的效率比較高
可以看出，他是按下標相隔距離為4分的組，也就是說把下標相差4的分到一組，比如這個例子中a[0]與a[4]是一組、a[1]與a[5]是一組...，這里的差值（距離）被稱為增量
每個分組進行插入排序后，各個分組就變成了有序的了（整體不一定有序）
此時，整個陣列變的部分有序了（有序程度可能不是很高）
然后縮小增量為上個增量的一半:2，繼續劃分分組，此時，每個分組元素個數多了，但是，陣列變的部分有序了，插入排序效率同樣比高
同理對每個分組進行排序（插入排序），使其每個分組各自有序
最后設定增量為上一個增量的一半：1，則整個陣列被分為一組，此時，整個陣列已經接近有序了，插入排序效率高
同理，對這僅有的一組資料進行排序，排序完成
隨后一塵寫出了插入arr[i]到所在組正確位置的代碼（insertI）
希爾排序的復雜度和增量序列是相關的
{1,2,4,8,...}這種序列并不是很好的增量序列，使用這個增量序列的時間復雜度（最壞情形）是O(n^2)
Hibbard提出了另一個增量序列{1,3,7，...,2^k-1}，這種序列的時間復雜度(最壞情形)為O(n^1.5)
Sedgewick提出了幾種增量序列，其最壞情形運行時間為O（n^1.3）,其中最好的一個序列是{1,5,19,41,109,...}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/33371.html
標籤：嵌入式
上一篇：痞子衡嵌入式：恩智浦i.MX RT1xxx系列MCU硬體那些事（2.1）- 玩轉板載OpenSDA,Freelink除錯器