C++ 希尔排序

概要:

希尔排序也被称为缩小增量排序,他的名字源于发明者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;
		}
	}
}

来自CSDN博客:希尔排序 http://blog.csdn.net/u011608357/article/details/21318091#

评论关闭
评论 还能输入200
评论关闭
评论 还能输入200
  • 全部评论(0)
资料加载中...
已关注 , 取消