归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
下图就是2-路归并排序的一个例子:
代价分析:
上图可以看出,一个N关键字的序列,两两归并可以构造一棵高度为[logN]的归并排序树。而每一次归并的时间复杂度为O(m+n)。因此每一趟归并的时间复杂度为O(N),如上图。归并排序算法的总时间复杂度为O(N*logN)
。其所需要的辅助空间就是一个能容纳中间合并结果的数量为N的连续空间。因此空间复杂度为O(N)
。是稳定排序方法。
速度仅次于快速排序。
------------------------------------------------------------------------------------------------
参考资料:
-------------------------------------------------------------------------------------------------------------------
我们可以用分治的思想解决归并排序,给定一个有N个关键字的有序序列,分治法的步骤如下:
(1)划分: 如果S中有1个元素,则直接返回S,因为它已经有序了。否则(S中至少有两个元素),把它们分别放入两个序列S1和S2中,S1和S2各包含大约S中的一半元素,即S1包含S中的前[N/2]个元素,S2包含S中的后[N/2]个元素。
(2)递归:递归求解子问题S1和S2。
(3)求解:归并有序序列S1和S2,使得他们成为一个有序序列,将其中的元素放回S中。
*这里有个问题就是排序的数字序列必须是2的次幂,否则就要处理越出的部分。
-------------------------------------------------------------------------------------------------------------------
public static void MergeSort(int[] array){
int size = array.length;
int step=2; // 设定一个步长
for(; step<=size; step*=2){ // 步长每次以2的指数级增长
for(int i=0; i<size; i+=step){
if(i+step<=size){
MergeSort(array, i, i+step/2-1, i+step-1);
}
}
}
// 对越出的部分(非2的次幂)进行处理
int lost = size%(step/2);
if(lost!=0){
MergeSort(array, 0, size-lost-1, size-1);
}
}
/**
* 对有序的子序列进行整合
* @param array
* @param start
* @param mid
* @param end
*/
private static void MergeSort(int[] array, int start, int mid, int end){
int i=start;
int j=mid+1;
int index = 0;
// 分配一个新的空间作为临时储存
int[] temp = new int[end-start+1];
// 对有序列进行排序
while(i<=mid && j<=end){
temp[index++] = array[i]<array[j]?array[i++]:array[j++];
}
while(i<=mid){
temp[index++] = array[i++];
}
while(j<=end){
temp[index++] = array[j++];
}
// 数据转移
index = 0;
for(int k=start; k<=end; k++){
array[k] = temp[index++];
}
}
- 大小: 36.9 KB
分享到:
相关推荐
归并排序 归并排序 归并排序 归并排序 归并排序
实现归并排序的c++代码,根据算法导论书籍内伪代码改写
代码是归并排序的c语言实现,归并算法MergeSortList.cpp
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
归并排序(MergeSort.h) 1.归并排序 MergeSort(int *array, int length) 分配排序(DistributionSort.h) 1.箱排序(桶排序)BinSort(int *array, int length) 或 BucketSort(int *array, int length) 2.基数...
用C++实现归并排序,题目基于MIT的算法导论中的第二章中的归并排序算法要求,visual studio 2010 实现
排序算法-归并排序详细讲解(MergeSort)
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
使用C++书写的归并排序算法,希望对各位有用。也请大牛指教代码中有何不足的地方!
%mergesort 分治算法——归并排序 %divide——将数组一分为二 %conquer——对两部分数组分别排序 %combine——将各自排好序的数组融合 %以此类推递归调用
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
//归并排序 public void MergeSort(int low, int high, int[] a) { int mid, i, j, k; int[] b = new int[high+1]; if (low >= high) { return; } mid = (low + high) / 2; MergeSort(low,mid,a); ...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort...合并排序:归并排序mergesort
java写的八大经典排序算法(win7 jdk 1.6 下运行) 冒泡排序 BubbleSort 堆排序 HeapSort 插入排序 InsSort ...归并排序 MergeSort 基数排序 BucketSort 简单选择排序 SelectSort 希尔排序 ShellSort
printf("\t6: 归并排序\n"); printf("\t7: 希尔排序\n"); printf("\t***************************\n"); scanf("%d",&i); //输入整数1-7,选择排序方式 switch (i){ case 1: InsertSort(R); break; //值为1,...
本文实例为大家分享了C++实现归并排序的具体代码,供大家参考,具体内容如下 一、思路:稳定排序 (1)划分:一直调用划分过程,直到子序列为空或只有一个元素为止,共需log2(n); (2)归并:将两个子序列从小到大...
归并排序执行三路归并排序
I created a complex MIPS assembler program and execute a simulation with SPIM.In my program,I implemented several sub-programs:mergesort,binary search,a sum total value,average,maximum and minimum. ...