八大排序算法--希尔排序

1、算法思想

希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

如下图所示为算法模拟过程:

2、代码

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
#include <iostream>

using namespace std;

//希尔排序
void shellSort(int iarr[],int length)
{
int dt[3] = {5,3,1},i =0 ,j,k,temp;
for(j = 0; j < 3; ++j)
{
for(i = dt[j]; i < length; ++i)
{
temp = iarr[i];
k = i - dt[j];
while(temp < iarr[k] && k >= 0)
{
iarr[k + dt[j]] = iarr[k];
k -= dt[j];
}
iarr[k + dt[j]] = temp;
}
}
}
int main()
{
int a[25]={4,1,3,2,16,9,10,14,8,7,7,10,7,28,30,3,12,0,1,3,9,12,11,4,19};
shellSort(a,25);
for(int i=0;i < 25; ++i)
cout << a[i] << " ";
return 0;
}

3、算法分析

3-1、性能分析

3-2、直接插入排序与希尔排序的比较

直接插入排序是稳定的;而希尔排序是不稳定的。

直接插入排序更适合于原始记录基本有序的集合。

希尔排序的比较次数和移动次数都要比直接插入排序少,当N越大时,效果越明显。

希尔排序的比较次数和移动次数都要比直接插入排序少,当N越大时,效果越明显。

直接插入排序也适用于链式存储结构;希尔排序不适用于链式结构

-------------The End-------------
谢谢大锅请我喝杯阔乐~