shellsort.cpp

附有本人超级详细解释（看不懂的面壁十天！） 一、 实际问题: 希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。它又称“缩小增量分类法”

// ShellSort.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include<iostream.h>
#include <stdio.h>
#include<math.h>

int n;
struct SqList
{
	int r[20];
	int length;
};

void ShellInsert(SqList &L,int dk)//一趟Shell插入排序
{
	L.length =n;
	int i,j;
	for(i=dk+1;i<=L.length;++i) //从后向前逐个插入排序
	if(L.r[i]<L.r[i-dk])
    {
      L.r[0]=L.r[i]; //暂存于L.r[0]
      for(j=i-dk; j>0 && (L.r[0]<L.r[j]);j-=dk)
        L.r[j+dk]=L.r[j]; //记录后移，查找插入位置
      L.r[j+dk]=L.r[0]; //插入
    }
}//ShellInsert

void ShellSort(SqList &Li)//按增量序列dlta[0..t-1]对顺序表作Shell插入排序
{
	int dlta[20];	int t;
	double p,r;
	p=log(n+1)/log(2);
	int k;t=int(p);
	for(k=1;k<=t;++k)
	{
		r=pow(2,t-k+1)-1;
		dlta[k]=int(r);
		cout<<"增量是:"<<dlta[k];  cout<<endl;
		ShellInsert(Li,dlta[k]);
		for(int q=1;q<=n;q++)
			cout<<Li.r[q]<<" ";
		cout<<endl;
	}
}//ShellSort


int main(int argc, char* argv[])
{
	SqList L;
	int i;
	cout<<"请输入序列个数n(小于或等于20): ";
	cin>>n;
	cout<<endl;
	cout<<"请输入一个个数为 "<<n<<" 的无序序列:"<<endl;
	cout<<endl;
	for(i=1;i<=n;i++)
		cin>>L.r[i];
	ShellSort(L);
	return 0;
}