Exercise1 and 2
归并排序及时间复杂性：#include<iostream>#include<stdlib.h>#include<time.h>using namespace std;#define N1 10000#define N3 30000#define N5 50000#define N8 80000#define N10 100000#define N20 200000void 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 countTime(int* arr, int l, int r) {//计算程序运行时间clock_t start, finish;double totaltime;start = clock();MergeSort(arr,l,r);// 被测试函数finish = clock();totaltime = (double)(finish - start) / CLOCKS_PER_SEC;cout << "\n数组长："<< r+1 <<"\t运行时间为:" << totaltime << "秒！" << endl;}int main() {int a1[N1];countTime(a1, 0, N1-1);int a3[N3];countTime(a3, 0, N3 - 1);int a5[N5];countTime(a5, 0, N5 - 1);int a8[N8];countTime(a8, 0, N8 - 1);int a10[N10];countTime(a10, 0, N10 - 1);int a20[N20];countTime(a20, 0, N20 - 1);}
注意 编译器默认内存栈为1M，10w以上的数组就容易栈溢出，需要改写系统栈的大小，相关博客链接——visual stdio改变系统的栈大小，点击一下
快速排序及时间复杂性：#include<iostream>#include<stdlib.h>#include<time.h>using namespace std;#define N1 10000#define N3 30000#define N5 50000#define N8 80000#define N10 100000#define N20 200000void quickSort(int* array, int left, int right){if (left < right){int pivot = array[left];int low = left, high = right;while (low < high){while (array[high] >= pivot && low < high)high--;array[low] = array[high];while (array[low] <= pivot && low < high)low++;array[high] = array[low];}array[low] = pivot;quickSort(array, left, low - 1);quickSort(array, low + 1, right);}}void countTime(int* arr, int l, int r) {//计算程序运行时间clock_t start, finish;double totaltime;start = clock();quickSort(arr, l, r);// 被测试函数finish = clock();totaltime = (double)(finish - start) / CLOCKS_PER_SEC;cout << "\n数组长：" << r + 1 << "\t运行时间为:" << totaltime << "秒！" << endl;}int main() {int a1[N1];countTime(a1, 0, N1 - 1);int a3[N3];countTime(a3, 0, N3 - 1);int a5[N5];countTime(a5, 0, N5 - 1);int a8[N8];countTime(a8, 0, N8 - 1);int a10[N10];countTime(a10, 0, N10 - 1);int a20[N20];countTime(a20, 0, N20 - 1);}//老师，编译器不支持超过10万的数组，栈溢出啦。
