《数据结构》
课 程 设 计 报 告
（期末考查）
学院（系）：
班 级：
学生姓名： 学号
成绩：
时间： 年 月 日
课程设计报告内容
一、课程设计分析（包括问题描述；算法描述；运行结果分析）
二、源程序清单及结果（要有良好的编程风格，主要语句要有注释）
目 录
课程设计题一 ............................................................................................3
问题描述 ..............................................................................................3
算法描述 ..............................................................................................3
课程设计题二 ..........................................................................................17
问题描述 ............................................................................................17
算法描述 ............................................................................................19
课程设计题一
利用随机函数产生 30000 个随机整数，利用插入排序、希尔排序、起泡排序、
快速排序、选择排序、归并排序等排序方法进行排序，并统计每一种排序上机所
花费的时间。
问题描述
根据题目所述，我需要：
（1） 利用随机函数产生 30000 个随机整数，形成整形数组。
（2） 编写插入排序、希尔排序、起泡排序、快速排序、选择排序、归并排序等
排序方法。
（3） 基于每一种编写的分类方法，对数组进行排序，并统计所花费的事件。
（4） 对比分析每一种排序方法。
算法描述
（1）对于随机数数组，可以使用 `#include <stdlib.h>` 提供的 rand()函数生成，
如下：
// 生成随机数
std::vector<int> randNum;
for (int i = 0; i < 30000; i++)
{
randNum.push_back(rand());
}
（2）排序算法分析：
排序是编程过程中经常遇到的操作，它在很大程度上影响了程序的执行效率。
七种常见的排序算法为：
1. 选择排序
2. 冒泡排序
3. 插入排序
4. 有堆排序
5. 希尔排序
6. 归并排序
7. 快速排序
本次实验，我将使用 C++来编写并运用这七种排序算法进行对比分析。首先，我
以命名空间的形式在头文件声明所有的排序算法接口。
namespace Sort
{
/**
* 冒泡排序
*/
void bubbleSort(std::vector<int> &data);
/**
* 堆排序
*/
void heapSort(std::vector<int> &data);
/**
* 插入排序
*/
void insertionSort(std::vector<int> &data);
/**
* 归并排序
*/
void mergeSort(std::vector<int> &data);
/**
* 快速排序
*/
void quickSort(std::vector<int> &data);
/**
* 选择排序
*/
void selectionSort(std::vector<int> &data);
/**
* 希尔排序
*/
void shellSort(std::vector<int> &data);
};
所有排序算法统一接口，这也为统计时间的函数相统一。
① 对于冒泡排序：
1. 算法原理：依次比较相邻的数据，将小数据放在前，大数据放在后；即第一
趟先比较第 1 个和第 2 个数，大数在后，小数在前，再比较第 2 个数与第 3 个数，
大数在后，小数在前，以此类推则将最大的数"滚动"到最后一个位置；第二趟则
将次大的数滚动到倒数第二个位置......第 n-1(n 为无序数据的个数)趟即能完成排
序。
2. 分析：冒泡排序的平均时间复杂度为 O(N^2)，整体效率并不高，比较适合做
小数据排序。空间复杂度是 O(1)，用于交换。稳定性为稳定。我们可以进一步
优化，用一个标记来记录在一趟的比较过程中是否存在交换，如果不存在交换则
整个数组已经有序退出排序过程，反之则继续进行下一趟的比较。
3. 代码实现：如下。
void Sort::bubbleSort(std::vector<int> &data)
{
bool flag;
for (int end = data.size() - 1; end >= 0; end--)
{
flag = false;
for (int i = 0; i < end; i++)
{
// 将大的值向后移
if (data[i] > data[i + 1])
{
std::swap(data[i], data[i + 1]);
flag = true;
}
}
