1. 復(fù)雜度與穩(wěn)定性

算法時(shí)間復(fù)雜度

最壞情況：O(n^2)

最好情況：O(n)

平均情況：O(n^2)

穩(wěn)定性：不穩(wěn)定排序

2.過(guò)程介紹

希爾排序，又名遞減增量排序算法，是一種非穩(wěn)定的更高效的插入排序，在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率極高，即可以達(dá)到線性排序的效率，直接插入排序整體來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位；

希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

過(guò)程如下：

1. 選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；

3. 每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

3. 圖示過(guò)程

可以見(jiàn)的，相比直接插入排序由于可以每趟進(jìn)行分段操作，故整體效率體現(xiàn)較高。

4. 相關(guān)的代碼

#include<iostream>
using namespace std;
void shellSort(int arr[], int n) {
    int i, j, gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = 0; i < gap; i++) {
            for (j = i + gap; j < n; j += gap) {
                for (int k = j; k > i && arr[k] < arr[k-gap]; k -= gap) {
                    swap(arr[k-gap], arr[k]);
                }
            }
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=8;
    shellSort(a,n);
    for(int i=0; i<n; i++) {
        cout<<a[i]<<' ';
    }
    return 0;
}