本专栏和大家分享关于排序的算法,其中有插入排（直接插入排序和希尔排序）、选择排序（直接选择排序和堆排）、交换排序（冒泡排序和快速排序）、归并排序以及其他非基于比较的排序
本文与大家分享归并排序
目录
归并排序基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：
(1)分解过程
设区间的最左边为left,最右边为right,mid为中间,每次将[left,.right]分为一组,[mid+1right]分为一组,直到区间元素个数为1(left <= right)
(2)合并过程
我们举这组为例子:
首先一定要保证该区间是有元素的,其次,我们实际上是开辟了新的数组,将排序后的数组放到新数组里面,再拷贝回原数组
我们每次利用都是利用L1和L2进行比较,若L1小,就将L1放入数组,同时L1++,再继续比较;L2同理,直到L1 > R1或者L2 > R2,此时再把未遍历完的数组元素全部放进新数组,再将新数组拷贝到原数组即可
代码
public class MergeSort {
public static void merseSort(int[] array){
merseFunc(array,0,array.length-1);
}
private static void merseFunc(int[] array,int left,int right){
if(left >= right){
return;
}
int mid = left + (right - left) / 2;
merseFunc(array,left,mid);
merseFunc(array,mid+1,right);
//归并
merse(array,left,mid,right);
}
private static void merse(int[] array,int left,int mid,int right){
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
int[] tmpArr = new int[right-left+1];
int i = 0;
while(s1 <= e1 && s2 <= e2) {
if (array[s1] < array[s2]) {
tmpArr[i++] = array[s1++];
} else {
tmpArr[i++] = array[s2++];
}
}
while(s1 <= e1){
tmpArr[i++] = array[s1++];
}
while(s2 <= e2){
tmpArr[i++] = array[s2++];
}
for(int j = 0; j < i; j++){
array[left+j] = tmpArr[j];
}
}
}时空复杂度分析
时间复杂度为O(n log n),主要原因是分治和合并两个操作。
分治：归并排序将数组分成两个大致相等的子数组，然后递归地对这两个子数组进行排序。这个过程的时间复杂度为O(log n)，因为每次都将数组一分为二，直到每个子数组只包含一个元素为止。
合并：在合并过程中，需要将两个已排序的子数组合并成一个有序数组。合并操作的时间复杂度是O(n)，因为需要遍历每个元素一次，并将其放入合并后的数组中。
空间复杂度O(N)
归并排序：非递归实现
通过我们上面的分析,我们发现,反正最后都是将数组分为一个元素为一组的情况,那么我们直接将数组看成是一个元素一组的形式,从合并的操作开始
实际上合并的操作和我们采用递归方法的合并操作是一样的
我们同样需要知道每两组的s1、e1，s2、e2
如上图所示,当每一组的元素个数为1时,我们将每两组进行合并,合并完成后,再将s1和e1,s2和e2移动到下一组进行合并
以此类推,直到遍历完整个数组,此时数组就每两个两个之间是有序的,每一组的元素也就变成2,那么我们再将此时的每两组进行合并
还是按照上面的方法来进行每两组合并
合并的方法我们在上面已经写过了
private static void merse(int[] array,int left,int mid,int right)因此我们最主要还是求出两组的left,mid,right,实际上这三者的关系与当前每一组里面的元素个数有关,我们用gap来定义当前每一组的元素个数
那么就能得到:mid = left + gap - 1,right = mid + gap
由此公式就能对两组进行合并,当这两组合并完后,left要跳过两个gap去合并后两组,因此left += 2*gap
但是要注意一个细节,我们在求mid和right的时候,
可能会出现这种情况,即最后只有一组的情况此时left += 2*gap时,就会来到8的位置,那么求得的mid就会越界,因此我们需要判断,当我们的mid >= array.length时,我们要让它等于最后一个元素,即mid = array.length - 1,这样的操作,同样当right >= array.length我们要让right = array.length - 1,这样的操作就是把最后剩的一组自己与自己归并
public static void merseSortNor(int[] array){
int gap = 1;
while(gap < array.length){
for(int left = 0; left < array.length; left += 2*gap){
int mid = left + gap - 1;
if(mid >= array.length){
mid = array.length-1;
}
int right = mid + gap;
if(right >= array.length){
right = array.length-1;
}
merse(array,left,mid,right);
}
gap *= 2;
}
}海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
先把文件切分成 200 份，每个 512 M
分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
在合并的时候，采取每次从两个文件里面读取1个元素进行排序的方法，
