依次的排序算法为 :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) 编辑 收藏 引用