一：归并排序原理
归并排序利用的是分治的思想实现的，对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的子序列，之后对子序列排序，最后再用递归方法将排好序的子序列合并成为有序序列。合并两个子序列时，需要申请两个子序列加起来长度的内存，临时存储新的生成序列，再将新生成的序列赋值到原数组相应的位置。
二：归并排序复杂度
平均时间复杂度均为O(nlogn)。
三：归并排序的实现
package Study.paixu;
import java.util.Arrays;
/**
* 归并排序
*/
public class gbpx {
public static void main(String[] args) {
int []px = {1,2,5,7,6,8,3,4};
sort(px);
System.out.println(Arrays.toString(px));
}
public static void sort(int[] arr){
int[] temp = new int[arr.length];
sort(arr,0,arr.length-1,temp);
}
public static void sort(int[] arr,int left,int right,int[] temp){
if(left < right){
int mid = (left + right)/2;
sort(arr,left,mid,temp);
sort(arr,mid+1,right,temp);
merege(arr,left,mid,right,temp);
}
}
public static void merege(int[] arr,int left,int mid,int right,int[] temp){
int i = left;
int j = mid+1;
int t = 0;
while(i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){
temp[t++] = arr[i++];
}
while(j<=right){
temp[t++] = arr[j++];
}
t = 0;
while(left <= right){
arr[left++] = temp[t++];
}
}
}
image.png
