排序算法之希尔排序

发表于

前言

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

希尔排序的实质就是分组插入排序，它们的思想高度是一致的的（为了共产主义😁😁😁），不过希尔排序的速度蛮快的，甚至可以与快速排序相媲美！

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

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

不好意思上面的部分来自维基百科

好了，第一部分介绍完了，我们来看图说画：

看图说话

以一个 n = 11 的数组为例：

希尔排序01

第一次

第一步 设步长为 2 则 int gap = 11/2 = 5

将数组分为 5 组，每组两个数据

希尔排序02

第二步

那么就被分成了 A B C D E 这几组数据：

希尔排序03

第三步

对每组数据进行排序：

希尔排序04

于是数组变为下面的：

希尔排序05

第二次

第一步 重复上面第一步 int gap = 5/2 = 2

将数组分为 2 组，每组5个数据

希尔排序06

第二步

那么就被分成了 A B 这两组数据：

希尔排序07

第三步

对每组数据进行排序：

希尔排序08

于是数组变为下面的：

希尔排序09

第三次

第一步 重复上面第一步 int gap = 2/2 = 1

将数组分为 1 组，那就是整个数组

希尔排序09

对整个数组进行排序：
希尔排序10

第四次

第一步 重复上面第一步 int gap = 1/2 = 0

则此时 数组排序已经完成

看程序

经过上面的一步步的分析，相信大家已经可以看得懂下面的程序（按照上面的理解即可）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shellsort2(int a[], int n) {

    int j, gap;
    
    for (gap = n / 2; gap > 0; gap /= 2)
        for (j = gap; j < n; j++)//从数组第gap个元素开始
            if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
            {
                int temp = a[j];
                int k = j - gap;
                while (k >= 0 && a[k] > temp)
                {
                    a[k + gap] = a[k];
                    k -= gap;
                }
                a[k + gap] = temp;
            }
}

测试

下面我们开始测试，同样的四种：

  1. 有序
  2. 近乎有序
  3. 随机
  4. 倒叙

我们测试100W个数据，测试它的排序时间，测试用例的程序在这里，测试代码如下：

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
46
47
48
49
50
int n  = 100000;
// 有序
int *a = generateSequenceArray(n);
// 近乎有序
int *b = generateRandomSequenceArray(n, 100);
// 随机
int *c = generateRandomArray(n,0,n);
// 倒叙
int *d = generateReverseArray(n);

int *a1 = copyGenerateRandomArray(a, n);
int *a2 = copyGenerateRandomArray(a, n);
int *a3 = copyGenerateRandomArray(a, n);

int *b1 = copyGenerateRandomArray(b, n);
int *b2 = copyGenerateRandomArray(b, n);
int *b3 = copyGenerateRandomArray(b, n);

int *c1 = copyGenerateRandomArray(c, n);
int *c2 = copyGenerateRandomArray(c, n);
int *c3 = copyGenerateRandomArray(c, n);

int *d1 = copyGenerateRandomArray(d, n);
int *d2 = copyGenerateRandomArray(d, n);
int *d3 = copyGenerateRandomArray(d, n);

printf("**************有序*************\n");
testSort("插入排序　　", insertSort,a1, n);
testSort("插入排序优化", insertSort2,a2, n);
testSort("希尔排序　　", shellsort2,a3, n);
printf("\n**************近乎有序*************\n");
testSort("插入排序　　", insertSort,b1, n);
testSort("插入排序优化", insertSort2,b2, n);
testSort("希尔排序　　", shellsort2,b3, n);
printf("\n**************随机*************\n");
testSort("插入排序　　", insertSort,c1, n);
testSort("插入排序优化", insertSort2,c2, n);
testSort("希尔排序　　", shellsort2,c3, n);
printf("\n**************倒叙*************\n");
testSort("插入排序　　", insertSort,d1, n);
testSort("插入排序优化", insertSort2,d2, n);
testSort("希尔排序　　", shellsort2,d3, n);

free(a);free(a1);free(a2);free(a3);

free(b);free(b1);free(b2);free(b3);

free(c);free(c1);free(c2);free(c3);

free(d);free(d1);free(d2);free(d3);

log如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
**************有序*************
sortname:插入排序　　	 sorttime: 0.000404s
sortname:插入排序优化	 sorttime: 0.000474s
sortname:希尔排序　　	 sorttime: 0.003668s

**************近乎有序*************
sortname:插入排序　　	 sorttime: 0.042827s
sortname:插入排序优化	 sorttime: 0.020470s
sortname:希尔排序　　	 sorttime: 0.011824s

**************随机*************
sortname:插入排序　　	 sorttime: 17.607321s
sortname:插入排序优化	 sorttime: 8.014994s
sortname:希尔排序　　	 sorttime: 0.032545s

**************倒叙*************
sortname:插入排序　　	 sorttime: 35.988631s
sortname:插入排序优化	 sorttime: 16.293709s
sortname:希尔排序　　	 sorttime: 0.009289s

由此可以看出 希尔排序的强悍，特别是对于最坏情况的排序，是未优化过的插入排序的近4000倍！

不知道希尔排序 大家搞明白了么！！！ 😀😀😀

最后附上Demo