希尔排序学习手册

最近打数学建模，其中一个步骤就是对给定的数据按照某个标准进行排序。当时选择了对其进行希尔排序，故在此写下学习手册。

基本思想

将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。

希尔排序是对直接插入排序的改进。我们知道若待排序记录按关键字值基本有序时，直接插入排序的效率可以大大提高。由于直接插入排序算法简单，则在待排序记录数量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]<<"\t";
 }
 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]<<"\t";
 }

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;
}