一:概念
归并排序(英文为Merge sort ): 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
----------------------------------------------------------------------------------------------------------------------
归并操作(merge):也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
归并操作的过程如下:
1. 申请空间S,使其大小为两个已经排序序列A、B之和,该空间用来存放合并A、B后的序列
2. 设定两个指针,最初位置分别为序列A、B的起始位置
3. 比较两个指针所指向的元素,选择相对较小的元素放入到空间S,并移动指针到下一个位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
----------------------------------------------------------------------------------------------------------------------
二:原理
分治法分以下三个步骤:
– Divide:划分问题转化(多个)为“简单”版的自己(子问题)。
– Conquer:使用相同的方法(通常是递归)解决每一个(子)问题
– Combine:结合的“简单”版本的结果,形成最终的解决方案。
归并排序可分以下三个步骤:
1. Sort the first half using merge sort. (recursive!)
2. Sort the second half using merge sort. (recursive!)
3. Merge the two sorted halves to obtain thefinal sorted array.
原理:把原始数组分成若干子数组,对每一个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组
流程图:
三:特点
· Stable --稳定性
· O(n) extra space for arrays (as shown) --数组 空间复杂度O(n)
· O(lg(n)) extra space for linked lists --链表 空间复杂度O(lg(n))
· O(n·lg(n)) time --时间复杂度O(n*log(n))
· Not adaptive
· Does not require random access to data --不需要随机访问数据
四:JAVA如何实现归并排序
import java.util.Arrays; public class MergeSort { public static void main(String[] args) { MergeSort t = new MergeSort(); int[] arrays = {1,8,5,7,9,2,5}; int[] a = t.mergeSort(arrays); System.out.println(Arrays.toString(a)); } /** * @param array 其元素都是有效的整数(不为null) * @return 返回数组,数组按升序排序(低到高) */ public int[] mergeSort(int array[]) { // 如果数组元素有多个(大于1),则进行归并操作 if(array.length > 1) { //初始化两个子数组的大小 int elementsInA1 = array.length / 2; //子数组2的大小 = (array.length&1)==1? array.length/2 : array.length/2+1; //int elementsInA2 = array.length - elementsInA1; (同下) int elementsInA2 = (array.length&1)==1? elementsInA1+1 : elementsInA1; //声明和初始化两个子数组 int arr1[] = new int[elementsInA1]; int arr2[] = new int[elementsInA2]; //对两个子数组进行赋值 arr1 = Arrays.copyOfRange(array, 0, elementsInA1); arr2 = Arrays.copyOfRange(array, elementsInA1,elementsInA1 + elementsInA2); //递归进行归并排序操作(递归函数调用) arr1 = mergeSort(arr1); arr2 = mergeSort(arr2); //-------------------------排序代码块【start】------------------------------- //定义三个变量 // [i] -- 参数数组array的索引 // [j] -- 子数组arr1中正在比较的元素的索引 // [k] -- 子数组arr2中正在比较的元素的索引 int i = 0, j = 0, k = 0; //下面的循环将一直运行,直到有一个子数组中的变空 while(arr1.length != j && arr2.length != k){ if(arr1[j] < arr2[k]){ //复制到最终的数组 array[i] = arr1[j]; i++; j++; }else{ array[i] = arr2[k]; i++; k++; } } //走到这,子数组中的一个已经被用尽,它已没有元素进行比较。这意味着剩下的数组中的元素 //都是最高的(已排序),所以可以把它复制到最终的数组。 while(arr1.length != j){ array[i] = arr1[j]; i++; j++; } while(arr2.length != k){ array[i] = arr2[k]; i++; k++; } //-------------------------排序代码块【end】------------------------------- } //返回已经排序的数组 return array; } }
四:算法复杂度
归并排序的最好、最坏和平均时间复杂度都是O(nlogn),而空间复杂度是O(n),比较次数介于(nlogn)/2和(nlogn)-n+1,赋值操作的次数是(2nlogn)。因此可以看出,归并排序算法比较占用内存,但却是效率高且稳定的排序算法
参考资料:
http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
http://www.cnblogs.com/kkun/archive/2011/11/23/merge_sort.html
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm
http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Merge_sort
http://www.cs.cmu.edu/~15110-f12/Unit05PtC-handout.pdf
http://www.roseindia.net/java/beginners/arrayexamples/mergeSort.shtml
http://www.mycstutorials.com/articles/sorting/mergesort
http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
http://blog.csdn.net/chenhuajie123/article/details/9296359
相关推荐
C++排序算法之归并排序源码
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
主要介绍了C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,需要的朋友可以参考下
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
自己编写的基于java的快速排序和归并算法
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
根据算法导论实现的归并排序算法
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
本人自己写的一些排序算法,这是系列1归并排序算法实现,
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
易语言归并排序算法源码,归并排序算法,归并排序,子程序_有序数组合并
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
从排序的基本概念讲起,详细讲解了插入排序、交换排序、选择排序、归并排序等排序算法的原理以及实现代码