数据结构笔记(九):排序算法之希尔排序

发布于 / 程序猿 / 1 条评论

上篇文章介绍了直接插入排序,这篇文章介绍插入排序的另一种:希尔排序(Shell Sort)。希尔排序是直接插入排序算法的一种更高效的改进版本,是非稳定排序算法,因D.L.Shell于1959年提出而得名。

基本思想

对于有n个待排序元素的数列,先取一个小于n的整数d(步长)作为第一个增量将待排序元素分成d组子序列,所有距离为d的倍数的元素放在同一个组中;然后,对各组内的元素进行直接插入排序。 此次排序完成之后,每一个组的元素都是有序的。然后减小d的值,并重复执行上述的分组和排序。直到当d=1,即所有元素放在同一组中进行直接插入排序后,整个排序过程完成,数列完全有序。

希尔排序实质上是一种分组插入方法。

动画演示

对于长度为12的序列{61, 109, 149, 111, 34, 2, 24, 119, 122, 125, 27, 145},进行希尔排序。

  • 当 d = n = 12 时,无变化:{61, 109, 149, 111, 34, 2, 24, 119, 122, 125, 27, 145}

  • 当 d = 12/2 = 6 时,分组排序后:{24, 109, 122, 111, 27, 2, 61, 119, 129, 125, 34, 145}

  • 当 d = 6/2 = 3 时,分组排序后:{24, 27, 2, 61, 34, 122, 111, 109, 145, 125, 119, 149}

  • 当 d = 3/2 = 1 时:分组排序后:{2, 24, 27, 34, 61, 109, 111, 119, 122, 125, 145, 149}

画图太累了,我画一张吧。

不能太懒了,我再加一张图。

依次类推,得到当前排序序列后,继续分组并完成排序。

算法实现

  • 分函数写,便于理解
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn = 10000000;
const int Max = 10000;
int a[maxn];
void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << " ";
        if ((i+1) % 5 == 0)
            cout << endl;
    }
    cout << endl;
}

void shell_insert(int a[], int n, int d, int x) // 单组直接插入排序
{
    int k = n - d;
    while (k >= 0 && x < a[k]) // 如果x < a[k],则寻找x位置,并将后面数据的位置都后移
        a[k+d] = a[k], k -= d;
    a[k+d] = x;
}

void shell_sub_sort(int a[], int n, int d) // 对n-d组(d组)进行排序
{
    for (int i = d; i < n; ++i)
        shell_insert(a, i, d, a[i]);
}

void shell_sort(int a[], int n) // 按步长d分组
{
    int d = n >> 1; // 步长d每次减为原来一半
    while (d)
    {
        shell_sub_sort(a, n, d);
        d >>= 1;
    }
}

int main()
{
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    clock_t _start, _end;
    _start = clock();
    shell_sort(a, maxn);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
    //display(a, maxn);
    //cout << "----------------------------------" << endl;
    //display(a, maxn);
    return 0;
}
maxn = 10000:     0.004s
maxn = 100000:    0.114s
maxn = 1000000:   1.227s
maxn = 10000000:  19.198s(不定,此时使用sort耗时7s左右)
  • 单函数完成,代码量小
void Shell_sort(int a[], int n)
{
    for (int d = n >> 1; d; d >>= 1) // 增量
    {
        for (int i = d; i < n; ++i) // 分组插入排序
        {
            int k = i - d;
            int tmp = a[i];
            while (k >= 0 && tmp < a[k])
                a[k+d] = a[k], k -= d;
            a[k+d] = tmp;
        }
    }
}

:上面希尔排序的步长d选择都是从n/2开始,每次再减半,直到最后为1。

算法分析

1.时间复杂度

希尔排序的时间复杂度与增量(即,步长d)的选取有关。例如,当增量为1时,希尔排序退化成了直接插入排序,此时的时间复杂度为O(N²),而Hibbard增量的希尔排序的时间复杂度为O(N^(3/2))

2.稳定性

希尔排序是不稳定的算法。对于相同的两个数,可能由于分在不同的组中而导致它们的顺序发生变化。

3.希尔排序的时间性能优于直接插入排序的原因

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当N值较小时,N和N²的差别也较小,即直接插入排序的最好时间复杂度O(N)和最坏时间复杂度O(N²)差别不大。
③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量d逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按d-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。

4.增量序列的选择

Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征:
① 最后一个增量必须为1;
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

说明

本文基础知识部分来源于:skywang12345数据结构学习网,其中动画演示部分为:某国外视频网站录屏,已经上传到哔哩哔哩,点击:传送门

推荐阅读


The end.
2017-12-08 星期五

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(九):排序算法之希尔排序
  1. 太傅

    推荐阅读的博客或者其他资料都可以算得上是经典「划掉,写得很好的」文章了。?