自底向上的归并排序算法

首页 > 代码库 > 自底向上的归并排序算法

自底向上的归并排序算法

2024-09-06 23:20:22 214人阅读

1、什么是自底向上的归并排序？

说到底，不管是前面说的自顶向下的归并排序还是现在讲的自底向上的归并排序，其实质都是归并。

来看看一个演示过程:

这个就是待排序的数组序列

技术分享先将数组序列以2个元素为一组分成4组，每个组内部分成2个子序列进行向上合并

技术分享这是合并之后的效果

技术分享然后以4个元素为一组分成2组，每个组内部分成2个子序列进行向上合并

技术分享这是合并之后的效果

然后以8个元素为一组分成1个组，每个组内部分成2个子序列进行向上合并

最终整个序列编程有序的了

其实从这里看就可以知道，这个就好像是前面说的自顶向下排序过程中的后面一个过程。

2、时间复杂度

同自顶向下的归并排序相同，时间复杂度也是O(nlogn)级别。

3、算法的实现（基于C++）

#define MIN(a, b) ((a) < (b) ? (a) : (b))

 1 /***************************** 自底向上的归并排序算法实现 ***********************************/
 2 template<typename T>
 3 void mergeSortBU (T arr[], int count)
 4 {
 5     for (int size = 1; size <= count; size += size) {    // 外层循环对子序列进行分组    
 6         for (int i = 0; i + size < count; i += size + size) {  // 内层循环遍历所有分好组的子序列依次向上归并
 7             __merge<T>(arr, i, i + size - 1, MIN(i + size + size - 1, count - 1));  // 这个函数就在自顶向下归并排序中实现的__merge函数 9         }
10     }
11 }
12 /*******************************************************************************************/

4、性能测试（与经过优化过的自顶向下归并排序算法相比较）

测试数据量50000:

技术分享

测试数据量100000:

技术分享

5、算法优化

其实跟自顶向下归并排序的优化算法是一样的

 1 /***************************** 自底向上的归并排序算法的优化 ***********************************/
 2 template<typename T>
 3 void mergeSortBU (T arr[], int count)
 4 {
 5     for (int size = 1; size <= count; size += size) {    // 外层循环对子序列进行分组    
 6         for (int i = 0; i + size < count; i += size + size) {  // 内层循环遍历所有分好组的子序列依次向上归并
 7             if (MIN(i + size + size - 1, count - 1) - i < 50) { // 优化措施2
 8                 __insertSortMG<T>(arr, i, MIN(i + size + size - 1, count - 1));     //  这个函数就是在自顶向下归并排序中实现的__insertSortMG函数
 9                 continue;
10             }
11 
12             if (arr[i + size - 1] > arr[i + size]) {   // 优化措施1
13                 __merge<T>(arr, i, i + size - 1, MIN(i + size + size - 1, count - 1));  // 这个函数就在自顶向下归并排序中实现的__merge函数
14             }   
15         }
16     }
17 }
18 /*******************************************************************************************/