首页 > 代码库 > 排序算法及其比较--数据结构课设
排序算法及其比较--数据结构课设
排序算法及其比较
课程设计报告
一、 设计内容
编程实现希尔、快速、堆排序、归并排序算法，并利用程序统计每种算法的执行时间。要求随机产生10000（或50000、 100000、 200000，由用户选择）个数据存入数据文件，然后读数据文件，分别采用不同排序方法进行排序，将结果存入另一个文件中。
二、 设计思想描述
1. 总思想
本程序采用模块化设计思想，分为产生随机数模块，计时模块，写入磁盘模块，读出磁盘模块，希尔排序模块，快速排序模块，堆排序模块，归并排序模块，计时模块。对常见的4 种经典排序算法希尔、快速、堆排序、归并排序进行实现，并根据待排数据个数的不同来对各种排序算法的执行时间进行比较，从而比较出在不同的情况下各排序算法的性能。
2. 模块介绍
【随机数模块】通过rand()函数实现，为防止每次随机数一样，用srand(time(NULL)) 设置时间种子，得到的随机数写入磁盘。
【计时模块】计时函数使用了Windows API 函数QueryPerformanceFrequency（返回硬件支持的高精度计数器的频率。） 和QueryPerformanceCounter （用于得到高精度计时器的值）来实现毫秒级的计时功能。
【写入磁盘模块】主要通过定义ofstream outfile对象来实现。
【读出磁盘模块】主要通过定义ifstream infile对象来实现。
【希尔排序模块】Shell排序又称缩小增量排序，属插入类排序法。它的基本思想是：先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。Shell是针对普通插入排序的缺陷进行的改进。
【快速排序模块】 快速排序是对气泡排序的一种改进。它的基本思想是：首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。
【堆排序模块】堆排序是简单选择排序的一种改进，它的基本思想是：利用堆结构的特点，以一维数组来存储这个堆，将堆调整为大（小）顶堆，然后取出堆顶元素，余下的继续调整为大（小）顶堆，如此直到取出所有元素，排序完成。
【归并排序模块】归并排序的前提是待排记录的两个子表分别有序，然后将其归并至一个有序的新表中，归并前的有序子表也是归并排序的结果。从最原始的只含一个元素的两子表，可看成有序的，经上述归并完成最终排序。
三、 程序结构
【分发包说明】
文件名 | 说明 |
Data1.txt | 存放随机生成数的文本 |
Data2.txt | 存放已排序数的文本 |
main.cpp | C++源文件，包含主程序界面的实现 |
Operation.h | 头文件，包含随机生成数、计时、读写文件等操作 |
Sort.h | 头文件，包含四种排序算法 |
课设报告1 | 本文档 |
【主程序设计】
【流程图】
四、 使用说明(测试案例)
【系统环境】
【使用说明】
一开始：打印使用说明
选择1 ：产生随机数并存入文档，设定数据个数为10000
选择2 ：读取待排序数据
选择3：排序，并计算四种算法所用的时间，以作比较
选择4 ：将结果存入新的文档中
此时，到文件夹中打开Data1.txt及Data2.txt会看到数据。
完毕。
五、 排序算法比较
当数据分别有10000、20000、30000、50000、100000个时，各个算法所用时间如下：
n = 10000：
n = 20000：
做成【折线图】为：
六、 设计中遇到的问题及其解决方案
1. 用const修饰变量的好处
const是一个C语言的关键字，它限定一个变量不允许被改变。使用const在一定程度上可以提高程序的安全性和可靠性。另外，在观看别人代码的时候，清晰理解const所起的作用，对理解对方的程序也有一些帮助。[出自百度百科]
例如，在写入磁盘函数中：const char *file_name，告诉编译器在这个函数中，file_name不能被修改，防止我们无意的修改。
2. 精确计时函数
在定时前应该先调用QueryPerformanceFrequency()函数获得机器内部计时器的时钟频率。接着在需要严格计时的事件发生前和发生之后分别调用QueryPerformanceCounter()，利用两次获得的计数之差和时钟频率，就可以计算出事件经历的精确时间。
附上源代码：
//main.cpp#include <iostream>#include <fstream>#include <cctype>#include <cstdlib>#include "time.h"#include "Sort.h"#include "Operation.h"using namespace std;//声明int Menu( );void Control( );int main(){ cout<<" 【欢迎使用本排序程序.】\n\n"; Sleep(2000); //停留2秒 cout<<"【您有5秒钟的时间浏览使用说明...】\n\n"; Sleep(1000); cout<<"【本程序会随机产生n个数，存入Data1.txt文件中，再从文件中读取数据，\n"; cout<<"利用四种排序（希尔、快速、堆、归并排序）算法对待排数据排序，并将结\n"; cout<<"果存入Data2.txt文件中。】\n"; Sleep(5000); cout<<"【请根据菜单提示 按步执行...】\n"; Sleep(1000); Control( ); return 0;}//菜单int Menu( ){ cout<<"+------------------------------+\n"; cout<<"1...产生随机数 存入磁盘文件\n"; cout<<"2...从文件读数据\n"; cout<<"3...执行排序\n"; cout<<"4...结果存入文件\n"; cout<<"0...退出\n"; cout<<"+------------------------------+\n"; cout<<"Please input your choice: "; int choice; cin>>choice; cout<<endl; return choice;}void Control( ){ //数据准备 int *array_cin; //待排数组 int *array_cout; //排好序的数组 int sort_time[4] = { 0 }; //记录给算法的用时 int n; //个数 while(1) { int choice = Menu(); if(choice == 0) break; switch(choice) { case 1: cout<<"【请输入待排数据的个数, 例如10000, 20000, 50000....】 "; cin>>n; cout<<endl; array_cin = new int[n]; array_cout = new int[n]; GetRandom(array_cin, n); cout<<"【随机产生"<<n<<"个数据 OK...】\n\n"; MyCout(array_cin, n, "Data1.txt"); cout<<"【数据存入Data1.txt文档 OK...】\n\n"; break; case 2: MyCin(array_cin, n, "Data1.txt"); cout<<"【读入数据 OK...】\n\n"; break; case 3: sort_time[0] = GetTime(ShellSort, array_cin, array_cout,n); sort_time[1] = GetTime(QuickSort, array_cin, array_cout,n); sort_time[2] = GetTime(HeapSort, array_cin, array_cout,n); sort_time[3] = GetTime(MergeSort, array_cin, array_cout,n); cout << "待排数据已经排序，各排序算法的执行时间已分别被记录." << endl; cout<<endl<<"4种排序算法的执行时间分别为:"<<endl; ShowTime(sort_time, 4); cout << endl; break; case 4: MyCout(array_cout, n, "Data2.txt"); cout << "【结果存入Data2.txt文档 OK...】\n\n"; //清除数据 //delete array_cin; //delete array_cout; cout<<endl; Sleep(1000); break; default: cout<<"【输入选择错误！！】\n"; Sleep(10000); }//switch }//while}//Control//Operation.h 操作函数：读文件 写文件 产生随机数 精确计时 等#include <windows.h>#include <iostream>#include <fstream>#include "time.h"using namespace std;//************************产生随机数*****************************void GetRandom(int *data, const int n){ srand(time(NULL)); //随机生成n个随机数 for(int i=1; i<=n; i++) data[i] = rand();}//************************写文件*********************************void MyCout(int *data, int n, const char *file_name){ fstream fout; fout.open(file_name,ios::out); if(fout.is_open()) { fout<<"*********\n"; fout<<"*********\n"; for(int i=1;i<=n;i++) { fout<<data[i]<<" "; if(i%10 == 0) fout<<‘\n‘; }//for }//if fout<<endl; fout.close();}//************************读文件**********************************void MyCin(int data[], int n, const char *file_name){ fstream fin; fin.open(file_name,ios::in); if(fin.is_open()) { for(int i=1;i<=n;i++) { fin>>data[i]; } } fin.close();}//**************************精确计时******************************8int GetTime(void (*fpt)(const int *array_to_sort, int *sorted_array, const int n), const int *array_to_sort, int *sorted_array, const int n) { LARGE_INTEGER iLarge; //获得频率 QueryPerformanceFrequency( &iLarge ); double dbFreq = (double) iLarge.QuadPart; //获得开始时间 QueryPerformanceCounter( &iLarge ); double dbBegin = (double) iLarge.QuadPart; //执行排序算法 fpt(array_to_sort, sorted_array, n); //获得结束时间 QueryPerformanceCounter( &iLarge ); double dbEnd = (double) iLarge.QuadPart; //计算用时 int nms = (int) (( dbEnd - dbBegin ) * 1000.0 / dbFreq ); return nms;}//**************************打印时间***************************************void ShowTime(int array_to_show[], const int n) { char *name[4] = { "Shell Sort", "Quick Sort", "Heap Sort", "Merge Sort"}; //显示时间 for (int i = 0; i < n; i++) { cout <<" 【"<<name[i] << ":" << array_to_show[i] << " ms 】"<<endl; }}//Sort.h 排序函数：希尔排序 快速排序 堆排序 归并排序#include <iostream>using namespace std;//*****************希尔排序***********************void shellsort(int data[], int n){ for(int d=n/2,c=1; d>=1; d=d/2,c++) //以增量为d进行直接插入排序 { for(int i=d+1; i<=n; i++) { data[0] = data[i]; //暂存被插入记录 for(int j=i-d; j>0&&data[0]<data[j]; j=j-d) data[j+d] = data[j]; //记录后移d个位置 data[j+d] = data[0]; } } }//**主调函数**void ShellSort(const int *array_to_sort, int *sorted_array, const int n) { for (int i = 0; i < n; i++) sorted_array[i] = array_to_sort[i]; shellsort(sorted_array, n);}//*****************快速排序***********************int Partition(int data[], int first, int end){ int i = first, j = end; //初始化 while(i<j) { while(i<j && data[i]<=data[j]) j--; //右侧扫描 if(i<j) //将较小记录交换到前面 { int temp = data[i]; data[i] = data[j]; data[j] = temp; i++; } while(i<j && data[i]<=data[j]) i++; //左侧扫描 if(i<j) //将较大记录交换到后面 { int temp = data[i]; data[i] = data[j]; data[j] = temp; j--; } }//while return i; //i为轴值记录的最终位置}void quicksort(int data[], int first, int end){ int c=0; if(first < end) { int pivot = Partition(data,first,end); quicksort(data,first,pivot-1); //递归地对左侧子序列进行快速排序 quicksort(data,pivot+1,end); //递归地对右侧子序列进行快速排序 c++; } }//**主调函数**void QuickSort(const int *array_to_sort, int *sorted_array, const int n) { for (int i = 0; i < n; i++) sorted_array[i] = array_to_sort[i]; quicksort(sorted_array, 0, n);}//*****************堆排序***********************void Sift(int data[], int k, int m){ int i=k; //置i为要筛的结点，j为i的左孩子 int j = i*2; while(j<=m) //筛选还没有进行到叶子 { if(j<m && data[j]<data[j+1]) j++; if(data[i]>data[j]) break; else { int temp = data[i]; data[i] = data[j]; data[j] = temp; i = j; j = 2*i; }//else }//while}void heapsort(int data[], int n){ //初建堆,从最后一个非终端结点至根结点 for(int i=n/2; i>=1; i--) Sift(data,i,n); //调整,重复执行移走堆顶及重建堆的操作 for(i=1; i<n; i++) { int temp = data[1]; data[1] = data[n-i+1]; data[n-i+1] = temp; Sift(data,1,n-i); }}//**主调函数**void HeapSort(const int *array_to_sort, int *sorted_array, const int n) { for (int i = 0; i < n; i++) sorted_array[i] = array_to_sort[i]; heapsort(sorted_array, n);}//*****************归并排序***********************//一次归并算法void Merge(int r[], int r1[], int s, int m, int t){ int i = s, j = m+1, k = s; while(i<=m && j<=t) { if(r[i]<=r[j]) r1[k++] = r[i++]; //取r[i]和r[j]中较小者放入r1[k] else r1[k++] = r[j++]; }//while if(i<=m)while(i<=m) //若第一个子序列没处理完，则进行收尾处理 r1[k++] = r[i++]; else while(j<=t) //若第二个子序列没处理完，则进行收尾处理 r1[k++] = r[j++];}//一趟归并算法void MergePass(int r[], int r1[], int n, int h){ int i=1; while(i<=n-2*h+1) //待归并记录至少有两个长度为h的子序列 { Merge(r,r1,i,i+h-1,i+2*h-1); i+=2*h; }//while if(i<n-h+1) Merge(r,r1,i,i+h-1,n); //待归并序列中有一个长度小于h else for(int k=i; k<=n; k++) //待归并序列中只剩一个子序列 r1[k] = r[k];}//归并排序非递归void MergeSort1(int r[], int r1[], int n){ int h=1; while(h<n) { MergePass(r,r1,n,h); h = 2*h; MergePass(r1,r,n,h); h = 2*h; }//while}//**主调函数**void MergeSort(const int *array_to_sort, int *sorted_array, const int n) { int sorted_array1[200000]={0}; //数组要大！ for (int i = 0; i < n; i++) sorted_array[i] = array_to_sort[i]; MergeSort1(sorted_array, sorted_array1,n);}
排序算法及其比较--数据结构课设