排序算法---插入排序&希爾排序

一、直接插入排序

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

在講解直接插入排序之前，先讓我們腦補一下我們打牌的過程。

先拿一張5在手裡，

摸到一張4，比5小，插到5前面，

摸到一張6，比5大，插到5後面，

摸到一張8，比6大，插到6後面，

這就是一個關于直接插入排序的經典例子了，相信這樣更容易了解插入排序的算法思想了吧。

二、直接插入排序算法實作

1、算法實作步驟

假設有一組無序序列 R0, R1, … , RN-1。

(1) 我們先将這個序列中下标為 0 的元素視為元素個數為 1 的有序序列。

(2) 然後，我們要依次把 R1, R2, … , RN-1 插入到這個有序序列中。是以，我們需要一個外部循環，從下标 1 掃描到 N-1 。

(3) 接下來描述插入過程。假設這是要将 Ri 插入到前面有序的序列中。由前面所述，我們可知，插入Ri時，前 i-1 個數肯定已經是有序了。是以我們需要将Ri 和R0 ~ Ri-1 進行比較，确定要插入的合适位置。這就需要一個内部循環，我們一般是從後往前比較，即從下标 i-1 開始向 0 進行掃描。

2、代碼實作子產品

void InsertSort(int*array, int size)
{
    for (int i = 1; i < size; i++)
    {
        int key = array[i];
        int end = i - 1;
        //找到插入位置
        while (end >= 0 && key < array[end])
        {
            array[end + 1] = array[end];
            --end;
        }
        //插入元素key
        array[end + 1] = key;
    }
}
           

算法性能分析：

（1）時間複雜度：當元素越接近有序，直接插入效率越高，時間複雜度在O(1)~O(N^2)之間

（2）空間複雜度：O(1);

（3）穩定性：是一種穩定的排序算法

3、算法改進

我們可以知道，當資料接近反序時，直接插入排序需要進行多次比較和搬移資料才能完成，這時就可以采用二分法實作，減少比較操作，提高插入效率：

代碼實作：

void BinaryInsertSort(int *array, int size)
{
    for (int i = 0; i < size; i++)
    {
        int key = array[i];
        int left = 0;
        int right = i - 1;
        int mid = 0;
        int end = i - 1;
        //二分法找待插入元素的位置
        while (left <= right)
        {   
            mid = left + ((right - left) >> 1);
            if (key < array[mid])
                right = mid - 1;
            else 
                left = mid + 1;
        }
        //搬移元素
        while (end >= left)
        {
            array[end + 1] = array[end];
            --end;
        }
        //插入元素
        array[end+1] = key; 
    }   
}
           

三、希爾排序

希爾排序(Shell’s Sort)是插入排序的一種，又稱“縮小增量排序”，是直接插入排序算法的一種更高效的改進版本；

其排序過程如下所示：

算法實作步驟：

假設增量序列為 h(1)，h(2)…..h(k)，其中h(1)必須為1，

且h(1）<(2)…

（1）第一趟排序時在增量為h(k)的各個元素上進行比較；

（2）第二趟排序在增量為h(k-1)的各個元素上進行比較;

……….

（3）最後一趟在增量h(1)上進行比較。由此可以看出，每進行一趟排序，增量是一個不斷減少的過程，是以稱之為縮小增量。

代碼實作部分：

void ShellSort(int*array, int size)
{
    int gap = size;
    while (gap>1)
    {
        gap = size / 3 + 1;
        for (int i = gap; i < size; i++)
        {
            int key = array[i];
            int end = i - gap;
            //找帶插入元素的位置
            while (key < array[end] && end >= 0)
            {
                array[end + gap] = array[end];
                end = end - gap;
            }
            //插入元素
            array[end + gap] = key;
        }
    }
}
           

算法性能分析：

（1）時間複雜度：O(n^1.25 ~ 1.6n^1.25)

（2）空間複雜度：O(1)

（3）穩定性：穩定

（4）适用場景：資料量大