使用插入排序优化的自底向上的归并排序的性能问题
使用了插入排序优化后，感觉性能差了不少，大约用时增加了50%，老师看看我是不是写的有问题呀，下面是完整的C++测试代码。
1 | #include <iostream><br>#include <ctime><br>#include <iomanip><br>#include <cassert><br><br>using namespace std;<br><br>template <typename T><br>class MergeSort {<br> private:<br> static void merge(T arr[], int l, int mid, int r, int temp[]) {<br> // 创建临时数组 temp 存放 arr[l, r] 的内容<br> // 复制当前的arr[l, r] 到 temp 中<br> for (int i = l; i <= r; i++) temp[i] = arr[i];<br> int i = l;<br> int j = mid + 1;<br> // 每轮循环为 arr[k] 赋值<br> // i 的取值范围为[l, mid]<br> // j 的取值范围为[mid + 1, r]<br> for (int k = l; k <= r; k++) {<br> // 取出 arr[i] 和 arr[j] 的最小值<br> // arr[j] 对应 temp[j - l], arr[i] 对应 temp[i - l]<br> if (i > mid) {<br> // i 已经超过范围<br> arr[k] = temp[j];<br> j++;<br> } else if (j > r) {<br> // j 已经超过范围<br> arr[k] = temp[i];<br> i++;<br> } else if (temp[i] <= temp[j]) {<br> // 注意这里如果 T 不是基本类型，需要重载 <= 运算符<br> arr[k] = temp[i];<br> i++;<br> } else {<br> arr[k] = temp[j];<br> j++;<br> }<br> }<br> }<br><br> public:<br> // 自底向上的归并排序(非递归)<br> static void sortBU(T arr[], int length) {<br> // 复制 arr 数组到 temp 数组<br> T *temp = new T[length];<br> for (int i = 0; i < length; i++) temp[i] = arr[i];<br><br> // 遍历合并的区间长度<br> for (int sz = 1; sz < length; sz += sz) {<br> // 遍历合并的两个区间的起始位置 i<br> // 合并 [i, i + sz - 1] 和 [i + sz, min(i + sz + sz - 1, length - 1)]<br> for (int i = 0; i + sz < length; i += sz + sz) {<br> int l = i;<br> int mid = i + sz - 1;<br> int r = min(i + sz + sz - 1, length - 1);<br> if (arr[mid] > arr[mid + 1]) merge(arr, l, mid, r, temp);<br> }<br> }<br> }<br><br> // 使用插入排序优化的自底向上的归并排序(非递归)<br> static void sortBUI(T arr[], int length) {<br> // 复制 arr 数组到 temp 数组<br> T *temp = new T[length];<br> for (int i = 0; i < length; i++) temp[i] = arr[i];<br><br> // 对于长度小于等于16的区间使用插入排序<br> for (int k = 0; k < length; k += 16) {<br> for (int i = k + 1; i < min(length - 1, k + 15); i++) {<br> T t = arr[i];<br> int j;<br> for (j = i; j - 1 >= 0 && t < arr[j - 1]; j--) arr[j] = arr[j - 1];<br> arr[j] = t;<br> }<br> }<br><br> // 遍历合并的区间长度<br> for (int sz = 1; sz < length; sz += sz) {<br> // 遍历合并的两个区间的起始位置 i<br> // 合并 [i, i + sz - 1] 和 [i + sz, min(i + sz + sz - 1, length - 1)]<br> for (int i = 0; i + sz < length; i += sz + sz) {<br> int l = i;<br> int mid = i + sz - 1;<br> int r = min(i + sz + sz - 1, length - 1);<br> if (arr[mid] > arr[mid + 1]) merge(arr, l, mid, r, temp);<br> }<br> }<br> }<br>};<br><br>template <typename T><br>class SortHelper {<br> public:<br> // 生成有n个元素的随机数组，每个元素的随机范围为[rangeL, rangeR]<br> static int *generateRandomArray(int n, int rangeL, int rangeR) {<br> // 设置断言，保证正确的输入<br> assert(rangeL <= rangeR);<br> int *arr = new int[n];<br> // 设置随机数种子<br> srand((unsigned int)time(NULL));<br> for (int i = 0; i < n; i++) {<br> // 标准的随机数生成方式<br> arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;<br> }<br> return arr;<br> }<br><br> // 生成有n个元素的近乎有序的数组<br> static int *generateNearlyOrderedArray(int n, int swapTimes) {<br> int *arr = new int[n];<br> for (int i = 0; i < n; i++) arr[i] = i;<br><br> srand((unsigned int)time(NULL));<br> for (int i = 0; i < swapTimes; i++) {<br> int posx = rand() % n;<br> int posy = rand() % n;<br> swap(arr[posx], arr[posy]);<br> }<br> return arr;<br> }<br><br> // 生成有n个元素的完全有序的数组<br> static int *generateOrderedArray(int n) {<br> int *arr = new int[n];<br> for (int i = 0; i < n; i++) arr[i] = i;<br> return arr;<br> }<br><br> static void printArray(T arr[], int n) {<br> for (int i = 0; i < n; i++) cout << arr[i] << " ";<br> cout << endl;<br> }<br><br> static bool isSorted(T arr[], int n) {<br> for (int i = 0; i < n - 1; i++)<br> if (arr[i] > arr[i + 1]) return false;<br> return true;<br> }<br><br> static void testSort(string sortName, void (*sort)(T[], int), T arr[],<br> int n) {<br> clock_t startTime = clock();<br> sort(arr, n);<br> clock_t endTime = clock();<br><br> assert(isSorted(arr, n));<br> cout << setw(17) << sortName << ", n = " << n << " : "<br> << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;<br> }<br><br> // 拷贝整形数组<br> static int *copyIntArray(int a[], int n) {<br> int *arr = new int[n];<br> copy(a, a + n, arr);<br> return arr;<br> }<br>};<br><br>int main() {<br> int dataSize[] = {10000, 100000, 1000000, 10000000};<br> for (int n : dataSize) {<br> int *arr1 = SortHelper<int>::generateRandomArray(n, 0, n);<br> int *arr2 = SortHelper<int>::copyIntArray(arr1, n);<br><br> cout << "\nFor Random Array:\n";<br> SortHelper<int>::testSort("Merge Sort BU", MergeSort<int>::sortBU, arr1, n);<br> SortHelper<int>::testSort("Merge Sort BUI", MergeSort<int>::sortBUI, arr2, n);<br><br> arr1 = SortHelper<int>::generateNearlyOrderedArray(n, 10);<br> arr2 = SortHelper<int>::copyIntArray(arr1, n);<br><br> cout << "\nFor Nearly Ordered Array:\n";<br> SortHelper<int>::testSort("Merge Sort BU", MergeSort<int>::sortBU, arr1, n);<br> SortHelper<int>::testSort("Merge Sort BUI", MergeSort<int>::sortBUI, arr2, n);<br><br> arr1 = SortHelper<int>::generateOrderedArray(n);<br> arr2 = SortHelper<int>::copyIntArray(arr1, n);<br> cout << "\nFor Fully Ordered Array:\n";<br> SortHelper<int>::testSort("Merge Sort BU", MergeSort<int>::sortBU, arr1, n);<br> SortHelper<int>::testSort("Merge Sort BUI", MergeSort<int>::sortBUI, arr2, n);<br> }<br>}<br> |
24
收起
正在回答
1回答
对长度为 16 的数组使用插入排序以后，下面的归并排序 sz 就不需要从 1 开始了。
P.S. 貌似你的区间插入排序的代码也是有问题的，可以在调试一下。
我之前的一个课程有 C++ 的 merge sort bu + insertion 优化的示例代码，可以参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/04-Merge-Sort-Bottom-Up/main.cpp
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧