希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时(这时数组已经部分有序),整个文件恰被分成一组,算法便终止。

原理

对于大规模乱序数组插入排序会很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端(如果最小的元素正好在数组的尽头,要将它移动到正确的位置就需要N-1次移动。)希尔排序为了加快速度简单的改进了插入排序,交换不相邻的元素以对数组的局部进行排序(将整个有序序列分割成若干小的子序列分别进行插入排序)。

排序过程是:先取一个正整数h < n,把所有序号相隔h的数组元素放一组,组内进行直接插入排序;然后取h1 < d1,重复上述分组和排序操作;直至hi = 1,即所有记录放进一个组中排序为止。(一般的初次取序列的一半为增量,以后每次减半,直到增量为1。)

希尔排序高效的原因是它权衡了子数组的规模和有序性。排序之初,各个子数组都很短,排序之后子数组都是部分有序。这两点都很适合插入排序。

希尔排序.png

实现

java
1
2
3
4
5
6
7
8
9
10
11
12
public static void ShellSort(int[] a) {
int N = a.length;
int h = N/2;
while(h >= 1) {
for (int i = h; i < N; i ++) {
for (int j = i; j >= h && less((a[j], a[j-h])); j -= h) {
exch(a, j, j-h);
}
}
h = h/2;
}
}
C++
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
#include<iostream>
using namespace std;
class ShellSort
{
public:
int* shellSort(int* A, int n)
//希尔排序
{
int gap,i,j,temp;
if(n==1)
return A;
for(gap=n/2;gap>0;gap/=2)
{
i=gap;
while(i<n)
{
temp=A[i];
j=i-gap;
while(j>=0&&A[j]>temp)
{
A[j+gap]=A[j];
j=j-gap;
}
A[j+gap]=temp;
i++;
}
}
return A;
}
};

int main()
{
int arr[]={54,35,48,36,27,12,44,44,8,14,26,17,28};
ShellSort a;
a.shellSort(arr,13);
for(int i=0;i<13;i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}

less()比较两个元素、exch()交换两个元素、具体实现见插入排序

稳定性

由于存在多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

算法分析

算法最开始以一定的增量进行排序。然后会继续以一定增量(增量逐渐减小)进行排序,最终算法以增量为1进行排序。当增量为1时,算法变为插入排序,这就保证了数据一定会被排序。
希尔排序的时间复杂度与增量序列的选取有关
以n/2作为增量时平均时间复杂度为nlogn,最坏时间复杂度为n^2。因为不需要占用其它辅助空间所以空间复杂度为O(1)。

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