自底向上的归并排序(即非递归归并排序)方法,排序过程如下图:
首先两两归并,然后再归并元素数量加倍,这样的归并规程就像一颗二叉树。
在下面的代码中,函数mergeSort就是控制数组进行自底向上的归并的。m用于指定每次每个归并数组的归并元素的数量,i用于控制归并数组的选择(即指针的偏移)。在归并的时候(merge函数),使用一个辅助数组aux来进行归并,辅助数组aux是一个全局变量,大小应该与待排序数组一样,下面的代码中为了简单,直接设置成了15(即带排序数组a的大小)
#include <stdio.h>
#include <stdlib.h>
#define min(A, B) (A < B)? A:B
typedef char Item;
void mergeSort(Item a[], int l, int r);
void merge(Item a[], int start, int mid, int end);
Item aux[15];
/**
自底向上的归并排序
*/
int main() {
int i;
Item a[] = {'A', 'S', 'O', 'R', 'T', 'I', 'N', 'G', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};
mergeSort(a, 0, 14);
for(i = 0; i < 15; i++) {
printf("%4c", a[i]);
}
return 0;
}
/*自底向上的归并排序方法*/
void mergeSort(Item a[], int l, int r) {
int m, i;
for(m = 1; m < r; m += m) {
for(i = 0; (l+i+m-1) < r; i = i + m + m) {
merge(a, l+i, l+i+m-1, min(l+i+m-1+m, r));
}
}
}
/**
改进的归并方法,这样就可以减少检测是否到队尾的比较次数
*/
void merge(Item a[], int start, int mid, int end) {
int i, j, k;
for(i = mid + 1; i > start; i--) aux[i-1] = a[i-1];
for(j = mid; j < end; j++) aux[end+mid-j] = a[j+1];
for(k = start; k <= end; k++)
if(aux[i] < aux[j])
a[k] = aux[i++];
else
a[k] = aux[j--];
}
相关推荐
BOTTOMUPSORT排序算法和冒泡排序时间对比,通过生成随机数放到数组里面,再通过大量的数据比较这两种排序算法所用的时间,用JAVA实现。
主要介绍了C++实现自底向上的归并排序算法,结合实例形式较为详细的分析总结了自底向上的归并排序算法的原理与具体实现技巧,需要的朋友可以参考下
主要给大家介绍了关于C++/GoLang如何实现自底向上的归并排序的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
2路归并排序循环算法,避免递归调用带来的麻烦,采用自底向上的方法
编写选择排序,插入排序,自顶向上合并排序,合并排序,快速排序,理解各排序算法的实现原理,加深对排序算法的理解。
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
根号n段归并排序算法的C++代码实现: 1.合并【根号n向下取整】段子数组,使用了自底向上的两两合并策略。 2.算法的总体时间复杂度为nlogn 3.带有详细注释
自底向上归并排序-MergeBUSort | 快速排序-QuickSort | 堆排序-HeapSort :lion:搜索算法-搜索 与搜索相关的数据结构:二叉查找树,平衡查找树,散列表 线性查找-LinearSearch 二分查找-BinarySearch 广度优先搜索 ...
归并排序自底向上 快速排序 随机化快速排序 双路快速排序 三路快速排序 堆和堆排序 堆的基本存储 ShiftUp ShiftDown 基础堆排序和Heapify 优化的堆排序 索引堆(IndexHeap) 索引堆的优化 二分搜索树 二分查找法...
归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序、自底向上合并相邻的两个链表。 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和...
排序算法基础、改进综合: //冒泡排序 //定向冒泡[鸡尾酒]排序 //选择排序 //改进的选择排序 //直接插入排序 //二分插入排序 ...//自底向上地归并排序 //堆排序 //快速排序 //改进的快速排序:三向切分快速排序
主要介绍了Java编程中实现归并排序算法的实例教程,包括自底向上的归并排序的实现方法介绍,需要的朋友可以参考下
算法-数据-结构 代码包含堆栈队列和排序算法等数据结构的实现 实现的算法 数据结构 堆 链接堆栈 队列 链接队列 ...自底向上归并排序 com.utils.UserExceptions 无效函数调用异常 队列空异常 堆栈空异常
本文件主要实现了九种常用的排序,分别为:冒泡排序、选择排序、插入排序、自底向上的归并排序、自顶向下的归并排序、快速排序、堆排序、基数排序、希尔排序,希望对初学者有所帮助,也欢迎讨论。
1.写一个“由底向上”的归并分类排序算法。 2.用快速分类算法对10个数(键盘输入)进行从大到小或从小到大的排列并输出结果。
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。 9.标准...
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort... * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现思路~
2.2.3 自底向上的归并排序 175 2.2.4 排序算法的复杂度 177 2.3 快速排序 182 2.3.1 基本算法 182 2.3.2 性能特点 185 2.3.3 算法改进 187 2.4 优先队列 195 2.4.1 API 195 2.4.2...