依次的排序算法为 :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"
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include<iostream>
#include<fstream>
#include<cmath>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef unsigned int * IntArrayPtr;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
IntArrayPtr unsortA,unsortB;
void (*pSort[])(unsigned int *,long,long)=
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{&insertsort,&shellsort,&mergersort,&quicksort,
&heapsort,&countingsort,&radixsort,&bucketsort};//8种排序算法
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cout<<"文件打开失败"<<endl;
exit(1);
}
//*****由5种问题规模(i)和8种排序方法(j)进行双重循环*****//
for(i=0; i<5 ;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
unsortA=new unsigned int[LEN[i]];
random(unsortA, LEN[i]);//产生随机乱序数组
//*****将未排序数组写入文件*****//
if(i<2)//数据量太大,故只写入pow(2,4), pow(2,8)规模下的数据
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)规模下的数据
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
1
#ifndef RANDOMIZER_H
2
#define RANDOMIZER_H
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
#define MAXNUM 65536
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
#include<iostream>
7
#include<time.h>
8
using namespace std;
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11
void random(unsigned int unsort[],long len)
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
21
#endif//RANDOMIZER_H
1
#ifndef CTIMER_H
2
#define CTIMER_H
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
#include "Windows.h"
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
class CTimer
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8
public:
9
CTimer()
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
11
QueryPerformanceFrequency(&m_Frequency);//取CPU频率
12
}
13
void Start()
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
15
QueryPerformanceCounter(&m_StartCount);//开始计数
16
}
17
double End()
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
19
LARGE_INTEGER CurrentCount;
20
QueryPerformanceCounter(&CurrentCount);//终止计数
21
return
22
double(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart*1000;
23
24
}
25
private:
26
LARGE_INTEGER m_Frequency;
27
LARGE_INTEGER m_StartCount;
28
};
29![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
30
#endif//CTIMER_H
1
#ifndef INSERTSORT_H
2
#define INSERTSORT_H
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
#include<iostream>
6
using namespace std;
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
10
void 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
26![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//***这段代码对一个整型数组进行升序排序,可以看出每个元素插入到队列中经过两个步骤:
28
一是挨个比较,找到自己所在的位置,而是把后面的数据全部移位,然后把元素插入。
29
要把数据插入,移位是必不可少了.因为要插入的队列已经是排序好的,我们可以使用二分法
30
来减少比较的次数。二分法的时间复杂度为O(log 2 n),而线性查找的复杂度为O(n)。
31
改进后的代码如下:***/
32![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
33
int compare(unsigned int a,unsigned int b)
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
35
return a<b?-1:a==b?0:1;
36
}
37![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
38
int binsearch(unsigned int A[], unsigned int key,long p, long r)//二分查找
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
40
long middle;
41
while (p <= r)
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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
哈哈 阅读(1135)
评论(3) 编辑 收藏 引用