/*** 希尔排序实质就是分组插入排序，是插入排序法的一种改进，希尔排序是非稳定的排序方法。***/

/*** 基本思想：先将整个待排序序列分割成若干子序列（由相隔某个“增量”的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，当gap值逐渐减小后，虽然子序列的元素变多，但大多基本有序，所以继承了直接插入排序的有点 ***/

/*** 平均时间复杂度：O(nlog2(n))；空间复杂度：O(1) ***/

/*** 希尔排序的效率取决于增量gap的选取，时间复杂度并不是一个定值，一般步长取一半***/

/*** 例子：假设有一组｛9, 1, 2, 5, 7, 4, 8, 6, 3, 5｝序列。

* 第一趟排序：

* 设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。

* 第二趟排序：

* 将上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。按照直接插入排序的方法对每个组进行排序。

* 第三趟排序：

* 再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。***/

#include<iostream>

using namespace std;

//严格按照定义写的希尔排序

void ShellSort(int arr[],int n)

{

int i,j,gap;

for(gap=n/2;gap>0;gap/=2)

for(i=0;i<gap;i++)

{

for(j=i+gap;j<n;j+=gap)

{

int temp=arr[j];

int k=j-gap;

while(k>=0 && arr[k]>temp)

{

arr[k+gap]=arr[k];

k-=gap;

}

arr[k+gap]=temp;

}

}

}

//以n为10的一个数组9, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

//第一次 gap = 10 / 2 = 5

//49 38 65 97 26 13 27 49 55 4

//1A 1B

// 2A 2B

// 3A 3B

// 4A 4B

// 5A 5B

//数字相同的表示在同一组，大写字母表示是该组的第几个元素

//即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)

//每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)

//排序后结果为：13 27 49 55 4 49 38 65 97 26

//第二次 gap = 5 / 2 = 2

//13 27 49 55 4 49 38 65 97 26

//1A 1B 1C 1D 1E

// 2A 2B 2C 2D 2E

//分为了2组，排序后顺序为4 26 13 27 38 49 49 55 97 65

//第三次 gap = 2 / 2 = 1

//4 26 13 27 38 49 49 55 97 65

//1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

//极1个元素为一组，排序后得到数组：

//4 13 26 27 38 49 49 55 65 97

//

//

//改进1：上面的代码严格按照希尔排序的理解来写，有利于理解希尔排序，但代码量大。优化后，

//以上述例子的第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比

//较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。

//这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序也是正确的。

void ShellSort_2(int arr[],int len)

{

int j,gap;

for(gap=len/2;gap>0;gap/=2)

{

for(j=gap;j<len;j++)

{

int temp=arr[j];

int k=j-gap;

while(k>=0 && arr[k]>temp)

{

arr[k+gap]=arr[k];

k-=gap;

}

arr[k+gap]=temp;

}

}

}

//改进3：继续简化上面的代码，就得到以下

void ShellSort_3(int arr[],int len)

{

int i,j,gap;

for(gap=len/2;gap>0;gap/=2)

{

for(i=gap;i<len;i++)

{

for(j=i-gap;j>=0 && arr[j]>arr[j+gap];j-=gap)

swap(arr[j],arr[j+gap]);

}

}

}

int main()

{

int arr[10]={2,3,4,1,2,11,33,8,7,45};

ShellSort_3(arr,10);

int i;

for(i=0;i<10;i++)

cout<<arr[i]<<endl;

}