1.2 插入排序算法之希爾排序

1、希爾排序：（Shell`s Sort）

思想：

• 将待排序的表分成若幹組
• 每組内進行直接插排，使整個序列基本有序
• 然後再對整個表進行更加細化的分組直接插排，始之基本有序
• 直至無法細化分組最終有序

分組方法：

• 對給定的一個步長d(d>0)，将下标相差為d的倍數的元素分在一組。

• 希爾排序算法經典的d的取值依次為:

  d1=n/2, d2=d1/2, ……，dk=1

  (直至步長為1，不可再分組，其中n為表長,)

—— 即不同步長進行分組，各個分組内進行”直接插入排序”，直至不能再分

語言很蒼白，用圖例來解決

例：數組Arr[] = {100, 8, 20, 16, 14, 7, 105,50, 78, 9}

• Step1 : 步長d1為5，相同顔色的為一組，比如第一組為”100 & 7”，每個組進行直接插排，局部有序
• Step2 : 第一輪結束，取步長為d2 = d1/2 , Arr[0] , Arr[2], Arr[4],Arr[6],Arr[7]相同顔色為一組；每組進行直接插排，局部有序

• Step3 : 取步長為 d3 = d2 /2 ,為1，無法再分，對整個數組進行直接插排，整體有序

  [注] 當步長 dk=1時，其實就是對最後局部有序的數組進行直接插入排序。

希爾排序算法及分析

• 穩定性：不穩定排序
• 空間性能：1個輔助空間。

• 時間性能: 與資料表初始狀态關系不大：

  需要循環log2n趟，每趟O(n)

  因而時間複雜度為O(nlog2n)

代碼：

#include <iostream>
using namespace std;

void Shell_sort(int *pArr, int len)
{
    int d = len / ;

    while(d > )
    {
        for(int k = ; k < d; k++)   // k : 每一個步長對應的分組數，依次對每個分組操作 
        {
            //對每一組進行 Straight_insert_Sort
            for(int i = d + k; i<len; i=i+d)
            {
                int temp = pArr[i];

                int j = i - d;

                while( j >=  && (pArr[j] > temp))
                {
                    pArr[j+d] = pArr[j];

                    j-=d;
                }
                pArr[j+d] = temp;
            }

        }
        d = d / ;
    }

    return;
}

/*
Shell_sort2 的代碼實作與上圖中的示例圖分析了解上可能有差别，但是實作的結果是相同的；
Shell_sort 是先根據步長将組分好，然後将第一個組中進行直接插排，再将第二個組進行直接插排，依次類推.
Shell_sort2 是：
組1的第二個元素與組1第一個元素直接插排，組2的第二個元素與組2第一個元素直接插排...組k的第二個元素與組k第一個元素直接插排;
組1的第三個元素與組1前兩個元素直接插排，組2的第三個元素與組2前兩個元素直接插排...組k的第二個元素與組k的前兩個元素直接插排
依次類推，可以看出并沒有嚴格先将某一組按照直接插排排好，再進行下一組的整體直接插排！！！
單步一下你就知道。2代碼更簡潔
*/
void Shell_sort2(int *pArr, int len)
{
    int d = len / ;

    while(d>)
    {
        for(int i = d; i < len; i++)     //單步走一下就很清楚 
        {
            int temp = pArr[i];

            int j = i-d;

            while(j>= && (pArr[j] > temp))
            {
                pArr[j+d] = pArr[j];

                j = j-d;
            }

            pArr[j+d] = temp;
        }    //對給定的d，在每一組内插入排序

        d = d/;
    }
    return;
}

int main()
{
    int a[]={,,,,,,,,,};
    int len = ; 

    Shell_sort(a, len);

    for(int i = ; i < len; i++)
    {
        cout<<a[i]<<"  ";
    }
    cout<<endl;

    return ;
 } 
           

最後的大白話：

Shell Sort 根據步長 d（分組）進行直接插入排序。