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

自底向上的归并排序算法

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 /*******************************************************************************************/

优化过后的性能测试:

测试数据量50000:

技术分享

 

测试数据量100000:

技术分享

 

总结: 从上面的数据可以看出来,经过优化之后,自底向上归并排序的性能得到了一个很大的提升,但是还是比自顶向下归并排序慢,

这个其实是有原因的,在这里不做分析。

还有一个值得一提的就是未经过优化的算法的代码可知,代码中没有使用数组的特性(使用索引找到对应的元素),所以我们可以

用自底向上归并排序对一个链表进行排序。

 

自底向上的归并排序算法