数据结构：希尔排序

作者: PerkyRookie | 来源:发表于2018-12-18 19:03 被阅读0次

021-数据结构与算法-排序
排序算法-堆排序
Python 算法大全
C语言：关于数据的几种排序算法
算法与数据结构路线图
数据结构-希尔排序
数据结构：希尔排序
【数据结构】希尔排序
数据结构--希尔排序
排序算法(二)之希尔排序

前言

希尔排序是Donald Shell于1959年提出来的一种排序算法，它是第一批突破O(n²)这个时间复杂度的算法之一。大话数据结构对这个算法的讲解，我看得一知半解的，之后网上找了下资料，发现维基百科对这个算法的讲解非常不错，特在此整理一波。

原理

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

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

image 先上个维基百科的动图，不知道你们看不看得懂，反正我不是很懂……

什么鬼.png

说说我的个人理解：

希尔排序其实就是直接插入排序的升级，原理就是先将整个待排序列按照某个增量（也称步长）分割成若干个子序列分别进行直接插入排序，然后合并，之后依次缩小增量大小在进行排序，当增量足够小（通常为1）时，再对全体元素进行直接插入排序，而此时需排序的数据几乎是已排好的了，所以此时插入排序较快。

当然如果你觉得文字比较乏味就看下面的这些例子吧

例如，假设有这样一组数[9 1 5 8 3 7 4 6 2]，如果我们先以步长为4进行分割，就是这样：

9 1 5 8
3 7 4 6 
2

然后我们对每列进行排序（注意每列哦）：

2 1 4 6
3 7 5 8
9

将上述四行数字，依序合并我们得到：[ 2 1 4 6 3 7 5 8 9 ]。此时2已经往前移，而8、9已经在后两位，然后再以2为步长进行分割：

继续排序：

合并得到［ 2 1 3 6 4 7 5 8 9］，此时序列已经基本有序，需交换数据的情况大为减少，这时整列进行直接插入排序效率就非常高。

最终完成排序过程，也就是步长为1时，得到最终序列为：1 2 3 4 5 6 7 8 9。

笑.png

示例代码（C）

#include <stdio.h>
#define MAXSIZE 100 //用于要排序数组的最大值 

typedef struct      //定义一个顺序表结构 
{
    int r[MAXSIZE+1];   //用于存储要排序数组，r[0]用作哨兵或者临时变量 
    int length;         //用于存储顺序表的最大长度 
}SqList;

void ShellSort(SqList *L)
{
    int i,j;
    int gap=L->length;  //获取数组长度 
    
    for(gap/=2;gap>=1;gap/=2)   //步长 
        for(i=gap+1; i<=L->length; i++) //从第gap+1个元素开始，因为r[0]被当做临时变量 
            if(L->r[i] < L->r[i-gap])   //每个元素与自己组内的数据进行直接插入排序 
            {
                L->r[0]=L->r[i];    //把要交换的数据暂存的L->r[0]中 
                for(j=i-gap; j>0&&L->r[j] > L->r[0]; j-=gap)    
                    L->r[j+gap] = L->r[j];  //记录后移，查找插入位置 
                    
                L->r[j+gap]=L->r[0];    //插入 
            }
} 

int main()
{
    int i=0;
    int array[] = {39,80,76,41,13,29,50,78,30,11,100,7,41,86};
    
    SqList L;
    L.length = sizeof(array)/sizeof(array[0]);  //获取数组长度 
    for(i=0;i<L.length;i++)
    {
        L.r[i+1]=array[i];  //把数组存入顺序表结构 
    }
    ShellSort(&L);
    
    //输出排序后的数组 
    for(i=0;i<L.length;i++) 
    {
        printf("%d ",L.r[i+1]);
    }
    return 0;
}

可能有几个步骤略难懂，这里解释下：

第17行：这里的步长采用 $\frac {n} {2}$ ,最终判断条件为gap>=1,这里不管你数组初始长度为多少，除到最后均会等于1，而等于1时，就是执行最后一次循环，这个时候也就是所有元素进行直接插入排序。当然也可写成gap>0。
第18行：在前面定义顺序表结构时，我们加多了一位，也就是把r[0]当做交换数据时的临时变量。
第22~23行：对于这个循环我们直接拿上面的例子中的一列进行讲解（9 3 2）：

image

当 $i=5$ 时，9和3进行了一次交换，变为（3 9 2）(位置为1 5 9），之后在 $i=9$ 时 $(此时r[0]=r[i]=2)$ ，做出的交换如上图所示（图略差...)，分为三个步骤： $(gap=4)$

第一次进入循环 $j=i-gap=5,r[j]=r[5]=9>r[0]$ ，执行23行得 $r[j+gap]=r[9]=r[j]=9$ ，此时该列数值变为(3 9 9)；
继续第二次循环 $j=j-gap=1,r[j]=r[1]=3>r[0]$ ，同样执行循环 $r[j+gap]=r[5]=r[j]=3$ ，此时变为（3 3 9）；
跳出循环(注意：跳出循环时多执行了一次 $j-=gap=-3$ )，执行 $r[j+gap]=r[-3+4]=r[1]=r[0]=2$ ，最终变为(2 3 9)。

步长（增量）选择

步长的选取非常关键，但是步长的选择没有统一规定，也没绝对的规律。只要满足最后一个步长为1即可。Donald Shell最初建议步长选择为 $\frac {n} {2}$ ,虽然这样去可以比 $O(n^2)$ 类的算法更好，但仍然有减少平均时间和最差时间的余地。维基百科给出的部分步长与最坏情况下复杂度有：

image

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，该序列的项来自 $9\times4^i-9\times2^i+1$ 和 $2^{i+2}\times(2^{i+2}-3)+1$ 这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序（后续博客整理），但是在涉及大量数据时希尔排序还是比快速排序慢。