排序演算法：插入排序與shell排序

今天講兩個經典的排序所發，插入排序和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時，整份文件恰被分成一組，演算法便終止。

過程示範（該圖也是從網路上找的）：

程式碼實作(這裡使用的是C語言)：

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中文網其他相關文章！