(完整word版)各种内排序算法的实现及性能比较

实 验 报 告
实验名称 各种内排序算法的实现及性能比较 指导教师
实验类型 设计 实验学时 2 实验时间
一、 实验目的和要求
（1） 理解和掌握各种排序算法。
（2） 学会比较排序方法的性能。

二、
实验环境(实验设备)

硬件：微型计算机
软件：Windows 操作系统、Microsoft Visual Studio 2015

三、实验原理及内容

//改进的快速排序
template
void QuickSort(T A[], int n)
{
QSort(A, 0, n - 1);
}

QuickSort
QSort
A,0,n-1
A,left,right QSort InsertSort A,j-1 A,n
实 验 报 告
template
void QSort(T A[],int left,int right)
{
int i, j;
if (left < right)
{
i = left; j = right + 1;
if (j-i < 10) //如果子集合小于10个元素时改用直接插入排序
InsertSort(A, j-i);
else {
do {
do i++; while (A[i] < A[left]);
do j--; while (A[j] > A[left]);
if (i < j) Swap(A[i], A[j]);
} while (i < j);
Swap(A[left], A[j]);
QSort(A, left, j - 1);
QSort(A, j + 1, right);
}
}
}

//随机数发生器
const int N = 1000;
template
void randomizer(T* a)
{
srand(time(NULL));
for (int i = 0; i < N; i++)
a[i] = rand() % 10000;
}
//各内排序时间计算函数
template
void Showtime(void(*Order)(T A[], int n),T A[])
实 验 报 告
{
double time;
clock_t start, end;
cout << "Total time-consuming: ";
start = clock(); //开始计时
for (int i = 0; i < 1000; i++)
{
Order(A, N);
randomizer(A);
}
end = clock(); //结束计时
time = (double)(end - start) / CLOCKS_PER_SEC; //耗时为两者差值除以clock中每秒的值
cout << time << endl;
}
//main函数中各内排序算法调用函数计算时间的语句段
//简单选择排序时间计算
cout << "\nSelectSort:" << endl;
Showtime(SelectSort, a);

//直接插入排序时间计算
cout << "\nInsertSort:" << endl;
Showtime(InsertSort, a);

//冒泡排序时间计算
cout << "\nBubbleSort:" << endl;
Showtime(BubbleSort, a);

//快速排序时间计算
cout << "\nQuickSort:" << endl;
Showtime(QuickSort, a);
//两路合并排序时间计算
cout << "\nMergeSort:" << endl;
Showtime(MergeSort, a);
实 验 报 告
测试结果如图：

结果表明：速度：改进的快速排序>两路合并排序>直接插入排序>简单选择排序>冒泡排序。
实 验 报 告
四、实验小结（包括问题和解决方法、心得体会、意见与建议等）
(一)实验中遇到的主要问题及解决方法
问题：InsertSort函数模版已被定义的错误。
解决方法：百度错误类型得知，应该是在main.cpp文件中调用头文件QuickSort.h与
InsertSort.h，而QuickSort.h中已经包含了InserSort.h文件。
问题：快速排序的时间反而比冒泡排序的时间长。
解决方法：手工运算代码中的两个排序计算语句段，发现每次调用排序算法函数后没有将随机
数组重新随机生成，而冒泡排序对于已经排序完的数组消耗时间几乎为0，快速排序却要再比较分割。
（二）实验心得
根据实验结果，确实看到了各种内排序算法对随机情况排序速度上的优劣。更加了解了各种内
排序算法的思想。

五、指导教师评语
成 绩 批阅人 日 期