依次的排序算法為 :insertsort,shellsort,mergersort,quicksort,heapsort, countingsort,radixsort,bucketsort. 依照《算法導論》偽代碼實現。
#include "randomizer.h"
#include "insertsort.h"
#include "heapsort.h"
#include "mergersort.h"
#include "shellsort.h"
#include "quicksort.h"
#include "countingsort.h"
#include "radixsort.h"
#include "bucketsort.h"
#include "CTimer.h"
#include<iostream>
#include<fstream>
#include<cmath>
typedef unsigned int * IntArrayPtr;
using namespace std;
int main()
{
IntArrayPtr unsortA,unsortB;
void (*pSort[])(unsigned int *,long,long)=
{&insertsort,&shellsort,&mergersort,&quicksort,
&heapsort,&countingsort,&radixsort,&bucketsort};//8種排序算法
unsigned long LEN[5]={pow(2,4), pow(2,8),pow(2,12),pow(2,16),pow(2,20)};//5種問題規模
long double counter[5][8];//運行時間記錄
int i=0,j=0;
long k=0;
CTimer time;//計時器
ofstream data;//文件寫入
data.open("data.txt");
if (data.fail())
{
cout<<"文件打開失敗"<<endl;
exit(1);
}
//*****由5種問題規模(i)和8種排序方法(j)進行雙重循環*****//
for(i=0; i<5 ;i++)
{
unsortA=new unsigned int[LEN[i]];
random(unsortA, LEN[i]);//產生隨機亂序數組
//*****將未排序數組寫入文件*****//
if(i<2)//數據量太大,故只寫入pow(2,4), pow(2,8)規模下的數據
{
data<<"第"<<i+1<<"組未排序的數據:"<<endl;
for(k=0; k<LEN[i] ; k++)
data<<"unsortA["<<k<<"]:"<<unsortA[k]<<endl;
data<<endl;
}
for(j=0; j<8; j++)
{
unsortB=new unsigned int[LEN[i]];
for(k=0; k<LEN[i]; k++)//復制亂序數組unsortA
unsortB[k]=unsortA[k];
time.Start();//計數開始
if (j==2||j==3)//mergersort或者quicksort調用LEN[i]-1
pSort[j](unsortB,0,LEN[i]-1);//調用排序算法
else
pSort[j](unsortB,0,LEN[i]);//調用排序算法
counter[i][j]=time.End();//計數結束
cout<<"runningtime:"<<counter[i][j]<<"ms"<<endl;
//*****將排好序的數據寫入文件*****//
if(i<2)//數據量太大,故只寫入pow(2,4), pow(2,8)規模下的數據
{
data<<"第"<<i+1<<"組已排好序的數據:經過第"<<j+1<<"種排序法"<<endl;
for(k=0; k<LEN[i] ; k++)
data<<"unsortB["<<k<<"]:"<<unsortB[k]<<endl;
data<<endl;
}
delete [] unsortB;
}
cout<<endl;
delete [] unsortA;
}
//*****將運行時間數據寫入文件*****//
data<<endl<<"依次的排序算法為:insertsort,shellsort,mergersort,quicksort,heapsort,countingsort,radixsort,bucketsort."<<endl;
for(i=0; i<5; i++)
for(j=0; j<8; j++)
data<<"第"<<i<<"組運行時間:"<<counter[i][j]<<endl;
data<<endl;
return 0;
}
1#ifndef RANDOMIZER_H
2#define RANDOMIZER_H
3
4#define MAXNUM 65536
5
6#include<iostream>
7#include<time.h>
8using namespace std;
9
10
11void random(unsigned int unsort[],long len)
12{
13 srand((unsigned) time(NULL));
14 for(long i=0; i<len; i++)
15 unsort[i] =2*rand()%MAXNUM;//產生0 ~ 2的16次方之間的隨機數,
16 //正好是unsigned int型的取值范圍
17}
18
19
20
21#endif//RANDOMIZER_H
1#ifndef CTIMER_H
2#define CTIMER_H
3
4#include "Windows.h"
5
6class CTimer
7{
8public:
9 CTimer()
10 {
11 QueryPerformanceFrequency(&m_Frequency);//取CPU頻率
12 }
13 void Start()
14 {
15 QueryPerformanceCounter(&m_StartCount);//開始計數
16 }
17 double End()
18 {
19 LARGE_INTEGER CurrentCount;
20 QueryPerformanceCounter(&CurrentCount);//終止計數
21 return
22 double(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart*1000;
23
24 }
25private:
26 LARGE_INTEGER m_Frequency;
27 LARGE_INTEGER m_StartCount;
28};
29
30#endif//CTIMER_H
1#ifndef INSERTSORT_H
2#define INSERTSORT_H
3
4
5#include<iostream>
6using namespace std;
7
8
9/**//*
10void insertsort(unsigned int A[],long,long len)
11{
12 for(long j=1; j<len ;j++)
13 {
14 unsigned int key=A[j];
15 long i=j-1;
16 while (i>=0 && A[i]>key)
17 {
18 A[i+1]=A[i];
19 i--;
20 }
21 A[i+1]=key;
22 }
23}
24*/
25
26
27/**//***這段代碼對一個整型數組進行升序排序，可以看出每個元素插入到隊列中經過兩個步驟：
28 一是挨個比較，找到自己所在的位置，而是把后面的數據全部移位，然后把元素插入。
29要把數據插入，移位是必不可少了.因為要插入的隊列已經是排序好的，我們可以使用二分法
30來減少比較的次數。二分法的時間復雜度為O(log 2 n)，而線性查找的復雜度為O(n)。
31改進后的代碼如下：***/
32
33int compare(unsigned int a,unsigned int b)
34{
35 return a<b?-1:a==b?0:1;
36}
37
38int binsearch(unsigned int A[], unsigned int key,long p, long r)//二分查找
39{
40 long middle;
41 while (p <= r)
42 {
43 middle = (p + r) / 2;
44<img id=Codehighlighter1_730_833_Open_Image onclick="this.style.display='none'; Codehighlighter1_730_833_Open_Text.style.display='none'; C%2
posted on 2006-11-04 11:48
哈哈 閱讀(1138)
評論(3) 編輯 收藏 引用