希尔排序

基本思路

希尔排序需要使用一个增量序列，如3或5，是插入排序的改编，插入排序的增量序列为默认的1
第一轮使用一个增量默认为n/2，之后每一轮减少这个增量一般要除以2，即下一次为n/4，再下一次的增量为n/8…。
因为每轮的排序间隔逐渐缩小，希尔排序也称为“缩小增量排序”
每一次都选择这样的增量中的数字
每一轮排的都是对应增量间距的数字，举例说明：
有1、2、3、4、5、6、7、8、9、10、11编号的数组
第一轮的增量为n/2 => 增量为5，所以第一轮以五为增量选出 多个 子数组：
{1、6、11} ;{ 2、7 };{ 3、8 };{ 4 、 9 };{ 5 }这十一个数据的第一轮应该就是这样分组
然后对这几个子数组做插入排序，相当于1、6、11为一组，这一轮就只相互比较这三个数；然后2、7相互比较…
最后会到1为增量的情况，此时就相当于普通的插入排序，但是我们提到过，插入排序的时间复杂度与数据组成有关，但是一般情况下数据组成都不是是理想状态，
使用希尔排序的目的是将数据组成尽量变成理想状态，来优化时间复杂度
所以，希尔排序需相当于是插入排序的优化

与直接插入比较的区别

  • 直接插入排序是稳定的；而希尔排序是不稳定的
  • 直接插入排序更适合于原始记录基本有序的集合
  • 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显
  • 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构

总结：数目少的情况下直接插入排序更优;数据多的情况，希尔排序更优

时空间复杂度

时间复杂度

步长的选择是希尔排序的重要部分，只要最终步长为1任何步长序列都可以工作。
算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
步长序列的不同，会导致最坏的时间复杂度情况的不同。以N/2为步长的最坏时间复杂度为 $N^2$ 。
Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比 $O(N^2)$ 类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

空间复杂度

希尔排序的空间复杂度为 $O(1)$

稳定性

希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法

源代码

vector 更通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>

using namespace std;

vector<int> ShellSort(vector<int> list)
{
    vector<int> result = list;
    int n = result.size();
    for (int gap = n >> 1; gap > 0; gap >>= 1)
    {
        //下面的代码就是插入排序，只是将增量从1改为gap了，这里gap表示的是增量
        for (int i = gap; i < n; i++)
        {
            int temp = result[i];
            int j = i - gap;
            while (j >= 0 && result[j] > temp)
            {
                result[j + gap] = result[j];
                j -= gap;//只比较在这个增量下选出来的一个组中的元素大小
            }
            result[j + gap] = temp;
        }
    }
    return result;
}

int main()
{
    int arr[] = {6, 4, 8, 9, 2, 3, 1};
    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
    cout << "排序前" << endl;
    for (int i = 0; i < test.size(); i++)
    {
        cout << test[i] << " ";
    }
    cout << endl;
    vector<int> result;
    result = ShellSort(test);
    cout << "排序后" << endl;
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
}

数组简单理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

void shellsort()
{
    int a[] = {10, 8, 11, 7, 4, 12, 9, 6, 5, 3, 1, 0, 2, 15, -2, 16, 8, -3, 16};

    int size = sizeof(a) / sizeof(int);
    int temp;
    for (int increase = size >> 1; increase > 0; increase >>= 1) //每一轮结束后都除以而缩小增量
    {
        for (int i = increase; i < size; i++) //i为这一个子数组的最后一个元素，后面操作基本上就是插入排序了
        {
            temp = a[i];
            int j;
            for (j = i; j > increase && temp < a[j - increase]; j -= increase) //这里是和插入排序之间的区别，也是从这里实现了分组操作，
                                                                               //这一轮只排这些位置的数，而不是直接将这个子数组拿出来做成一个新数组再排序
                a[j] = a[j - increase];
            a[j] = temp;
        }
    }
    for (int i = 0; i < size; i++)
        cout << a[i] << " ";
}

int main()
{
    shellsort();
}