简介:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
一、主要步骤
将待排序数组[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。
综上可知:
归并排序其实要做两件事:
(1)“分解”——将序列每次折半划分。
(2)“合并”——将划分后的序列段两两合并后排序。
二、演示过程
1、先看合并
(1)、两端相邻的有序子数组,arr[start]~arr[mid] 称为数组A和arr[mid+1]~arr[end] 称为数组B
(2)、每次各从数组A和数组B中取出一个值相比较,小的一个放到临时数组C
(3)、最后数组A和数组B中的数据取完时,数组C就是一个有序的合并后的数组。
(4)、最后在临时数组复制到原数组中
2、在看分解
(1)、先把数组分成最细,gap=1,然后把相邻的两个数据合并排序
(2)、然后设置gap=2,继续把相邻的两个数组合并。若子表个数为奇数,则最后一个子表无须和其他子表归并(即本趟处理轮空);
若子表个数为偶数,则要注意到最后一对子表中后一个子表区间的上限为n-1。
(3)、直到gap等于数组的长度,数组合并完成
如图所示:
三、代码实现
@Override public void sort(int[] arr) { mergeSort(arr); } private void merge(int[] array,int start,int mid,int end){ int temp[] = new int[end-start+1];//临时数组 int firstArrIndex = start;//第一段数组序列的下标 int secondArrIndex = mid+1;//第二段数组序列的下标 int tempArrIndex = 0;//临时存放数组的下标 //1.扫描第一个数组序列和第二个数组序列 while(firstArrIndex <=mid && secondArrIndex<=end){ //1.1 当第一段数组小于第二段数组 未排序的首个元素时 if(array[firstArrIndex] <=array[secondArrIndex]){ temp[tempArrIndex] = array[firstArrIndex]; firstArrIndex++; }else{//1.2 当第二段数组小于第一段数组 未排序的首个元素时 temp[tempArrIndex] = array[secondArrIndex]; secondArrIndex++; } tempArrIndex++; } //2.当第一段没有复制完全时,将剩余的数组全部复制到临时数组 while(firstArrIndex<=mid){ temp[tempArrIndex] = array[firstArrIndex]; firstArrIndex++; tempArrIndex++; } //3.当第二段没有复制完全时,讲剩余的数组全部复制到临时数组 while(secondArrIndex<=end){ temp[tempArrIndex] = array[secondArrIndex]; secondArrIndex++; tempArrIndex++; } //4.将临时数组复制到原始数组 for(tempArrIndex=0,firstArrIndex=start;firstArrIndex<=end;tempArrIndex++,firstArrIndex++){ array[firstArrIndex] = temp[tempArrIndex]; } } private void mergeSort(int[] arr){ for (int gap = 1; gap < arr.length; gap = 2 * gap) { int i=0; //归并gap长度的两个相邻子数组 for(i=0; i+2*gap-1< arr.length; i = i + 2*gap) { merge(arr, i, i+gap-1, i+2*gap-1); } // 余下不足两个合并的子数组。保证第一个数组gap存在。 if(i + gap - 1 < arr.length){ merge(arr, i, i + gap - 1, arr.length - 1); } } }
相关推荐
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排
算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间
详解Java常用排序算法-归并排序
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - 鸡尾酒排序Cocktail sort 经典排序算法 - 希尔排序Shell sort 经典排序算法 - ...
排序算法-归并排序详细讲解(MergeSort)
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
基于python的排序算法-归并排序Merge Sort
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法-数据结构和算法-14-归并排序.rar
根据算法导论实现的归并排序算法
算法的实现----归并排序 数据结构中学过的 编起耍哈哈
python 归并排序算法 归并排序是一种基于分治思想的排序算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),是一种...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...