使用插入排序优化的自底向上的归并排序的性能问题
使用了插入排序优化后，感觉性能差了不少，大约用时增加了50%，老师看看我是不是写的有问题呀，下面是完整的C++测试代码。
#include <iostream>
#include <ctime>
#include <iomanip>
#include <cassert>
using namespace std;
template <typename T>
class MergeSort {
private:
static void merge(T arr[], int l, int mid, int r, int temp[]) {
// 创建临时数组 temp 存放 arr[l, r] 的内容
// 复制当前的arr[l, r] 到 temp 中
for (int i = l; i <= r; i++) temp[i] = arr[i];
int i = l;
int j = mid + 1;
// 每轮循环为 arr[k] 赋值
// i 的取值范围为[l, mid]
// j 的取值范围为[mid + 1, r]
for (int k = l; k <= r; k++) {
// 取出 arr[i] 和 arr[j] 的最小值
// arr[j] 对应 temp[j - l], arr[i] 对应 temp[i - l]
if (i > mid) {
// i 已经超过范围
arr[k] = temp[j];
j++;
} else if (j > r) {
// j 已经超过范围
arr[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
// 注意这里如果 T 不是基本类型，需要重载 <= 运算符
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
}
}
public:
// 自底向上的归并排序(非递归)
static void sortBU(T arr[], int length) {
// 复制 arr 数组到 temp 数组
T *temp = new T[length];
for (int i = 0; i < length; i++) temp[i] = arr[i];
// 遍历合并的区间长度
for (int sz = 1; sz < length; sz += sz) {
// 遍历合并的两个区间的起始位置 i
// 合并 [i, i + sz - 1] 和 [i + sz, min(i + sz + sz - 1, length - 1)]
for (int i = 0; i + sz < length; i += sz + sz) {
int l = i;
int mid = i + sz - 1;
int r = min(i + sz + sz - 1, length - 1);
if (arr[mid] > arr[mid + 1]) merge(arr, l, mid, r, temp);
}
}
}
// 使用插入排序优化的自底向上的归并排序(非递归)
static void sortBUI(T arr[], int length) {
// 复制 arr 数组到 temp 数组
T *temp = new T[length];
for (int i = 0; i < length; i++) temp[i] = arr[i];
// 对于长度小于等于16的区间使用插入排序
for (int k = 0; k < length; k += 16) {
for (int i = k + 1; i < min(length - 1, k + 15); i++) {
T t = arr[i];
int j;
for (j = i; j - 1 >= 0 && t < arr[j - 1]; j--) arr[j] = arr[j - 1];
arr[j] = t;
}
}
// 遍历合并的区间长度
for (int sz = 1; sz < length; sz += sz) {
// 遍历合并的两个区间的起始位置 i
// 合并 [i, i + sz - 1] 和 [i + sz, min(i + sz + sz - 1, length - 1)]
for (int i = 0; i + sz < length; i += sz + sz) {
int l = i;
int mid = i + sz - 1;
int r = min(i + sz + sz - 1, length - 1);
if (arr[mid] > arr[mid + 1]) merge(arr, l, mid, r, temp);
}
}
}
};
template <typename T>
class SortHelper {
public:
// 生成有n个元素的随机数组，每个元素的随机范围为[rangeL, rangeR]
static int *generateRandomArray(int n, int rangeL, int rangeR) {
// 设置断言，保证正确的输入
assert(rangeL <= rangeR);
int *arr = new int[n];
// 设置随机数种子
srand((unsigned int)time(NULL));
for (int i = 0; i < n; i++) {
// 标准的随机数生成方式
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
}
return arr;
}
// 生成有n个元素的近乎有序的数组
static int *generateNearlyOrderedArray(int n, int swapTimes) {
int *arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = i;
srand((unsigned int)time(NULL));
for (int i = 0; i < swapTimes; i++) {
int posx = rand() % n;
int posy = rand() % n;
swap(arr[posx], arr[posy]);
}
return arr;
}
// 生成有n个元素的完全有序的数组
static int *generateOrderedArray(int n) {
int *arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = i;
return arr;
}
static void printArray(T arr[], int n) {
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
}
static bool isSorted(T arr[], int n) {
for (int i = 0; i < n - 1; i++)
if (arr[i] > arr[i + 1]) return false;
return true;
}
static void testSort(string sortName, void (*sort)(T[], int), T arr[],
int n) {
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
assert(isSorted(arr, n));
cout << setw(17) << sortName << ", n = " << n << " : "
<< double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
}
// 拷贝整形数组
static int *copyIntArray(int a[], int n) {
int *arr = new int[n];
copy(a, a + n, arr);
return arr;
}
};
int main() {
int dataSize[] = {10000, 100000, 1000000, 10000000};
for (int n : dataSize) {
int *arr1 = SortHelper<int>::generateRandomArray(n, 0, n);
int *arr2 = SortHelper<int>::copyIntArray(arr1, n);
cout << "\nFor Random Array:\n";
SortHelper<int>::testSort("Merge Sort BU", MergeSort<int>::sortBU, arr1, n);
SortHelper<int>::testSort("Merge Sort BUI", MergeSort<int>::sortBUI, arr2, n);
arr1 = SortHelper<int>::generateNearlyOrderedArray(n, 10);
arr2 = SortHelper<int>::copyIntArray(arr1, n);
cout << "\nFor Nearly Ordered Array:\n";
SortHelper<int>::testSort("Merge Sort BU", MergeSort<int>::sortBU, arr1, n);
SortHelper<int>::testSort("Merge Sort BUI", MergeSort<int>::sortBUI, arr2, n);
arr1 = SortHelper<int>::generateOrderedArray(n);
arr2 = SortHelper<int>::copyIntArray(arr1, n);
cout << "\nFor Fully Ordered Array:\n";
SortHelper<int>::testSort("Merge Sort BU", MergeSort<int>::sortBU, arr1, n);
SortHelper<int>::testSort("Merge Sort BUI", MergeSort<int>::sortBUI, arr2, n);
}
}
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积分~
来为老师/同学的回答评分吧
0 星