希尔排序

    希尔排序也被称为缩小增量排序，他的名字源于发明者Donald Shell,希尔排序是插入排序的一种，是对插入排序的改进。希尔排序的思想是选取增量h1,h2,h3…hk,首先使用h1作为间隔，把数组分成h1组，对每一组的数据进行插入排序，然后使用h2,h3…进行分组，插入排序，知道增量变为1。本文程序选取的增量序列为数组长度的一半，以后每次减半，直到增量为1.

希尔排序是不稳定的排序方法。

希尔排序的时间复杂度与增量序列有关，希尔增量排序的时间复杂度为O(n^2),而Hibbard增量的希尔排序时间复杂度为O(n^1.5).

假设有数组a[10]={25,46,21,4,65,3,0,91,23,8},排序的过程是：

第一趟：增量为5     3,0,21,4,65,25,46,91,23,8

第二趟：增量为2     3,0,21,4,23,8,46,25,65,91

第三趟：增量为1     0,3,4,8,21,23,25,46,65,91

希尔排序的程序为：

# include <iostream>
using namespace std;
# include <stdlib.h>
int main()
{   void shellsort(int a[],int n);
	int i=0;
	int a[10]={25,46,21,4,65,3,0,91,23,8};
	shellsort(a,10);
	for(;i<10;i++)
		cout<<a[i]<<endl;
	system("pause");
	return 0;
}


void shellsort(int a[],int n) // 希尔排序
{
int cri=n/2;
int i,j;
int tmp;
for(cri=n/2;cri>0;cri/=2)     //增量起始值为N/2,之后逐次减半
{
for(i=cri;i<n;i++)
{
tmp=a[i];
for(j=i;j>=cri;j-=cri)
{
	if(a[j-cri]>tmp)
        a[j]=a[j-cri];
	else 
		break;
}
a[j]=tmp;
}
}
}

希尔排序,布布扣,bubuko.com

希尔排序

原文：http://blog.csdn.net/u011608357/article/details/21318091