希尔排序(Shell Sort)

基本思想：
　    先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d_l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d₂<d₁重复上述的分组和排序，直至所取的增量d_t=1(d_t<d_t-l<…<d₂<d₁)，即所有记录放在同一组中进行直接插入排序为止。
    　该方法实质上是一种分组插入方法。 

给定实例的shell排序的排序过程

    　假设待排序文件有10个记录，其关键字分别是：
        49，38，65，97，76，13，27，49，55，04。
    　增量序列的取值依次为：
        5，3，1

体会：一个> 或<  符号可能是致命的影响

不太清楚原理最好看看：排序过程如【动画模拟演示】

经过了半天的折腾终于搞定了，下面是我的代码

#include<iostream>
using namespace std;

void ShellSort(int arr[], int len);
void main()
{
	int a[]={49,38,65,97,76,13,27,49,55,04};
	ShellSort(a,10);
	cout<<"排序完成后"<<endl;
	for (int i=0; i<10; i++)
	{
		cout<<a[i]<<endl;
	}
	system("pause");
}

void ShellSort(int arr[], int len)
{
	int j,k,temp;
	j = len/2;
	for (j; j>= 1; j /=2)//确定增量
	{
		for (k =j; k<len;k++)//从数组增量到末尾的判断
		{ 
			
			if (arr[k] < arr[k-j])//对分组的进行插入排序
			{	
				temp = arr[k];
				int s =k-j;
				while (arr[s] > temp)
				{
					arr[s +j] = arr[s];
					s-=j;
				}
				arr[s+j] = temp;
							
			}	
		}
		cout<<"**********"<<"增量"<< j << "**********"<<endl;
		for (int g=0; g<10; g++)
		{
			cout<<arr[g];
			cout<<",";
		}
		cout<<""<<endl;
	}
		
}

希尔排序(Shell Sort)--学习（四）