实 验 报 告
1． 实验题目
生成若干个随机数（不少于10000个），然后用各种排序方法（至少5个）实现对其排序，并比较各算法所花费的时间。
2． 实验步骤
本程序有sort.h、sort.cpp和TestSort.cpp三个文件组成。其中：
l sort.h：定义了排序的元素类Element和数据表类dataList，用来存储待排序的数据，并且在数据表类里有排序相关的成员函数：直接插入排序InsertSort、折半插入排序BinaryInsertSort、希尔排序ShellSort、起泡排序BubbleSort、快速排序QuickSort、选择排序SelectSort、堆排序HeapSort共7个。
l sort.cpp：对sort.h中定义的成员的实现。
l TestSort.cpp：是对各种排序方法的测试。
(1) 文件Sort.h中的内容
#ifndef SORT_H
#define SORT_H
#include "iostream.h"
#include "assert.h"
#include "time.h"
#include "stdlib.h"
const int DefaultSize = 10000;
template <class Type> class dataList;
template <class Type> class Element{ // 数据表元素类型
private:
Type key; // 关键码
// field otherdata; // 其他数据域
public:
Element( ) { }
Element(Type k): key(k){ }
Type getKey( )const { return key; }
void setKey(const Type x) { key = x; }
Element<Type> &operator=(const Element<Type> &x) { // 赋值
this->key = x.key;
return *this;
}
bool operator==(const Element<Type> &x) { return (key==x.key); } // 判断是否相等
bool operator!=(const Element<Type> &x) { return (key!=x.key); } // 判断是否不等
bool operator>=(const Element<Type> &x) { return (key>=x.key); } // 判断大于等于
bool operator<=(const Element<Type> &x) { return (key<=x.key); } // 判断小于等于
bool operator>(const Element<Type> &x) { return (key > x.key); } // 判断大于
bool operator<(const Element<Type> &x) { return (key < x.key); } // 判断小于
};
template<class Type>class dataList{
private:
Element<Type> *vector, *v_bak; // v_bak 是 vector 的备份
int MaxSize, CurrentSize;
void QuickSort(int left, int right);
int Partition(int left, int right);
void FilterDown(int i, int EndOfHeap);
public:
dataList(int MaxSz = DefaultSize): MaxSize(MaxSz), CurrentSize(0) {
vector = new Element<Type>[MaxSz];
v_bak = new Element<Type>[MaxSz];
assert(vector != NULL && v_bak!=NULL);
}
~dataList( ){ delete vector; delete v_bak; }
void CreateRandData(int ListSize = 0); // 随机产生ListSize个待排序数据
void Restore(void); // 恢复数据，以便下一次排序
void DisplayData(void); // 输出数据
void InsertSort(void);
void BinaryInsertSort(void);
void ShellSort(void);
void BubbleSort(void);
void QuickSort(void); { QuickSort(0, CurrentSize - 1); }
void SelectSort(void);
void HeapSort(void);
};
#include "sort.cpp"
#endif
(2) 文件Sort.cpp中的内容
#ifndef SORT_CPP
#define SOET_CPP
#include "iostream.h"
#include "assert.h"
#include "time.h"
#include "stdlib.h"
#include "sort.h"
template<class Type>
void dataList<Type>::HeapSort(void){
// 调整为一个最大堆
for(int i = (CurrentSize-1)/2; i>=0; i--) FilterDown(i, CurrentSize-1);
// 对表排序
for(i = CurrentSize - 1; i>=1; i--) {
Element<Type> temp = vector[i];
vector[i] = vector[0];
vector[0] = temp;
FilterDown(0, i-1);
}
}
template<class Type>
void dataList<Type>::FilterDown(int i, int EndOfHeap){
int child = 2*i+1;
Element<Type> temp = vector[i];
while(child <= EndOfHeap){
if(child < EndOfHeap && vector[child] < vector[child+1]) child = child + 1;
if(temp >= vector[child]) break;
else{vector[i] = vector[child]; i = child; child = 2*i+1; }
}
vector[i] = temp;
}
template<class Type>
void dataList<Type>::SelectSort(void){
for(int i = 1; i < CurrentSize; i++){
int k = i - 1;
for(int j = i; j < CurrentSize; j++) if(vector[j] > vector[k]) k = j;
if(k!=(i-1)){
Element<Type> temp = vector[i-1];
vector[i-1] = vector[k];
vector[k] = temp;
}
}
}
template<class Type>
void dataList<Type>::ShellSort(void){
int gap = CurrentSize/2;
while(gap){
for(int i = gap; i < CurrentSize; i++){
Element<Type> temp = vector[i];
for(int j = i; j >= gap && temp < vector[j-gap]; j-=gap) vector[j] = vector[j-gap];
vector[j] = temp;
}
gap = (gap==2 ? 1 : gap/2);
}
}
template<class Type>
int dataList<Type>::Partition(int left, int right){
int pivotpos = left;
Element<Type> pivot = vector[left], temp;
for(int i = left + 1; i <= right; i++)
if(vector[i] < pivot && ++pivotpos != i)
{ temp = vector[i]; vector[i] = vector[pivotpos]; vector[pivotpos] = temp; }
temp = vector[left];
vector[left] = vector[pivotpos];
vector[pivotpos] = temp;
return pivotpos;
}
template<class Type>
void dataList<Type>::QuickSort(int left, int right){
if(left < right) {
int pivotpos = Partition(left, right);
QuickSort(left, pivotpos - 1);
QuickSort(pivotpos + 1, right);
}
}
template<class Type>
void dataList<Type>::BubbleSort(void){
bool exchange = true; // false 时结束循环
for(int i = 1; i < CurrentSize && exchange; i++){
exchange = false;
for(int j = CurrentSize - 1; j >= i; j--){
if(vector[j] < vector[j-1]){
Element<Type> temp = vector[j];
vector[j] = vector[j-1];
vector[j-1] = temp;
exchange = true;
}
}
}
}
template<class Type>
void dataList<Type>::BinaryInsertSort(void){
for(int i = 1; i < CurrentSize; i++){
int left = 0, right = i-1;
while(left <= right){
int mid = (left + right)/2;
if(vector[i] < vector[mid]) right = mid - 1;
else left = mid + 1;
}
Element<Type> temp = vector[i];
for(int k = i - 1; k>=left; k--) vector[k+1] = vector[k];
vector[left] = temp;
}
}
template<class Type>
void dataList<Type>::InsertSort(void){
for(int i = 1; i < CurrentSize; i++)
for(int j = i; j > 0 && vector[j] < vector[j-1]; j--){
Element<Type> temp = vector[j];
vector[j] = vector[j-1];
vector[j-1] = temp;
}
}
template<class Type>
void dataList<Type>::Restore(void){
for(int i = 0; i < CurrentSize; i++) vector[i] = v_bak[i];
}
template<class Type>
void dataList<Type>::DisplayData(void){
for(int i = 0; i < CurrentSize; i++) cout<<vector[i].getKey( )<<' ';
cout<<endl;
}
template<class Type>
void dataList<Type>::CreateRandData(int ListSize){
assert(ListSize<=MaxSize);
srand((unsigned)time(NULL));
for(int i = 0; i < ListSize; i++){
Type k = (rand( )%30000)-10000;
vector[i].setKey(k); v_bak[i].setKey(k);
}
CurrentSize = ListSize;
}
#endif
(3) 文件TestSort.cpp中的内容
#include "iostream.h"
#include "sort.h"
#include <time.h>
const int SortNum = 7;
const int ListLength = 20000;
void main(void){
time_t start, stop;
dataList<int> L(ListLength);
L.CreateRandData(ListLength);
// cout<<"\n随机生成的数据为："<<endl;
// L.DisplayData( );
// 1. 直接插入排序
start = clock( ); L.InsertSort( ); stop = clock( );
cout<<"直接插入排序："<<start<<','<<stop<<','<<stop - start<<endl;
// 2. 折半插入排序
L.Restore( ); start = clock( ); L.BinaryInsertSort( ); stop = clock( );
cout<<"折半插入排序："<<start<<','<<stop<<','<<stop - start<<endl;
// 3. 希尔排序
L.Restore( ); start = clock( ); L.ShellSort( ); stop = clock( );
cout<<"希尔排序："<<start<<','<<stop<<','<<stop - start<<endl;
// 4. 起泡排序
L.Restore( ); start = clock( ); L.BubbleSort( ); stop = clock( );
cout<<"起泡排序："<<start<<','<<stop<<','<<stop - start<<endl;
// 5. 快速排序
L.Restore( ); start = clock( ); L.QuickSort( ); stop = clock( );
cout<<"快速排序："<<start<<','<<stop<<','<<stop - start<<endl;
// 6. 选择排序
L.Restore( ); start = clock( ); L.SelectSort( ); stop = clock( );
cout<<"选择排序："<<start<<','<<stop<<','<<stop - start<<endl;
// 7. 堆排序
L.Restore( ); start = clock( ); L.HeapSort( ); stop = clock( );
cout<<"堆排序："<<start<<','<<stop<<','<<stop - start<<endl;
}
3． 程序测试
图1 运行结果
本试验在[-10000, 20000]上随机选取了10000个整数，测试结果如上图（各排序方法后有三个正整数，其中，第一个数表示开始排序的时间，第二个数表示排序结束的时间，第三个数表示排序所用的时间）。
经过多次试验，其结果大致类似：希尔排序、快速排序和堆排序有较高的效率；起泡排序时间效率最差；其他排序方法介于这两者之间。
4． 分析
图2 明确任务
图3 过程分析