一、实验目的和要求
熟悉排序算法和内存管理
二、实验环境
语言：C++
环境：IDEA Dev-C++ 5.11
三、实验内容
将100、1000、…、1000000个数据排序
时间如何？
空间如何？
完成尽量多的数据排序，并显示运行时间。
四、实验过程
?
4.1 任务定义和问题分析
1.编写程序运行计时器
2.编写随机数产生器
3.寻找适用于大量数据处理的排序算法
4.根据各排序算法运行时间寻找合适的算法
5.改进算法并增加数据处理量
6.编译器内存申请和管理
7.实现数据内外交互
4.2 概要设计（数据结构）
程序目标：开发一个能完成尽可能多的数据排序的程序
主要功能包括：
- 各类排序算法函数
- 程序运行计时器
- 随机数产生器
- 调用排序算法的主函数
- 内存管理
- 运行结果输出
- 数据内外交互
4.3 详细设计
- 各类排序算法函数：
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 快速排序
- 归并排序
- 堆排序
- 基数排序
- 库函数sort（）
2.利用时间种子产生相应数量的随机数。
3.使用C++数据流将输出结果导入txt文件实现数据的交互。
4.将数组定义为全局变量或将数组定义在堆上，以申请更大的内存。
五、测试及结果分析
5.1 实验数据
???????? 本次实验的数据均由C++种子随机数生成器产生
-
- 结果及分析
一、第一次排序 测试数据100000个：
- 冒泡排序
?
总共用时26.432s 稳定，耗时较长，内存消耗较大
- 选择排序
?
总共用时13.177s 不稳定，耗时较长，内存消耗较大
- 插入排序
?
总共用时8.216s 稳定，耗时较短，内存消耗较少
- 希尔排序
?
总共用时8.073s 不稳定，耗时较短，内存消耗较少
- 快速排序
?
总共用时8.201s 不稳定，耗时较短，内存消耗较少
- 归并排序
?
总共用时8.175s 稳定，耗时较短，内存消耗较少
- 堆排序
?
总共用时8.392s 不稳定，耗时较短，内存消耗较少
- 基数排序
?
?? 总共用时8.561s 稳定，耗时较短，内存消耗较少
??
9.库函数sort（）
?
总共用时8.038s 稳定，耗时较短，内存消耗较少
综上，选择快速排序进行下一步实验
第二次实验：
测试数据1000000个：
?
输出排序结果总共用时：78.203 s
?
不输出排序结果总共用时：0.109 s
测试数据10000000个：
?
输出排序结果总共用时：694.931 s
?
不输出排序结果总共用时：2.160 s
测试数据100000000个：
?
不输出最后排序结果，总共用时：128.282 s
综上，最多能完成100000000个随机数的排序
六、实验收获
1.实验前的准备很重要，比起打开电脑就开始漫无目的开始写代码，不如在开始前先对问题进行解析，学会把任务进行分解，设计解决问题的思路和流程，这样不但能在完成小块任务时获得成就感和动力，也能使问题解决更加清晰明了，逻辑更加严密。
2.遇到问题先思考，不要被问题的难度吓到，而是应该分析、尝试并不断调整。
3.实验时遇到无法解决的困难需要交流，别人的思路会给你带来新的启发，证明和证伪的过程也是新的学习过程，在尝试和探索的过程中总能有新的收获，这样不但能锻炼独立思考的能力，也能培养我们的合作意识。
4.实验过程中难免会经历失败，这需要我们马上调整心态，挫折不可避免但是需要以坦然来面对，有时候不需要太过执着，换个思路也许就是解决方案。
5.及时记录数据很重要！不小心把运行了好久的代码关掉很抓狂，所以一定一定要小心谨慎，运行的时候不要乱动电脑。
七、参考文献
一些csdn的文章😊
八、附录（源代码）
第一次实验：：
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<fstream>
using namespace std;
//冒泡排序
void BubbleSort(int arr[],int length) {
???????? for (int i = 0; i < length; i++) {
????????????????? for (int j = 0; j <= length - i - 1; j++) {
????????????????????????? if (arr[j+1] < arr[j]){
?????????????????????????????????? int temp = arr[j+1];
?????????????????????????????????? arr[j+1] = arr[j];
?????????????????????????????????? arr[j] = temp;
????????????????????????? }
????????????????? }
???????? }
}
//选择排序
void SelectSort(int arr[], int length) {
???????? for (int i = 0; i < length; i++) {
????????????????? int min = i;
????????????????? for (int j = i + 1; j < length; j++) {
????????????????????????? if (arr[j] < arr[min]) {
?????????????????????????????????? min = j;
????????????????????????? }????????????????????????
????????????????? }
????????????????? if (min != i) {
????????????????????????? int temp = arr[min];
????????????????????????? arr[min] = arr[i];
????????????????????????? arr[i] = temp;
????????????????? }
???????? }
}
//插入排序
void InsertSort(int arr[], int length) {
???????? int j;
???????? for (int i = 1; i < length; i++) {
????????????????? if (arr[i] < arr[i - 1]) {
????????????????????????? int temp = arr[i];
????????????????????????? for (j = i - 1; j >= 0 && temp < arr[j]; j -- ) {
?????????????????????????????????? arr[j + 1] = arr[j];????
????????????????????????? }
????????????????????????? arr[j + 1] = temp;
????????????????? }
???????? }
}
//希尔排序
void ShellSort(int arr[],int length ) {
???????? int increasement = length;
???????? int i,j,k;????
???????? do{
????????????????? increasement = increasement / 3 + 1;
????????????????? for (i = 0; i < increasement; i++) {
????????????????????????? for (j = i + increasement; j < length; j+=increasement) {
?????????????????????????????????? if (arr[j] < arr[j - increasement]) {
??????????????????????????????????????????? int temp = arr[j];
??????????????????????????????????????????? for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement) {
???????????????????????????????????????????????????? arr[k + increasement] = arr[k];
??????????????????????????????????????????? }
??????????????????????????????????????????? arr[k + increasement] = temp;
?????????????????????????????????? }
????????????????????????? }
????????????????? }
???????? } while (increasement > 1);
}
//快速排序
void QuickSort(int arr[],int start,int end) {
???????? int i = start;
???????? int j = end;
???????? int temp = arr[start];
???????? if (i < j) {
????????????????? while(i < j){
????????????????????????? while (i < j&&arr[j]>=temp){
?????????????????????????????????? j--;
????????????????????????? }
????????????????????????? if (i < j) {
?????????????????????????????????? arr[i] = arr[j];
?????????????????????????????????? i++;
????????????????????????? }
????????????????????????? while (i < j&&arr[i] < temp) {
?????????????????????????????????? i++;
????????????????????????? }
????????????????????????? if (i < j) {
?????????????????????????????????? arr[j] = arr[i];
?????????????????????????????????? j--;
????????????????????????? }
????????????????? }
????????????????? arr[i] = temp;
????????????????? QuickSort(arr, start, i - 1);
????????????????? QuickSort(arr, j + 1, end);
???????? }
}
//归并排序
void Merge(int arr[], int l, int q, int r){
??? int n=r-l+1,i=0,left=l,right=q+1;
??? int* tmp=new int[n];
??? while(left<=q && right<=r)
??????? tmp[i++] = arr[left]<= arr[right]?arr[left++]:arr[right++];
??? while(left<=q)
??????? tmp[i++]=arr[left++];
??? while(right<=r)
??????? tmp[i++]=arr[right++];
??? for(int j=0;j<n;++j)
??????? arr[l+j]=tmp[j];
??? delete [] tmp;
}
void MergeSort(int arr[], int l, int r){
??? if(l==r)
??????? return;
??? int q = (l + r)/2;
??? MergeSort(arr, l, q);
??? MergeSort(arr, q + 1, r);
??? Merge(arr, l, q, r);
}
//堆排序
void adjust(int arr[], int len, int index)
{
??? int left = 2*index + 1;
??? int right = 2*index + 2;
??? int maxIdx = index;
??? if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
??? if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;
?? ?if(maxIdx != index)
??? {
??????? int temp = arr[maxIdx];
????????????????? arr[maxIdx] = arr[index];
????????????????? arr[index] = temp;
??????? adjust(arr, len, maxIdx);
??? }
}
void HeapSort(int arr[], int size)
{
??? for(int i=size/2 - 1; i >= 0; i--)
??? {
??????? adjust(arr, size, i);
??? }
??? for(int i = size - 1; i >= 1; i--)
??? {
??????? int temp = arr[0];
????????????????? arr[0] = arr[i];
????????????????? arr[i] = temp;
??????? adjust(arr, i, 0);
??? }
}
//基数排序
void RadixSort(int*a,int length) {
???????? int i, max = a[0], base = 1;
???????? for (i = 0; i < length; i++) {
????????????????? if (a[i] > max) {
????????????????????????? max = a[i];
????????????????? }
???????? }
???????? int *t = new int[8*length];
???????? while (max / base > 0) {
????????????????? int bucket[10] = { 0 };
????????????????? for (i = 0; i < length; i++) {
????????????????????????? bucket[a[i] / base % 10]++;
????????????????? }
????????????????? for (i = 1; i < 10; i++) {
????????????????????????? bucket[i] += bucket[i - 1];
????????????????? }
????????????????? for (i =length - 1; i>= 0; i--) {
????????????????????????? t[bucket[a[i] / base % 10 ]-1] = a[i];
????????????????????????? bucket[a[i] / base % 10]--;
????????????????? }
????????????????? for (i = 0; i < length; i++) {
????????????????????????? a[i] = t[i];
????????????????? }
????????????????? base = base * 10;
???????? }
}
//c++库函数sort()
void SortSort(int arr[], int len) {
???????? sort(arr,arr+len);
}
int main() {
???????? ofstream fout("output.txt");
????????
???????? int a[100000] = { 0 };
???????? srand((unsigned)time(NULL));
???????? for (int i = 0; i < 100000; i++)
????????????????? a[i] = rand();
????????
???????? clock_t start = clock();
????????
???????? //BubbleSort(a,100000);
???????? //SelectSort(a,100000);
???????? //InsertSort(a,100000);
???????? //ShellSort(a,100000);
???????? //QuickSort(a,0,100000);
???????? //MergeSort(a,0,100000);
???????? //HeapSort(a,100000);
???????? //RadixSort(a,100000);
???????? SortSort(a,100000);
???????? for(int i = 0; i < 100000; i++){
????????????????? cout << a[i] << " ";
????????????????? fout << a[i] << " ";???
???????? }
???????? cout << endl;
????????
???????? clock_t end = clock();
???????? double endtime = (double)(end - start) / CLOCKS_PER_SEC;
???????? cout << endl;
???????? cout << "Total time:" << endtime << "s" << endl;
???????? fout << flush;
???????? fout.close();
???????? return 0;
}第二次实验：
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//快速排序
void QuickSort(int arr[],int start,int end) {
???????? int i = start;
???????? int j = end;
???????? int temp = arr[start];
???????? if (i < j) {
????????????????? while(i < j){
????????????????????????? while (i < j&&arr[j]>=temp){
?????????????????????????????????? j--;
????????????????????????? }
????????????????????????? if (i < j) {
?????????????????????????????????? arr[i] = arr[j];
?????????????????????????????????? i++;
????????????????????????? }
????????????????????????? while (i < j&&arr[i] < temp) {
?????????????????????????????????? i++;
????????????????????????? }
????????????????????????? if (i < j) {
?????????????????????????????????? arr[j] = arr[i];
?????????????????????????????????? j--;
????????????????????????? }
????????????????? }
????????????????? arr[i] = temp;
????????????????? QuickSort(arr, start, i - 1);
????????????????? QuickSort(arr, j + 1, end);
???????? }
}
????????
int main() {
???????? clock_t start = clock();
????????
???????? int *a;
??? a=new int[100000000];
???????? srand((unsigned)time(NULL));
???????? for (int i = 0; i < 100000000; i++)
????????????????? a[i] = rand();
???????? QuickSort(a,0,100000000);
???????? //MergeSort(a,0,100000);
???????? //HeapSort(a,100000);
???????? for(int i = 0; i < 100000000; i++)
????????????????? cout << a[i] << " ";
???????? cout << endl;
????????
???????? clock_t end = clock();
???????? double endtime = (double)(end - start) / CLOCKS_PER_SEC;
???????? cout << endl;
???????? cout << "Total time:" << endtime << "s" << endl;
???????? return 0;
}