第一次写博客，排版可能存在一定问题，还请见谅。
分享这篇实验报告的目的是想这可以帮助有需要的同学，毕竟我在进行该课程中也参考了许多前人的代码（前人code，后人copy）
该课程是存在查重系统的，可以借鉴，但不要照搬别人的实验报告和代码
实验目的
1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理
2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性
3.完成一亿数据排序
实验原理
通过对大量样本的测试结果，统计不同排序算法的时间效率与输入规模的关系， 通过经验分析方法，展示不同排序算法的时间复杂度，并与理论分析的基本运算次数做比较， 验证理论分析结论的正确性。
实验过程及内容：
冒泡排序：
算法原理：
比较相邻的元素，如果前一元素大于后一元素，则两元素交换，最终将最大的元素送至队尾
伪代码：
时间复杂度：
比较次数：[n*(n-1)] / 2
最好情况：O(n^2)
最坏情况：O(n^2)
平均时间复杂度：O(n^2)
选择排序
算法原理：
每趟遍历都会选择最大的元素，放置到队末，经过多次遍历最终形成有序序列
伪代码：
时间复杂度：
比较次数：[n*(n-1)] / 2
最好情况：O(n^2)
最坏情况：O(n^2)
平均时间复杂度：O(n^2)
插入排序
算法原理：
将序列分为有序序列和无序序列两部分，有序序列最初只有一个元素，每趟将一个无序序列中待排序的对象,插入到前面已经排好序的有序序列的适当位置上, 直到对象全部插入为止。
伪代码：
时间复杂度：
比较次数：不确定
最好情况：O(n)
最坏情况：O(n^2)
平均时间复杂度：O(n^2)
合并排序
算法原理：
合并排序代码分为两部分，第一部分为划分，使用二分的方法将无序序列划分为子序列，直到每个子序列都只有一个元素。然后开始第二部分合并，将两个有序子序列合并成一个有序子序列，直到只存在一个子序列为止
伪代码：
时间复杂度：
所有情况的递归式
T(n)=2T(n/2)+n
T(1)=1
T(n)=2²T(n/2²)+2n
......
T(n)=2^kT(1)+kn
2 =n
k=log₂n
算法复杂度为O(nlogn)
快速排序
算法原理：
选择序列第一个元素为基准，序列中比基准大的元素移至右侧，比基准小的元素移至左侧，以基准为界划分成两个子序列，然后子序列再进行快速排序，直到每个子序列只有一个元素为止
伪代码：
时间复杂度：
如果每执行一次快速排序，两个子序列长度相同，则为最理想的情况，时间复杂度为O(nlog2n) 如果每执行一次快速排序，其中一个子序列长度只为1，则为最糟糕的情况，时间复杂度为O(n^2)
最坏情况：(每次只划分一个数字)
T(n)=T(n-1)+n-1
T(1)=1
T(n)=n(n-1)/2
最好情况:(每次刚好均分)
T(n)=2T(n/2)+n-1
T(1)=1
T(n)= O(nlog2n)
最坏情况下时间复杂度为O(n^2)
算法时间理论效率分析的曲线和实测的效率曲线
//文章显示存在一定问题，有些表格数据不全，会以图片形式展现，请见谅
| 10000 | 20000 | 30000 | 40000 | 50000 | 60000 | 70000 | 80000 | 90000 | 100000 | |
| 快速排序 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 归并排序 | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
| 插入排序 | 50 | 196 | 443 | 788 | 1235 | 1774 | 2415 | 3156 | 3988 | 4932 |
| 冒泡排序 | 191 | 841 | 1956 | 3543 | 5627 | 8173 | 11181 | 14665 | 18586 | 23000 |
| 选择排序 | 104 | 415 | 933 | 1659 | 2591 | 3730 | 5075 | 6627 | 8386 | 10353 |
从数据中我们可以看出合并排序和快速排序消耗时间较小，理论计算容易引起较大误差，故在后文使用10万至100万的数据以减小误差
冒泡排序
由1万至10万所花费的时间（ms）
| 冒泡排序 | 理论 | 191 | 764 | 1719 | 3056 | 4775 | 6876 | 9359 | 12224 | 15471 | 19100 |
| 实验 | 191 | 841 | 1956 | 3543 | 5627 | 8173 | 11181 | 14665 | 18586 | 23000 |
冒泡排序时间曲线为二次曲线，与理论分析结果相符。 理论曲线与实验曲线偏差较大，可能是由于冒泡排序频繁交换元素消耗过多时间导致
选择排序
由1万至10万所花费的时间时间（ms）
| 选择排序 | 理论 | 104 | 416 | 936 | 1664 | 2600 | 3744 | 5096 | 6656 | 8424 | 10400 |
| 实验 | 104 | 415 | 933 | 1659 | 2591 | 3730 | 5075 | 6627 | 8386 | 10353 |
选择排序时间曲线为二次曲线，与理论分析结果相符。
理论曲线与实验曲线偏差小，与预测结果相符
插入排序
由1万至10万所花费的时间时间（ms）
| 插入排序 | 理论 | 50 | 200 | 450 | 800 | 1250 | 1800 | 2450 | 3200 | 4050 | 5000 |
| 实验 | 50 | 196 | 443 | 788 | 1235 | 1774 | 2415 | 3156 | 3988 | 4932 |
插入排序时间曲线为二次曲线，与理论分析结果相符。
理论曲线与实验曲线偏差小，与预测结果相符
快速排序
由10万至100万所花费的时间时间（ms）
| 快速排序 大数据： | 实验 | 10 | 20 | 32 | 44 | 56 | 69 | 83 | 97 | 112 | 126 |
| 理论 | 10 | 21.21 | 32.87 | 44.82 | 56.99 | 69.34 | 81.84 | 94.45 | 107.18 | 120 |
归并排序
由10万至100万所花费的时间时间（ms）
| 归并排序 大数据： | 实验 | 44 | 89 | 135 | 181 | 232 | 277 | 323 | 368 | 415 | 462 |
| 理论 | 44 | 93.3 | 144.6 | 197.19 | 250.75 | 305.09 | 360.06 | 415.58 | 471.58 | 528 |
合并排序时间曲线为一次曲线，与理论分析结果相符。
理论曲线与实验曲线存在偏差较大，可能是由于递归多次调用函数以及数据存在差异，导致理论计算出现误差
一亿数据排序
现在有 1 亿的数据，请选择合适的排序算法与数据结构，在有限的时间内完成进行排序
采用了计数排序
核心算法：
找出数组中最大值max，创建一个长度为max+1，元素初值全部为 0 的数组，遍历待排序列，每读取一次数字，数组中对应该数字下标的数值加一。然后再依次放回到原数组中，完成排序
时间复杂度：O(n+k)
代码性能：
执行一千万至一亿排序的平均时间（ms）：
算法优势：
为O（n）算法，执行速度远远高于快速排序和归并排序，可以在更短的时间内完成排序
算法劣势：
不能排序浮点数，如果排序的数字最大值较大，会占用大量的空间，牺牲空间换取时间
实验结论：
冒泡排序，选择排序，插入排序便于理解和编写，适合小规模排序，快速排序和归并排序复杂度为O（nlogn），性能远优于O（n^2）算法，适合大规模数据排序
在实验理论效率分析的曲线的分析中，五个排序算法曲线都和时间复杂度相符合。经验分析和理论分析一致
代码
#include<iostream>
#include<ctime>
#include<algorithm>
using namespace std;
//输出数组
void display(int* num, int size) {
for (int i = 0; i < size; i++)
cout << num[i] << " ";
cout << endl;
}
//快速排序
void QuickSort(int *num,int low, int high)
{
int i = low, j = high, temp = num[low];
while (low < high) {
while ((low < high) && (temp <= num[high]))
high--;
if (low < high)
num[low++] = num[high];
else
break;
while ((low < high) && (num[low] <= temp))
low++;
if (low < high)
num[high--] = num[low];
}
num[low] = temp;
if (i < low - 1)
QuickSort(num, i, low - 1);
if (high + 1 < j)
QuickSort(num, high + 1, j);
}
int Quick_Sorting(int* num, int size) {
int start, end;
start = clock();
QuickSort(num, 0, size - 1);
end = clock();
return end - start;
}
//归并排序
void Merge(int* num, int Left, int Right, int mid)
{
int i, j, k;
int* temp = new int[Right - Left + 1];
for (k = Left; k <= Right; k++)
temp[k - Left] = num[k];
i = Left;
j = mid + 1;
for (k = Left; k <= Right; k++)
{
if (i > mid)
{
num[k] = temp[j - Left];
j++;
}
else if (j > Right)
{
num[k] = temp[i - Left];
i++;
}
else if (temp[i - Left] > temp[j - Left])
{
num[k] = temp[j - Left];
j++;
}
else
{
num[k] = temp[i - Left];
i++;
}
}
delete[]temp;
}
void MergeSorting(int* num, int Left, int Right)
{
if (Left >= Right)
return;
int mid = (Left + Right) / 2;
MergeSorting(num, Left, mid);
MergeSorting(num, mid + 1, Right);
Merge(num, Left, Right, mid);
}
int Merge_Sorting(int* num, int size) {
int start, end;
start = clock();
MergeSorting(num, 0, size - 1);
end = clock();
return end - start;
}
//冒泡排序
int Bubbling_Sorting(int* num, int size) {
int start, end;
start = clock();
int temp = 0;
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - 1 - i; j++) {
if (num[j] > num[j + 1]) {
temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
}
}
}
end = clock();
return end - start;
}
//插入排序
int Insert_Sort(int* num, int size) {
int start, end;
start = clock();
int temp = 0;
for (int i = 1; i < size; i++)
{
int j = i - 1;
temp = num[i];
while (j >= 0 && temp < num[j])
{
num[j + 1] = num[j];
j--;
}
num[j + 1] = temp;
}
end = clock();
return end - start;
}
//选择排序
int Select_Sort(int* num, int size) {
double start, end;
start = clock();
int temp = 0, min = INT_MAX;
for (int i = 0; i < size - 1; i++) {
for (int j = i; j < size; j++) {
if (num[j] < min) {
temp = j;
min = num[j];
}
}
num[temp] = num[i];
num[i] = min;
min = INT_MAX;
}
end = clock();
return end - start;
}
//计数排序
int Count_Sort(int* num, int size) {
int start, end;
start = clock();
int max = 0;
for (int i = 0; i < size; i++) {
if (num[i] > max)
max = num[i];
}
int* Count = new int[max+1];
for (int i = 0; i < max + 1; i++)
Count[i] = 0;
for (int i = 0; i < size; i++)
Count[num[i]]++;
int k = 0;
for (int i = 0; i <= max; i++) {
while (Count[i]-- > 0) {
num[k++] = i;
}
}
delete[]Count;
end = clock();
return end - start;
}
//测试时间
void test(int fre, int size) {
srand(rand());
int* num = new int[size];
int sum,temp;
sum = 0, temp = 0;
for (int i = 0; i < fre; i++) {
for (int j = 0; j < size; j++)
num[j] = rand();
temp = Count_Sort(num, size);
sum += temp;
}
cout << "计数排序平均时间为" << sum / fre << endl;
sum = 0, temp = 0;
for (int i = 0; i < fre; i++) {
for (int j = 0; j < size; j++)
num[j] = rand();
temp = Quick_Sorting(num, size);
sum += temp;
}
cout << "快速排序平均时间为" << sum / fre << endl;
sum = 0, temp = 0;
for (int i = 0; i < fre; i++) {
for (int j = 0; j < size; j++)
num[j] = rand();
temp = Merge_Sorting(num, size);
sum += temp;
}
cout << "归并排序平均时间为" << sum / fre << endl;
sum = 0, temp = 0;
for (int i = 0; i < fre; i++) {
for (int j = 0; j < size; j++)
num[j] = rand();
temp = Insert_Sort(num, size);
sum += temp;
}
cout << "插入排序平均时间为" << sum / fre << endl;
sum = 0, temp = 0;
for (int i = 0; i < fre; i++) {
for (int j = 0; j < size; j++)
num[j] = rand();
temp = Bubbling_Sorting(num, size);
sum += temp;
}
cout << "冒泡排序平均时间为" << sum / fre << endl;
sum = 0, temp = 0;
for (int i = 0; i < fre; i++) {
for (int j = 0; j < size; j++)
num[j] = rand();
temp = Select_Sort(num, size);
sum += temp;
}
cout << "选择排序平均时间为" << sum / fre << endl;
}
int main() {
for (int i = 1; i <= 10; i++) {
cout << "规模大小：" << i * 10000 << endl;
test(20, i * 10000);
//调用test函数测试时间，每个算法执行20次，数据规模为1万至10万
}
}