今天講兩個經典的排序所發，插入排序和shell排序。你可以把shell排序理解為插入排序的升級版。
插入排序
插入排序（Insertion-Sort）的演算法描述是一種非常簡單直覺的排序演算法。它的複雜度和冒泡排序差不多。工作原理是透過建立有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
從網路上找了一個動圖如下：
#流程如下：
從第一個元素開始，該元素可以認為已經被排序；
取出下一個元素，在已經排序的元素序列中從後向前掃描；
如果該元素（已排序）大於新元素，將該元素移到下一位置；
#重複步驟3，直到找到已排序的元素小於或等於新元素的位置；
將新元素插入到該位置後；
#重複步驟2~5。
程式碼實作(這裡使用的是C語言)：
void insort (int arr[], int len)
{
int i,current,preindex;
for (i = 1; i < len; i++) {
preindex = i - 1;
current = arr[i];
while (preindex >= 0 && current < arr[preindex]) {
arr[preindex + 1] = arr[preindex];
preindex --;
}
arr[preindex + 1] = current;
}
}shell排序
##在理解了插入排序後，就很容易理解shell排序。 Shell排序演算法是D.L.Shell於1959年發明的，其基本思想是：先比較距離遠的元素，這樣可以快速減少大量的無序情況，從而減輕後續的工作。被比較的元素之間的距離逐步減少，直到減少為1，這時排序就變成了相鄰元素的交換。 希爾排序是把記錄按下表格的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整份文件恰被分成一組，演算法便終止。 過程示範（該圖也是從網路上找的）：
void shell_sort (int arr[], int len)
{
int gap,i,current,preindex;
for (gap = len / 2; gap > 0; gap /= 2) {
for (i = gap; i < len; i++) {
preindex = i - gap;
current = arr[i];
while (preindex >= 0 && current < arr[preindex]) {
arr[preindex + gap] = arr[preindex];
preindex -= gap;
}
arr[preindex + gap] = current;
}
}
}以上是排序演算法：插入排序與shell排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
