希爾排序學習手冊

最近打數學建模，其中一個步驟就是對給定的數據按照某個標准進行排序。當時選擇了對其進行希爾排序，故在此寫下學習手冊。

基本思想

將整個待排序記錄分割成若干個子序列，在子序列內分別進行直接插入排序，待整個序列中的記錄基本有序時，對全體記錄進行直接插入排序。

希爾排序是對直接插入排序的改進。我們知道若待排序記錄按關鍵字值基本有序時，直接插入排序的效率可以大大提高。由於直接插入排序算法簡單，則在待排序記錄數量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;
}