這里直接轉(zhuǎn)載文章【https://www.cnblogs.com/chengxiao/p/6194356.html】
代碼實(shí)現(xiàn)
package com.yc.day04;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int arr[] = {8,4,5,7,1,3,6,2};
int temp[] = new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
System.out.println("遞歸排序后："+ Arrays.toString(arr));
}
//分+合
public static void mergeSort(int[]arr,int left,int right,int[] temp){
if(left<right){
int mid = (left+right)/2;
//向左遞歸分
mergeSort(arr,left,mid,temp);
//向右遞歸分
mergeSort(arr,mid+1,right,temp);
//合并
merge(arr,left,mid,right,temp);
}
}
//合并函數(shù)
/**
* arr:原始數(shù)組
* left:左邊有序序列的起始索引值
* mid:中間索引值
* right:最右邊元素的索引值
* temp:零時(shí)數(shù)組
*
* */
public static void merge(int[]arr,int left,int mid,int right,int[]temp){
int i = left;
int j = mid+1;
int t = 0;
//1.先將左右兩邊有序的數(shù)據(jù)按照規(guī)則填充到temp數(shù)組中
//直到左邊或者右邊數(shù)據(jù)處理完畢
while (i<=mid&&j<=right){
if(arr[i]<=arr[j]){
temp[t] = arr[i];
i++;
t++;
}else {
temp[t] = arr[j];
j++;
t++;
}
}
//2.將有剩余元素的一邊有序數(shù)據(jù)依次填充到temp中
while(i<=mid){
temp[t] = arr[i];
i++;
t++;
}
while(j<=right){
temp[t] = arr[j];
j++;
t++;
}
//3.將temp數(shù)組拷貝到arr中
t = 0;
int tempLeft = left;
while(tempLeft<=right){
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
