日期：2011-03-22 13:55:00 来源：本站整理

数据构造学习(C++)之排序[VC/C++编程]

赞助商链接

分享到： QQ空间新浪微博腾讯微博人人网

　　本文“数据构造学习(C++)之排序[VC/C++编程]”是由七道奇为您精心收集，来源于网络转载，文章版权归文章作者所有，本站不对其观点以及内容做任何评价，请读者自行判断，以下是其具体内容：

测试程序

背面的例程,都是对数组的排序,利用静态链表的也实用于链表的排序.为简单起见,只对单关键码排序,并且最后的后果都是重新到尾按升序布列.下面是统一的测试程序:

#include <iostream>
#include <iomanip>
using namespace std;
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "InsertSort.h"
#define random(num) (rand() % (num))
#define randomize() srand((unsigned)time(NULL))
#define N 10000 //排序元素的数目
#define SORT InsertSort //排序办法
class timer//单位ms
{
public:
void start() { start_t = clock(); }
clock_t time() { return (clock() - start_t); }
private:
clock_t start_t;
};
int KCN, RMN; timer TIMER;
void test(int a[])
{
TIMER.start();
SORT<int>(a, N, KCN, RMN);
cout << "　　TimeSpared: " << TIMER.time() << "ms" << endl;
cout << "KCN=" << left << setw(11) << KCN;
cout << "KCN/N=" << left << setw(11)<< (double)KCN/N;
cout << "KCN/N^2=" << left << setw(11)<< (double)KCN/N/N;
cout << "KCN/NlogN=" << left << setw(11)<< (double)KCN/N/log((double)N)*log(2.0) << endl;
cout << "RMN=" << left << setw(11) << RMN;
cout << "RMN/N=" << left << setw(11)<< (double)RMN/N;
cout << "RMN/N^2=" << left << setw(11)<< (double)RMN/N/N;
cout << "RMN/NlogN=" << left << setw(11)<< (double)RMN/N/log((double)N)*log(2.0) << endl;
}
int main()
{
int i;
//randomize();为了在相同情形下对比各个排序算法,不加这句
int* ascending = new int[N];//升序序列
int* descending = new int[N];//降序序列
int* randomness = new int[N];//随机序列
for (i = 0; i < N; i++) { ascending[i] = i; randomness[i] = i; descending[i] = N - i - 1;}
for (i = 0; i < N; i++) swap(randomness[i], randomness[random(N)]);
cout << "Sort ascending N=" << N; test(ascending);
cout << "Sort randomness N=" << N; test(randomness);
cout << "Sort descending N=" << N; test(descending);
return 0;
}

需求阐明一点,KCN（关键码对比次数）、RMN（记录移动次数）并非算法必须的,是为了对算法的性能有个直观的评价（不用那些公式算来算去）.对10000个整数排序应当是最费事的测试手段,倡议不要再增添记录数目了,一是在最坏的情形不用等太久的时间,二是避免KCN、RMN溢出,别的有些递归的算法在情形对比糟的时刻,记录数目太多仓库大概会溢出,招致程序崩溃.

　　以上是“数据构造学习(C++)之排序[VC/C++编程]”的内容，如果你对以上该文章内容感兴趣，你可以看看七道奇为您推荐以下文章：

Microsoft SQL Server 7.0数据库设置与数据构造

Java底子:Util包下常用的数据构造介绍

本文地址：