《数据结构与算法》课程设计
30、排序综合
问题描述：
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
基本要求：
（1）至少采用三种方法实现上述问题求解（提示：可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中；
（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法；
（3）如果采用4种或4种以上的方法者，可适当加分。
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<algorithm>using namespace std;
struct sortTime {
string name; //排序方法名int time; //排序消耗时间
};bool cmpSotTime(sortTime o, sortTime t) {
return o.time < t.time;
}//直接插入排序
void InsertSort(vector<int> &vi, int length) {
int i, j, tmp;for (i = 1; i < length; i++) {
if (vi[i] < vi[i - 1]) {
//反序时tmp = vi[i];j = i - 1;do {
//找 vi[i] 的插入位置vi[j + 1] = vi[j]; //将数据大于 vi[i] 的记录后移j--;} while (j >= 0 && vi[j] > tmp);vi[j + 1] = tmp; //在 j+1 处插入 R[i]}}
}//折半插入排序
void BinInsertSort(vector<int> &vi, int length) {
int i, j, low, high, mid, tmp;for (i = 1; i < length; i++) {
if (vi[i] < vi[i - 1]) {
//反序时tmp = vi[i]; //将 vi[i] 保存到 tmplow = 0, high = i - 1;while (low <= high) {
//在 vi[low...high] 中查找插入的位置mid = (low + high) >> 1; //取中间位置if (tmp < vi[mid]) {
high = mid - 1; //插入点在左半区} else {
low = mid + 1; //插入点在又半区}} //找位置 highfor (j = i - 1; j >= high + 1; j--) {
//集中进行元素后移vi[j + 1] = vi[j];}vi[high + 1] = tmp; //插入 tmp}}
}//希尔排序
void ShellSort(vector<int> &vi, int length) {
int d = 1;while (d < length / 3) {
//设置增量d = 3 * d + 1;}while (d >= 1) {
for (int i = d; i < length; i++) {
//对所有组采用直接插入排序for (int j = i; j >= d && vi[j] < vi[j - d]; j -= d) {
//对相隔 d 个位置一组采用直接插入排序swap(vi[j], vi[j - d]);}}d = d / 3; //减小增量}
}//冒泡排序
void BubbleSort(vector<int> &vi, int length) {
int i, j;bool exchange;for (i = 0; i < length; i++) {
exchange = false; //一趟前 exchange 置为假for (j = length - 1; j > i; j--) {
//归位 vi[i],循环 length-i-1 次if (vi[j] < vi[j - 1]) {
//相邻两个元素反序时swap(vi[j], vi[j - 1]); //将 vi[j] 和 vi[j-1] 两个元素交换exchange = true; //一旦有交换，exchange 置为真}}if (!exchange) {
//本趟没有发生交换，中途结束算法return;}}
}//快速排序
void QuickSort(vector<int> &vi, int l, int r) {
if (l >= r) return;int tmp = vi[(l + r) >> 1], i = l - 1, j = r + 1; //用区间中间元素作为基准while (i < j) {
do i++; while (vi[i] < tmp); //从左向右扫描，找一个大于 tmp 的 vi[i]do j--; while (vi[j] > tmp); //从右向左扫描，找一个小于 tmp 的 vi[j]if (i < j) swap(vi[i], vi[j]); //交换大于 tmp 的 vi[i] 和小于 tmp 的 vi[j]}QuickSort(vi, l, j); //对左区间递归排序QuickSort(vi, j + 1, r); //对右区间递归排序
}//选择排序
void SelectSort(vector<int> &vi, int length) {
int i, j, k;for (i = 0; i < length - 1; i++) {
//做第 i 趟排序k = i;for (j = i + 1; j < length; j++) {
//在当前无序区 vi[i...length-1] 中选数据最小的 vi[k]if (vi[j] < vi[k]) {
k = j; //k 记下目前找到的最小数据所在的位置}}if (k != i) {
//vi[i] 和 vi[k] 两个元素交换swap(vi[i], vi[k]);}}
}//构造大根堆
void sift(vector<int> &vi, int low, int high) {
int i = low, j = 2 * i + 1; //vi[j] 是 vi[i]的左孩子int tmp = vi[i];while (j <= high) {
if (j + 1 <= high && vi[j] < vi[j + 1]) {
//若右孩子较大，把 j 指向右孩子j++;}if (vi[i] > vi[j]) {
//若根结点大于等于最大孩子关键字，筛选结束break;} else {
//若根结点小于最大孩子的关键字swap(vi[i], vi[j]); //将 vi[j] 调整到双亲结点的位置上i = j; //修改 i 和 j 值，以便继续向下筛选j = i * 2 + 1;}}vi[i] = tmp; //被筛选结点放入最终位置上
}//堆排序
void HeapSort(vector<int> &vi, int length) {
for (int i = (length >> 1) - 1; i >= 0; i--) {
//循环建立初始堆，调用 sift 算法 ?n/2? 次sift(vi, i, length - 1);}for (int i = length - 1; i >= 0; i--) {
//进行 n-1 趟完成堆排序，每一趟堆中元素个数减 1swap(vi[0], vi[i]); //将最后一个元素与根 vi[1] 交换sift(vi, 1, i - 1); //对 vi[1...i-1] 进行筛选，得到 i1 个结点的堆}
}//二路归并排序
const int N = 1000010;
int tmp[N];void MergeSort(vector<int> &vi, int l, int r) {
if (l >= r) return;int mid = l + r >> 1; //取中间位置MergeSort(vi, l, mid), MergeSort(vi, mid + 1, r); //递归分组int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r) {
if (vi[i] <= vi[j]) tmp[k++] = vi[i++]; //从小到大加进 tmpelse tmp[k++] = vi[j++];}while (i <= mid) tmp[k++] = vi[i++]; //将剩余元素加进 tmpwhile (j <= r) tmp[k++] = vi[j++]; //将剩余元素加进 tmpfor (i = l, j = 0; i <= r; i++, j++) vi[i] = tmp[j];
}int main() {
srand((unsigned) time(NULL));int length;cout << "请输入随机数的个数：";cin >> length;vector<int> insertArray, binInsertArray, shellArray, bubbleArray, quickArray, selectArray, heapArray, mergeArray;cout << "开始生成随机数...\n";for (int i = 0, t; i < length; i++) {
t = rand();insertArray.push_back(t);binInsertArray.push_back(t);shellArray.push_back(t);bubbleArray.push_back(t);quickArray.push_back(t);selectArray.push_back(t);heapArray.push_back(t);mergeArray.push_back(t);}cout << "随机数生成完毕!\n开始进行排序...\n";clock_t start; //定时器sortTime st[8];start = clock();InsertSort(insertArray, insertArray.size());st[0].name = "直接插入排序", st[0].time = clock() - start;start = clock();BinInsertSort(binInsertArray, binInsertArray.size());st[1].name = "折半插入排序", st[1].time = clock() - start;start = clock();ShellSort(shellArray, shellArray.size());st[2].name = "希尔排序", st[2].time = clock() - start;start = clock();BubbleSort(bubbleArray, bubbleArray.size());st[3].name = "冒泡排序", st[3].time = clock() - start;start = clock();QuickSort(quickArray, 0, quickArray.size() - 1);st[4].name = "快速排序", st[4].time = clock() - start;start = clock();SelectSort(selectArray, selectArray.size());st[5].name = "选择排序", st[5].time = clock() - start;start = clock();HeapSort(heapArray, heapArray.size());st[6].name = "堆排序", st[6].time = clock() - start;start = clock();MergeSort(mergeArray, 0, mergeArray.size() - 1);st[7].name = "二路归并排序", st[7].time = clock() - start;cout << "排序完毕!开始将数据写入文件...\n";//开流ofstream insertSortOutStream("../CurriculumDesign/data/InsertSort.txt", ios::out);ofstream binInsertSortOutStream("../CurriculumDesign/data/BinInsertSort.txt", ios::out);ofstream shellSortOutStream("../CurriculumDesign/data/ShellSort.txt", ios::out);ofstream bubbleSortOutStream("../CurriculumDesign/data/BubbleSort.txt", ios::out);ofstream quickSortOutStream("../CurriculumDesign/data/QuickSort.txt", ios::out);ofstream selectSortOutStream("../CurriculumDesign/data/SelectSort.txt", ios::out);ofstream heapSortOutStream("../CurriculumDesign/data/HeapSort.txt", ios::out);ofstream mergeSortOutStream("../CurriculumDesign/data/MergeSort.txt", ios::out);//写数据insertSortOutStream << "直接插入排序:\n" << "时间消耗:" << st[0].time << "ms\n";binInsertSortOutStream << "折半插入排序:\n" << "时间消耗:" << st[1].time << "ms\n";shellSortOutStream << "希尔排序:\n" << "时间消耗:" << st[2].time << "ms\n";bubbleSortOutStream << "冒泡排序:\n" << "时间消耗:" << st[3].time << "ms\n";quickSortOutStream << "快速排序:\n" << "时间消耗:" << st[4].time << "ms\n";selectSortOutStream << "选择排序:\n" << "时间消耗:" << st[5].time << "ms\n";heapSortOutStream << "堆排序:\n" << "时间消耗:" << st[6].time << "ms\n";mergeSortOutStream << "二路归并排序:\n" << "时间消耗:" << st[7].time << "ms\n";for (int i = 0; i < length; i++) {
insertSortOutStream << insertArray[i] << '\n';binInsertSortOutStream << binInsertArray[i] << '\n';shellSortOutStream << binInsertArray[i] << '\n';bubbleSortOutStream << binInsertArray[i] << '\n';quickSortOutStream << binInsertArray[i] << '\n';selectSortOutStream << binInsertArray[i] << '\n';heapSortOutStream << binInsertArray[i] << '\n';mergeSortOutStream << binInsertArray[i] << '\n';}cout << "数据写入文件完毕!\n";//关流insertSortOutStream.close();binInsertSortOutStream.close();shellSortOutStream.close();bubbleSortOutStream.close();quickSortOutStream.close();selectSortOutStream.close();heapSortOutStream.close();mergeSortOutStream.close();sort(st, st + 8, cmpSotTime);cout << "第一快的排序方法:" << st[0].name << "时间消耗:" << st[0].time << "ms\n";cout << "第二快的排序方法:" << st[1].name << "时间消耗:" << st[1].time << "ms\n";return 0;
}