归并排序就这么简单
从前面已经讲解了冒泡排序、选择排序、插入排序,快速排序了,本章主要讲解的是归并排序,希望大家看完能够理解并手写出归并排序快速排序的代码,然后就通过面试了!如果我写得有错误的地方也请大家在评论下指出。
归并排序的介绍来源百度百科:
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
过程描述:
归并过程为:比较a[i]和b[j]的大小,若a[i]≤b[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素b[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
原理:
归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
下面我就来做个小小的总结:
将两个已排好序的数组合并成一个有序的数组,称之为归并排序
步骤:遍历两个数组,比较它们的值。谁比较小,谁先放入大数组中,直到数组遍历完成
一、演算归并排序过程现在我有两个已经排好顺序的数组:int[] arr1 = {2, 7, 8}和int[] arr2 = {1, 4, 9},我还有一个大数组来装载它们int[] arr = new int[6];
1.1那么,我将两个数组的值进行比较,谁的值比较小,谁就放入大数组中!
首先,拿出arr1[0]和arr2[0]进行比较,显然是arr2[0]比较小,因此将arr2[0]放入大数组中,同时arr2指针往后一格
所以,现在目前为止arr = {1}
1.2随后,拿arr1[0]和arr2[1]进行比较,显然是arr1[0]比较小,将arr1[0]放入大数组中,同时arr1指针往后一格
所以,现在目前为止arr = {1,2}
1.3随后,拿arr1[1]和arr2[1]进行比较,显然是arr2[1]比较小,将arr2[1]放入大数组中,同时arr2指针往后一格
所以,现在目前为止arr = {1,2,4}
........
遍历到最后,我们会将两个已排好序的数组变成一个已排好序的数组arr = {1,2,4,7,8,9}
二、归并排序前提分析(分治法)从上面的演算我们就直到,归并排序的前提是需要两个已经排好顺序的数组,那往往不会有两个已经排好顺序的数组给我们的呀(一般是杂乱无章的一个数组),那这个算法是不是很鸡肋的呢??
其实并不是的,首先假设题目给出的数组是这样子的:int[] arr = {2, 7, 8, 1, 4, 9};
当我们要做归并的时候就以arr[3]也就元素为1的那个地方分开。是然后用一个指针L指向arr[0],一个指针M指向arr[3],用一个指针R指向arr[5](数组最后一位)。有了指针的帮助,我们就可以将这个数组切割成是两个有序的数组了(操作的方式就可以和上面一样了)
可是上面说了,一般给出的是杂乱无章的一个数组,现在还是达不到要求。比如给出的是这样一个数组:int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
此时,我们就得用到分治的思想了:
那么我们也可以这样想将int[] arr = {2, 7, 8, 1, 4, 9};数组分隔成一份一份的,arr[0]它是一个有序的"数组",arr[1]它也是一个有序的"数组",利用指针(L,M,R)又可以像操作两个数组一样进行排序。最终合成{2,7}.......再不断拆分合并,最后又回到了我们的arr = {1,2,4,7,8,9},因此归并排序是可以排序杂乱无章的数组的
这就是我们的分治法--->将一个大问题分成很多个小问题进行解决,最后重新组合起来
三、归并代码实现实现步骤:
拆分
合并
........