/*

希尔排序：

实际上是基于插入排序的，在插入排序中相比较的是相邻的两个元素，

但是如果一个很小的数在数组的最右端，而他本应该是在最左端的，

这样的话所有中间的元素都要向右移动一位，并且执行了N次。

希尔排序就是首先对大跨度的元素做比较并且进行移动，这样的就相对有序了，

再在这个基础上进行普通的插入排序，效率就会高很多。

效率：

快速排序>希尔排序>简单排序

希尔排序在最坏的执行效率上和平均的执行效率上没有差很多。

*/

/* 希尔排序(Shell Sort)也称为递减增量排序，是插入排序的一种高速而稳定的改良版。

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

* # 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

* # 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

* 对有n个元素可比较的资料，先取一个小于n的整数d?作为第一个增量，把文件的全部记录分成d?个组。

* 所有距离为d?的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d?

<d?

* 重复上述的分组和排序，直至所取的增量为1，即所有记录放在同一组中进行直接插入排序为止。

* 该方法实质上是一种分组插入方法。

* 已知的最好序列是{1,4,10,23,57,132,301,701,1750,...}。具有此分组序列的希尔排序比插入排序和

堆排序

* 要快，但是，如果对小数组（少于50个元素）情况下比快速排序快，那么对大数组就要比快速排序慢。

在1750之后

* 的序列值按如下公式计算：next_step = round(step * 2.3)

* 在实际应用中，对于经典的shell分组序列{n/2,n/4,...,1},一般采用2.2作为递减因子而不是2，这样

可以获得

* 更好的效率。

*/

/*

eg 7 3 5 8 9 1 2 4 6

increment : 9/2 = 4; 分组，每组4个元素 7358 9124 6

7358 9124 6

7158 9324 6

7128 9354 6

7124 9358 6

7124 6358 9

6124 7358 9

increment : 4/2 = 2; 分组，每组2个元素 61 24 73 58 9

21 64 73 58 9

21 63 74 58 9

21 63 54 78 9

21 53 64 78 9

increment : 2/2 = 1; 分组，每组1个元素 2 1 5 3 6 4 7 8 9

1 2 5 3 6 4 7 8 9

1 2 3 5 6 4 7 8 9

1 2 3 5 4 6 7 8 9

1 2 3 4 5 6 7 8 9 over

*/

#include <iostream>

using namespace std;

typedef int T;

void PrintArry(int a[], int n)

{

for (int i=0; i<n; i++)

cout<< a[i]<<" ";

cout<<endl;

}

void ShellSort(T a[], int n){

int i, j;

T temp;

int increment = n/2;

while (increment > 0)

{

for(i = increment; i<n; i++){

temp = a[i];

j = i;

while (j-increment>=0 && temp < a[j-increment])

{

a[j] = a[j-increment];

j -= increment;

}

a[j] = temp;

}

increment /= 2;

PrintArry(a, 9);

}

}

int main(){

int a[9] = {7,3,5,8,9,1,2,4,6};

ShellSort(a, 9);

//PrintArry(a, 9);

return 0;

}