依次的排序算法為 :insertsort,shellsort,mergersort,quicksort,heapsort, countingsort,radixsort,bucketsort. 依照《算法導(dǎo)論》偽代碼實(shí)現(xiàn)。
#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種問(wèn)題規(guī)模
long double counter[5][8];//運(yùn)行時(shí)間記錄
int i=0,j=0;
long k=0;
CTimer time;//計(jì)時(shí)器
ofstream data;//文件寫入
data.open("data.txt");
if (data.fail())
{
cout<<"文件打開(kāi)失敗"<<endl;
exit(1);
}
//*****由5種問(wèn)題規(guī)模(i)和8種排序方法(j)進(jìn)行雙重循環(huán)*****//
for(i=0; i<5 ;i++)
{
unsortA=new unsigned int[LEN[i]];
random(unsortA, LEN[i]);//產(chǎn)生隨機(jī)亂序數(shù)組
//*****將未排序數(shù)組寫入文件*****//
if(i<2)//數(shù)據(jù)量太大,故只寫入pow(2,4), pow(2,8)規(guī)模下的數(shù)據(jù)
{
data<<"第"<<i+1<<"組未排序的數(shù)據(jù):"<<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++)//復(fù)制亂序數(shù)組unsortA
unsortB[k]=unsortA[k];
time.Start();//計(jì)數(shù)開(kāi)始
if (j==2||j==3)//mergersort或者quicksort調(diào)用LEN[i]-1
pSort[j](unsortB,0,LEN[i]-1);//調(diào)用排序算法
else
pSort[j](unsortB,0,LEN[i]);//調(diào)用排序算法
counter[i][j]=time.End();//計(jì)數(shù)結(jié)束
cout<<"runningtime:"<<counter[i][j]<<"ms"<<endl;
//*****將排好序的數(shù)據(jù)寫入文件*****//
if(i<2)//數(shù)據(jù)量太大,故只寫入pow(2,4), pow(2,8)規(guī)模下的數(shù)據(jù)
{
data<<"第"<<i+1<<"組已排好序的數(shù)據(jù):經(jīng)過(guò)第"<<j+1<<"種排序法"<<endl;
for(k=0; k<LEN[i] ; k++)
data<<"unsortB["<<k<<"]:"<<unsortB[k]<<endl;
data<<endl;
}
delete [] unsortB;
}
cout<<endl;
delete [] unsortA;
}
//*****將運(yùn)行時(shí)間數(shù)據(jù)寫入文件*****//
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<<"組運(yùn)行時(shí)間:"<<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;//產(chǎn)生0 ~ 2的16次方之間的隨機(jī)數(shù),
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);//開(kāi)始計(jì)數(shù)
16 }
17 double End()
18 {
19 LARGE_INTEGER CurrentCount;
20 QueryPerformanceCounter(&CurrentCount);//終止計(jì)數(shù)
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/**//***這段代碼對(duì)一個(gè)整型數(shù)組進(jìn)行升序排序，可以看出每個(gè)元素插入到隊(duì)列中經(jīng)過(guò)兩個(gè)步驟：
28 一是挨個(gè)比較，找到自己所在的位置，而是把后面的數(shù)據(jù)全部移位，然后把元素插入。
29要把數(shù)據(jù)插入，移位是必不可少了.因?yàn)橐迦氲年?duì)列已經(jīng)是排序好的，我們可以使用二分法
30來(lái)減少比較的次數(shù)。二分法的時(shí)間復(fù)雜度為O(log 2 n)，而線性查找的復(fù)雜度為O(n)。
31改進(jìn)后的代碼如下：***/
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
哈哈 閱讀(1143)
評(píng)論(3) 編輯 收藏 引用