最近打數學建模,其中一個步驟就是對給定的數據按照某個標准進行排序。當時選擇了對其進行希爾排序,故在此寫下學習手冊。
基本思想
將整個待排序記錄分割成若干個子序列,在子序列內分別進行直接插入排序,待整個序列中的記錄基本有序時,對全體記錄進行直接插入排序。
希爾排序是對直接插入排序的改進。我們知道若待排序記錄按關鍵字值基本有序時,直接插入排序的效率可以大大提高。由於直接插入排序算法簡單,則在待排序記錄數量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;
}