（三）实验算法源码分析
详细的完整代码在附件中。
现对代码结构及实现过程进行如下解释：
1、L1~L9：
进行头文件声明
2、L11~L242：
定义各个排序函数，每个函数的实现过程中均包含详细的注释。
3、L261~L558：
主函数：
①使用输出流创建文件，将每次程序运行的结果存入details.txt和result.txt中
②对于每个算法，利用循环将数据量级从101~106进行测试，每次测试时，均生成20组数据，计算时间后将结果再存会result.txt和details.txt文件中。
四、实验结论或体会
①同样问题下不同的数量级有不同的处理方法并应选择不同的算法。
例如对101103 这种小数据的排序可以选择基数排序与合并排序外的六种排序方式。而对数据量大于104
的数据应该选择快速排序，合并排序，基数排序，希尔排序或堆排序。对于数据量巨大例如1012
的数据则应该选择计数排序，并应该考虑内存外存的数据搬运问题。
②既定算法是对某种普遍情况的处理方式，可能存在极端情况。
例如快速排序，当数据大小大致成二分分布时，有很好的性能，但当数据恰好倒序或恰好正序时，则性能很差。因此对于特殊情况需要选择特定算法进行处理。
③不能忽略对现有算法的优化
例如冒泡排序和选择排序，在算法进行中，存在冗余操作，即存在可优化的空间。对算法进行优化可以在算法本质不变的情况下一定程度上提高算法的效率。
④实践是检验算法的唯一标准，应避免“想当然”
例如两种“可行”的冒泡排序优化算法，从理论上都似乎可行，但实际运行起来，一种算法并不能提高运行效率反而降低了效率。这给我的启示是对于算法的学习中，一定要使用数据对算法进行实践，避免理论上的想当然。
五、思考
在本次实验过程中，我也发现了一些问题如下：
1. 冒泡排序算法优化
传统冒泡排序算法中，排序完成的结束标准为所有循环全部循环结束。在实际算法运行中，会发现，在某次排序之后，部分序列变为有序，此时这部分序列不需进行冒泡排序。基于此，提出如下两个优化算法：
①减少无效循环次数
不难发现在实际运行中，冒泡排序算法截止的标志是全部循环运行结束，因此可能存在在循环结束前，序列已经有序，但仍需进行循环，此时将造成时间浪费。可以通过定义标志变量判断冒泡的一趟是否进行交换，如果未进行交换则序列已经有序，break出循环减少无效循环。基于这个想法，编写代码并测试：
从上表中可以发现，“优化”过的算法时间不仅没有减少，反而增加了。可能是因为算法几乎要全部循环结束才能完成排序，设置标志变量减少的循环次数不多。而且对标志变量赋值判断消耗的时间大于设置标志变量减少的循环消耗时间。因此不能提高算法效率！
②提高有效循环效率
假如有一个长度为50的数组，在一趟交换后，最后发生交换的位置是10，那么这个位置之后的40个数必定已经有序了，记录下这位置，下一趟交换只要从数组头部到这个位置就可以了
基于这个想法，编写代码并测试
可以看出，冒泡排序的时间消耗略微缩短了，算法得到了优化。
2.选择排序算法优化
在正常的选择排序中，每次都需要对所有元素进行比较但仅获得最大/最小值，不妨在选择排序过程中，每次获得最大值和最小值，从而将选择次数缩短一半。
基于此想法，编写代码并测试
可以看出，选择排序的时间消耗明显缩短，大致节省了20%的时间，算法得到了优化。
3.（思考题）现在有1万亿的数据，请选择合适的排序算法与数据结构，在有限的时间内完成进行排序。
一万亿数据进行排序即对1012个整数进行排序。一个长整形占4个字节。则1012
个整数占4 × 1012≈4TB。如此巨大的数据量不可能一次放到内存中。因此需要将数据存放在外存中，并在内存外存中搬运数据完成数据的排序处理。
此时，一般的排序方法将由于无法使用，经过查阅资料后，我选择了一种非比较算法进行排序——计数排序。
（1）计数排序介绍与原理
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为O ( n + k ) Ο(n+k)O(n+k)（其中k是整数的范围），快于任何比较排序算法。
算法具体实现如下：
①开辟一新数组，用来作为桶存每个元素出现的频率
②遍历待排序序列，将每个元素放入对应的桶中（频率值加一）
③遍历频率数组，并将每个元素存回原序列。
下面以排序2,3,8,4,6,1,3,9,4,7这10个数为例
（2）计数排序伪代码
COUNTSORT(A): memset(C,sizeof(C),0); //C数组置零 for i=1 to n do C[A[i]]++; //统计输入数组中相同元素的个数 for i=2 to k do C[i] = C[i]+C[i-1]; //C[i]表示输入数组中小于或者等于i的元素个数 for i=n downto 1 do B[C[A[i]]] = A[i]; //把每一个A[i]放到输出数组中相应位置上 C[A[i]]--; //如果有几个相同元素时,当然不能放在同一个位置了。
（3）计数排序在相对小数量级下的测试（单位ms）
通过随机数生成器生成不同测试数据，分别使用计数排序和通过实验得出对于大数据最高效的基数排序进行排序并比较时间。
可以看出，计数排序的时间消耗比目前最快的算法仍要快出很多。
（4）具体排序1012数据的步骤
①利用文件流创建若干个空文件，用来作为桶存各个数字出现频率。
②利用文件流，从外存中读入数字。并放入桶文件的对应位置。
③清空原数据源文件，并遍历桶文件将对应数字存入数据源文件中。
（5）时间消耗预计
由于计数排序的时间复杂度为O ( n + k ) （其中k是整数的范围）。则当排序1012个数字时，大约需要17 h
六、样例代码
//Code by:DongYunhao 2019284073 #include <algorithm> #include <cmath> #include <ctime> #include <fstream> #include <iostream> #include <random> #include <windows.h> using namespace std; 堆排序 void minHeapDown(int a[], int start, int end) { int current = start; // 当前(current)节点的位置 int left = 2 * current + 1; // 为左(left)孩子的位置 int tmp = a[current]; // 当前(current)节点的值 for (; left <= end; current = left, left = 2 * left + 1) { // "left"是左孩子，"left+1"是右孩子 if (left < end && a[left] > a[left + 1]) left++; // 左右两孩子中选择较小者 if (tmp <= a[left]) break; // 调整结束 else // 交换值 { a[current] = a[left]; a[left] = tmp; } } } //堆排序(降序)：交换数据，将a[1]和a[n]交换，使a[n]是a[1...n]中的最小值；然后将a[1...n-1]重新调整为最小堆。 void Heap_Sort_Desc(int a[], int n) { int i, tmp; for (i = n / 2 - 1; i >= 0; i--) // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最小)二叉堆。 minHeapDown(a, i, n - 1); //交换数据 for (i = n - 1; i > 0; i--) { // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最小的。 tmp = a[0]; a[0] = a[i]; a[i] = tmp; // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最小堆。 minHeapDown(a, 0, i - 1); } } 希尔排序 void Shell_Sort(int a[], int n) { int i, j, gap; // gap为步长，每次减为原来的一半。 for (gap = n / 2; gap > 0; gap /= 2) { // 共gap个组，对每一组都执行直接插入排序 for (i = 0; i < gap; i++) { for (j = i + gap; j < n; j += gap) { // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。 if (a[j] < a[j - gap]) { int tmp = a[j]; int k = j - gap; while (k >= 0 && a[k] > tmp) { a[k + gap] = a[k]; k -= gap; } a[k + gap] = tmp; } } } } } 基数排序 int maxbit(int a[], int n) { int d = 1; //保存最大的位数 int p = 10; for (int i = 0; i < n; i++) { while (a[i] >= p) { p *= 10; d++; } } return d; } void Radix_Sort(int a[], int n) { int d = maxbit(a, n); int *tmp = new int[n]; //int tmp[n]错误定义，数组长度必须是整数常量或整数符号常量，想要用变量设置大小，必须用动态分配 int count[10]; //计数器 int i, j, k; int radix = 1; for (i = 1; i <= d; i++) //进行d次排序 { for (j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for (j = 0; j < n; j++) { k = (a[j] / radix) % 10; //统计每个桶中的记录数 count[k]++; } for (j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //这时count里的值表示在tmp中的位置（减一为tmp里的存储下标） for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (a[j] / radix) % 10; tmp[count[k] - 1] = a[j]; count[k]--; //用于一个桶中有多个数，减一为桶中前一个数在tmp里的位置 } for (j = 0; j < n; j++) //将临时数组的内容复制到data中 a[j] = tmp[j]; radix = radix * 10; } delete[] tmp; } 快速排序 int quickSortPartition(int s[], int l, int r) { //Swap(s[l], s[(l + r) / 2]); //若以中间数为基准，则先将中间的这个数和第一个数交换即可 int i = l, j = r, x = s[l]; //将最左元素记录到x中 while (i < j) { // 从右向左找第一个<x的数 // 无需考虑下标越界 while (i < j && s[j] >= x) j--; if (i < j) s[i++] = s[j]; //直接替换掉最左元素（已在x中存有备份） // 从左向右找第一个>x的数 while (i < j && s[i] <= x) i++; if (i < j) //替换掉最右元素(已在最左元素中有备份） //最左元素一定被覆盖过，若没有，则表明右侧所有元素都>x，那么算法将终止 s[j--] = s[i]; } s[i] = x; //i的位置放了x，所以其左侧都小于x，右侧y都大于x return i; } void quickSort(int s[], int l, int r) { //数组左界<右界才有意义，否则说明都已排好，直接返回即可 if (l >= r) { return; } // 划分，返回基准点位置 int i = quickSortPartition(s, l, r); // 递归处理左右两部分，i处为分界点，不用管i了 quickSort(s, l, i - 1); quickSort(s, i + 1, r); } 归并排序 void Merge(int arr[], int l, int q, int r) { int n = r - l + 1; //临时数组存合并后的有序序列 int *tmp = new int[n]; int i = 0; int left = l; int right = q + 1; 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; //递归基是让数组中的每个数单独成为长度为1的区间 int q = (l + r) / 2; MergeSort(arr, l, q); MergeSort(arr, q + 1, r); Merge(arr, l, q, r); } 选择排序 void Selectsort(int num[], int length) { int index; for (int i = 0; i < length - 1; i++) { index = i; for (int j = i + 1; j < length; j++) { if (num[index] < num[j]) { index = j; } } swap(num[index], num[i]); } } //冒泡排序 void BubbleSort(int num[], int length) { for (int jj = 0; jj < length - 1; jj++) { for (int ii = 0; ii < length - 1 - jj; ii++) if (num[ii] > num[ii + 1]) { swap(num[ii], num[ii + 1]); } } } 插入排序 void InsertSort(int num[], int length) { for (int ii = 1; ii < length; ii++) { int jj = ii; int temp = num[ii]; for (; jj > 0 && temp < num[jj - 1]; jj--) { num[jj] = num[jj - 1]; } num[jj] = temp; } } /*主函数 */ int main() { //cout << "Please input the level of quantity: " << endl; int level; //输入数量级 ofstream details("details.txt"); ofstream logs("logs.txt"); for (level = 1; level <= 6; level++) { //cin >> level; //cout << "Please input the number of tests: " << endl; int numOfData; numOfData = 20; long long int length = pow(10, level); details << "===============================" << endl; logs << "===============================" << endl; details << "Level:" << level << " Quantity:" << length << " TestNumber:" << numOfData << endl; logs << "Level:" << level << " Quantity:" << length << " TestNumber:" << numOfData << endl; cout << "Running on " << level << endl; int *num = new int[length]; /* 选择排序 */ double total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); Selectsort(num, length); QueryPerformanceCounter(&nEndTime); details << "Select_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } details << "Select_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; logs << "Select_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; /* 冒泡排序 */ total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); BubbleSort(num, length); QueryPerformanceCounter(&nEndTime); details << "Bubble_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } details << "Bubble_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; logs << "Bubble_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; /* 插入排序 */ total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); InsertSort(num, length); QueryPerformanceCounter(&nEndTime); details << "Insert_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } details << "Insert_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; logs << "Insert_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; /* 快速排序 */ total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); quickSort(num, 0, length - 1); QueryPerformanceCounter(&nEndTime); details << "Quick_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } details << "Quick_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; logs << "Quick_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; /* 归并排序 */ total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); MergeSort(num, 0, length - 1); QueryPerformanceCounter(&nEndTime); details << "Merge_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } details << "Merge_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; logs << "Merge_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; /* 基数排序 */ total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); Radix_Sort(num, length); QueryPerformanceCounter(&nEndTime); details << "Radix_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } details << "Radix_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; logs << "Radix_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; /* 希尔排序 */ total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); Shell_Sort(num, length); QueryPerformanceCounter(&nEndTime); details << "Shell_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } logs << "Shell_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; details << "Shell_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; /* 堆排序 */ total_time = 0; for (int t = 0; t < numOfData; t++) { time_t seed = time(nullptr); default_random_engine eng(seed); uniform_int_distribution<int> dist(1, length); for (int i = 0; i < length; i++) { num[i] = dist(eng); } LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&nBeginTime); //排序源代码 Heap_Sort_Desc(num, length); QueryPerformanceCounter(&nEndTime); details << "Heap_sort Test Data " << t + 1 << " time cost:" << (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart * 1000 << "ms" << endl; total_time += (double) (nEndTime.QuadPart - nBeginTime.QuadPart) / (double) nFreq.QuadPart; } details << "Heap_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; logs << "Heap_sort Average Time Cost:" << total_time * 1000 / numOfData << "ms" << endl; } details.close(); logs.close(); return 0; }
