甲乙小朋友的房子

甲乙小朋友很笨,但甲乙小朋友不会放弃

0%

希尔排序

思想

希尔排序的实质是分组插入排序,又称缩小增量排序。

该方法的基本思想是: 1. 先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的),对这些子序列分别进行直接插入排序 2. 依次缩减增量再进行排序 3. 待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

例子

现在我们要将这样一个数组排序,一共有10个元素

  • 第一次 增量 gap = 10/2 = 5

整个数组被分成了5个子数组,分别是[49,13],[38,27],[65,49],[97,55],[26,4] 然后对这五个子数组进行插入排序,得到下面结果

  • 第二次 增量 gap = 5/2 = 2

这次我们把整个数组分成了两个子数组,分别是[13,49,4,38,97],[27,55,49,65,26] 对这个两个子数组排序,结果如下:

  • 第三次 增量 gap = 2/2 = 1 此时整个数组已经接近有序,对整个数组进行全排列

最终得到数组有序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//希尔排序
void HillSort(int a[], int len) {
int delta = len/2;
while (delta > 0) {
for (int i = 0; i < delta; i++) {//分成了delta个子序列
//对每个子序列进行插入排序
for (int j = i + delta; j < len; j = j + delta) {
int jj = j - delta;
int temp = a[j];
while ((a[jj] > temp)&&(jj>=0)) {
a[jj + delta] = a[jj];
jj -= delta;
}
//插入
a[jj + delta] = temp;
}
}
delta = delta / 2;
}
}

优化

白话经典算法系列原文是这么说的 >很明显,上面的shellsort1代码虽然对直观的理解希尔排序有帮助,但代码量太大了,不够简洁清晰。因此进行下改进和优化,以第二次排序为例,原来是每次从1A到1E,从2A到2E,可以改成从1B开始,先和1A比较,然后取2B与2A比较,再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始,每个元素与自己组内的数据进行直接插入排序显然也是正确的。

我理解了一下,思路就是把在序列中提取子序列的过程简化了,我们可以从第gap个元素开始,向后遍历到序列末尾,可以个元素都跟其所在的子序列中位于它前面的数字做插入排序,最终就会得到一个有序数列了~

画个图表示一下吧,还是刚才那个序列,比如说此时进行到第二次排序了,gap=2的情况:

从a[2]开始遍历,此时a[2]所在的子序列为[a[0],a[2],a[4],a[6],a[8]],需要将a[2]和位于它前面的a[0]比较,插入到合适的位置:

指针后移一位, 同上此时a[3]所在的子序列为[a[1],a[3],a[5],a[7],a[9]],需要将a[3]和位于它前面的a[1]比较,插入合适的位置:

接下来指针指向a[4],此时需要将a[4]和位于它前面的a[2]、a[0]比较,插入合适的位置:

下面重复上面的步骤:

此处省略剩余步骤.....最终可以将数组排列至有序状态

现在可以上代码了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//希尔排序
void HillSort(int a[], int len) {
int delta = len/2;
while (delta > 0) {
for (int i = delta; i < len; i++) {//遍历
//对该元素子前面的子数组进行插入排序
int temp = a[i];
int jj = i - delta;
while ((jj >=0)&&(a[jj]>temp)){
swap(a[jj], a[jj+delta]);
jj -= delta;
}
}
delta = delta / 2;
}
}

参考

MoreWindows Blog 白话经典算法系列