文章目录
归并排序原理
归并排序，也是应用了分治的思想。将原数组分为两个子数组，左子数组和右子数组，两个子数组排好序后，通过拷贝的方法将两个数组边排序边合并。子数组可以继续分为子数组，直到子数组长度为1时天然有序。合并过程则是将拆分的子数组依次合并，直到合并到原数组的长度即排序完成。
排序演示1
原数组：[9,18,0,0,-9,17,0,3,0,10,19,8,4,-7]，用归并排序为该数组排序
排序演示2
原数组：[-12,3,5,1,-1,-9,9,-12,-9,3,16,-10,4,-13,11]，用归并排序为该数组排序
代码实现
递归方式
/**
* 通过递归的方式实现归并排序
* @param arr 要排序的数组
* @param left 数组的左边界
* @param right 数组的右边界
*/
public static void mergeSortByRec(int[] arr,int left,int right){
//递归出口，left=right时，说明递归到了长度为1的数组，天然有序
if(left==right) return;
//计算中间的索引值，(left+right)/2。
// 之所以这么优化，是为了避免left+right的值大于int最大范围导致出现bug
int mid = left + ((right-left)>>1);
//把左半边的数组排好序
mergeSortByRec(arr,left,mid);
//把右半边的数组排好序
mergeSortByRec(arr,mid+1,right);
//把左右两边部分有序的数组合并
//System.out.println("索引为"+left+"-"+mid+"的左半数组 和 索引为"+(mid+1)+"-"+right+"的右半数组已经局部有序，将它们合并，使"+left+"-"+right+"整体有序");
merge(arr,left,mid,right);
//AlgorithmComparatorUtil.printIntArr(arr);//自己写的测试工具
System.out.println();
}
/**
* 将已经有序的左右两个数组合并
* @param arr 要合并的数组
* @param left 左半边数组的开始位置
* @param mid mid为左半边数组的结束位置，mid+1为右半边数组的开始位置
* @param right 右半边数组的结束位置
*/
public static void merge(int[] arr,int left,int mid,int right){
//左数组的索引指针
int leftIndex = left;
//右数组的索引指针
int rightIndex = mid+1;
//用来存放数据的临时数组
int[] tmpArr = new int[right-left+1];
//临时数组的索引指针
int tmpIndex = 0;
//比较左边跟右边数组的元素，把更小的元素放入临时数组，有一边完成排序时（索引越界时）结束
// 为了保证稳定性，相同的元素则左边优先
while(leftIndex<=mid && rightIndex<=right){
tmpArr[tmpIndex++] = arr[leftIndex]<=arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++];
}
//有一边排完了全部元素（即索引越界），把另一边的元素也全部排进去
while(leftIndex<=mid){
tmpArr[tmpIndex++] = arr[leftIndex++];
}
while(rightIndex<=right){
tmpArr[tmpIndex++] = arr[rightIndex++];
}
//把排好的临时数组覆盖原数组
for(int i=left;i<=right;i++){
arr[i] = tmpArr[i-left];
}
}
迭代方式
/**
* 用迭代的方式实现归并排序
* @param arr
*/
public static void mergeSort(int arr[]){
if(arr==null || arr.length<2) return;
//子数组的长度为1时自然有序，所以从1开始归并，每次归并 子数组长度*2
for(int subArrLen=1;subArrLen<arr.length;subArrLen*=2){
//需要合并数组的长度为subArrLen，左边界为left，右边界为right
int left = 0;
while(left < arr.length){
//给right赋值，为了避免越界，还要比较left+subArrLen*2-1和arr.length-1
int right = Math.min(left+subArrLen*2-1 , arr.length-1);
if(right-left+1 > subArrLen){//区间大于子数组的长度才合并，否则没意义
merge(arr,left,left+subArrLen-1,right);
}
left += subArrLen*2;
}
}
}
/**
* 将已经有序的左右两个数组合并
* @param arr 要合并的数组
* @param left 左半边数组的开始位置
* @param mid mid为左半边数组的结束位置，mid+1为右半边数组的开始位置
* @param right 右半边数组的结束位置
*/
public static void merge(int[] arr,int left,int mid,int right){
//左数组的索引指针
int leftIndex = left;
//右数组的索引指针
int rightIndex = mid+1;
//用来存放数据的临时数组
int[] tmpArr = new int[right-left+1];
//临时数组的索引指针
int tmpIndex = 0;
//比较左边跟右边数组的元素，把更小的元素放入临时数组，有一边完成排序时（索引越界时）结束
// 为了保证稳定性，相同的元素则左边优先
while(leftIndex<=mid && rightIndex<=right){
tmpArr[tmpIndex++] = arr[leftIndex]<=arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++];
}
//有一边排完了全部元素（即索引越界），把另一边的元素也全部排进去
while(leftIndex<=mid){
tmpArr[tmpIndex++] = arr[leftIndex++];
}
while(rightIndex<=right){
tmpArr[tmpIndex++] = arr[rightIndex++];
}
//把排好的临时数组覆盖原数组
for(int i=left;i<=right;i++){
arr[i] = tmpArr[i-left];
}
}
复杂度分析
时间复杂度
对于长度为n的数组，排序过程中，占有时间的地方有：将数组合并的过程，和辅助数组覆盖原数组的过程。
把长度为2k的子数组进一步分为两个长度为k的子数组。
对于长度为k的子数组进行合并和覆盖时：合并占用时间约等于k，覆盖占用时间为k
故总时间复杂度为：(n + n) + 2*(n/2 + n/2) + 4*(n/4 + n/4) + … + n*(1+1) ≈ O(n * log n)
空间复杂度
排序过程中用到的最大辅助空间为n，每次归并的过程都会申请对应长度的辅助空间，归并完成后释放。故整个排序过程的空间复杂度为：O(n)。
稳定性
由上面代码实现可以看出，排序过程不会改变相同元素的相对顺序，故归并排序是稳定的排序算法。
标签：归并,right,int,arr,详解,数组,排序,left From： https://blog.csdn.net/weixin_51372196/article/details/140350053