希尔排序学习手册

最近打数学建模，其中一个步骤就是对给定的数据按照某个标准进行排序。当时选择了对其进行希尔排序，故在此写下学习手册。基本思想将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。希尔排序是对直接插入排序的改进。我们知道若待排序记录按关键字值基本有序时，直接插入排序的效率可以大大提高。由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。算法伪代码void ShellSort（int n, LIST A）
{ int i, j, d; for （d=n/2; d>=1; d=d/2） {
for （i=d+1; i<=n; i++） { //将A[i]插入到所属的子序列中
A[0].key= A[i].key; //暂存待插入记录
j=i-d; //j指向所属子序列的最后一个记录
while （j>0 && A[0].key< A[j].key） { A[j+d]= A[j]; //记录后移d个位置
j=j-d; //比较同一子序列的前一个记录
}
A[j+d]= A[0];
}
}
}算法时间复杂度分析希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快希尔排序的时间性能在O（n2）和O（nlog2n）之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O（n1.3 ）。算法具体实现// hillsorting.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include"iostream"
#include"math.h"
#include"time.h"
#define maximum 1000
using namespace std;
typedef int shell;
shell increase[maximum];
shell decrease[maximum];
shell random[maximum];
shell repeat[maximum];
shell increasette=10;
shell decreasette=100000;
shell repeatette=50000;
void shellsort（shell* samplesaary,shell number）
{
int j;
for （int d = number/2; d>=1; d/=2）
{
for （int i = d+1; i <=number; i++）
{
samplesaary[0]=samplesaary[i];
j=i-d;
while （j>0&&samplesaary[j]>samplesaary[0]）
{
samplesaary[j+d]=samplesaary[j];
j-=d;
}
samplesaary[j+d]=samplesaary[0];
}
}
}
int _tmain（int argc, _TCHAR* argv[]）
{
clock_t begin_time;
clock_t end_time;
for （int i = 1; i < maximum; i++）
{
srand（increasette）;
increase[i]=increasette;
increasette+=rand（）%50;
decrease[i]=decreasette;
decreasette-=rand（）%70;
random[i]+=increase[i]/2+decrease[i]/4+rand（）%10000;
repeat[i]=repeatette+pow（-1,i）*（rand（）%60）;
}
cout<<"increase: "<<endl;
begin_time=clock（）;
shellsort（increase,maximum）;
end_time=clock（）; for （int i = 1; i < maximum; i++）
{
cout<<increase[i]<<" ";
}
cout<<"running time:"<<（long double）（end_time-begin_time）*1000000000/CLOCKS_PER_SEC<<"us"<<endl;
cout<<"decrease: "<<endl;
begin_time=clock（）;
shellsort（decrease,maximum）;
end_time=clock（）; for （int i = 1; i <maximum; i++）
{
cout<<decrease[i]<<" ";
} cout<<"running time:"<<（double）（end_time-begin_time）*1000000000/CLOCKS_PER_SEC<<"us"<<endl;
cout<<"random: "<<endl;
begin_time=clock（）;
shellsort（random,maximum）;
end_time=clock（）;
cout<<"running time:"<<（double）（end_time-begin_time）*1000000000/CLOCKS_PER_SEC<<"us"<<endl;
cout<<"repeat:"<<endl;
begin_time=clock（）;
shellsort（repeat,maximum）;
end_time=clock（）;
cout<<"running time:"<<（long double）（end_time-begin_time）*1000000000/CLOCKS_PER_SEC<<"us"<<endl;
getchar（）;
getchar（）;
getchar（）;
getchar（）;
return 0;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-11/137535.htm