排序---希尔排序

1. 希尔排序

希尔排序(Shell Sort)，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。【详情见维基百科】

我们使用插入排序时，希望待排序列具有以下特性：

待排序列部分有序
序列较短

而对于随机无序序列，插入排序时间复杂度为O(n²)

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

**希尔排序**
以23, 10, 4, 1的步长序列进行希尔排序。
分类	排序算法
数据结构	数组
最坏时间复杂度	根据步长序列的不同而不同。已知最好的： $O(nlog^2 n)$
最优时间复杂度	O(n)
平均时间复杂度	根据步长序列的不同而不同。
最坏空间复杂度	O(n)

2. 希尔排序C++ 实现

#include<iostream>
#include<vector>
using namespace std;

void ShellSort(vector<int> &array){
    int h = 1;
    // 递增序列 1, 4, 13, 40, ...
    while(h < array.size()/3)
        h = 3 * h + 1;

    while(h >= 1){
        for(int i = h; i < array.size(); i++){
            for(int j = i; j >= h; j -= h){
                if(array[j] < array[j-h])
                    swap(array[j], array[j-h]);
            }
        }
        h = h / 3;
    }
}


int main(int argc, char const *argv[])
{
    vector<int> a1 = {5, 9, 0, 1, 3, 6, 4, 8, 2, 7};
    ShellSort(a1);
    for(auto &it : a1)
        cout<<it<<' ';
    cout<<endl;

    return 0;
}

【点击此处查看常用排序算法】