十大排序算法之——希爾排序

具體細節在代碼中注釋。

#include<string>
#include<iostream>
#include<cstring>
#include<head.h>
using namespace std;
//希爾排序
//template<typename T>
void shellSort(int *,int);
int main()
{
    int arr[] = {7,8,10,4,5,2,1,6,3,9};
    int length = sizeof(arr)/sizeof(int);
    cout << "原來的序列：" << endl;
    for(auto var : arr)
    {
        cout << var << " ";
    }
    shellSort(arr,length);

    cout << "\n現在的序列：" << endl;
    for(auto var : arr)
    {
        cout << var << " ";
    }

    return 0;
};

//template<typename T>
void shellSort(int *arr,int length)
{
    for(int gap=length/2;gap>0;gap/=2)          //5 | 2 增量gap為上一次長度的一半
    {
        cout << "\n\n一次遞減增量排序開始，目前gap=" << gap;
        for(int ix=gap;ix<length;++ix)          //5 6 7 8 9 | 2 3
        {
            int jy = ix;                        //5 6 7 8 9 | 2 3   交換完目前位置元素和增量位置元素之後，還要繼續和增量的增量元素進行比較
            while(jy-gap>=0 && arr[jy - gap] > arr[jy])     //0 1 2 3 4 | 0 1      将首目前素和目前元素的增量元素進行比較
            {                                               //第二次還是0,2 1,3 2,4 3,5 4,6
                int temp = arr[jy-gap];
                arr[jy-gap] = arr[jy];
                arr[jy] = temp;
                jy -= gap;                                  //-5  增量元素要一直到最前面，一直到該位置有序，即隻要增量相同，那麼增量倍數的位置元素絕對有序 
            }
            cout << "\n目前的序列：" << endl;
            for(int i=0;i<length;++i)
            {
                cout << arr[i] << " ";
            }
        }
    }
}
           

輸出：

原來的序列：
7 8 10 4 5 2 1 6 3 9 

一次遞減增量排序開始，目前gap=5
目前的序列：
2 8 10 4 5 7 1 6 3 9 
目前的序列：
2 1 10 4 5 7 8 6 3 9 
目前的序列：
2 1 6 4 5 7 8 10 3 9 
目前的序列：
2 1 6 3 5 7 8 10 4 9 
目前的序列：
2 1 6 3 5 7 8 10 4 9 

一次遞減增量排序開始，目前gap=2
目前的序列：
2 1 6 3 5 7 8 10 4 9 
目前的序列：
2 1 6 3 5 7 8 10 4 9 
目前的序列：
2 1 5 3 6 7 8 10 4 9 
目前的序列：
2 1 5 3 6 7 8 10 4 9 
目前的序列：
2 1 5 3 6 7 8 10 4 9 
目前的序列：
2 1 5 3 6 7 8 10 4 9 
目前的序列：
2 1 4 3 5 7 6 10 8 9 
目前的序列：
2 1 4 3 5 7 6 9 8 10

一次遞減增量排序開始，目前gap=1
目前的序列：
1 2 4 3 5 7 6 9 8 10
目前的序列：
1 2 4 3 5 7 6 9 8 10
目前的序列：
1 2 3 4 5 7 6 9 8 10
目前的序列：
1 2 3 4 5 7 6 9 8 10
目前的序列：
1 2 3 4 5 7 6 9 8 10
目前的序列：
1 2 3 4 5 6 7 9 8 10
目前的序列：
1 2 3 4 5 6 7 9 8 10
目前的序列：
1 2 3 4 5 6 7 8 9 10
目前的序列：
1 2 3 4 5 6 7 8 9 10
現在的序列：
1 2 3 4 5 6 7 8 9 10