归并排序的时间复杂度：O（n log（n））
归并排序的思想：将两个或两个以上有序的序列合并成一个大序列，一般使用2-路归并排序即将邻近的两个序列归并起来。
归并排序实现方法
1）将待排序的序列分成两份，再进行分割成为若干独立的子序列
2）将两两相邻的序列进行归并排序
3）合并两个序列
Java代码的实现
/**
* 归并排序
* @return
*/
public static int[] guiBing( int[] arr ) {
int[][] arry = new int[arr.length][1];
/**
* 拆成子数组，每个子数组里面只有一个数，所以只有一个数的数组就是有序数组
*/
for(int i = 0; i < arr.length; i++){
arry[i] = new int[] { arr[i] };
}
/**
* 合并有序的子数组，一直到合并到一个为止
*/
int[][] arr3 = arry;
for(;;) {
if( arr3.length > 1 ) {
arr3 = SortClass.getHalf(arr3);
}else {
break;
}
}
return arr3[0];
}
/**
* 压缩自身数组元素至原来的一半
* @return
*/
public static int[][] getHalf(int[][] arr) {
int[][] result;
if( arr.length % 2 == 1 ) {
result = new int[ arr.length / 2 + 1][];
}else {
result = new int[ arr.length / 2][];
}
for( int i = 0; i < result.length; i++) {
if( (i * 2 + 1) >= arr.length ) {
result[i] = mergeArr(arr[i*2],new int[] {});
}else {
result[i] = mergeArr(arr[i*2],arr[i*2 + 1]);
}
}
return result;
}
}
/**
* 入参是两个有序的由小到大的数组
* @param arr1
* @param arr2
* @return 返回由小到大的有序数组
*/
public static int[] mergeArr(int[] arr1, int[] arr2) {
int[] result = new int[ arr1.length + arr2.length ];
int startArr1 = 0;
int startArr2 = 0;
int insertIndex = 0;
for(; ; ) {
if( startArr1 > arr1.length - 1 || startArr2 > arr2.length - 1 ) {
break;
}
if( arr1[startArr1] <= arr2[startArr2] ) {
result[insertIndex] = arr1[startArr1];
startArr1 += 1;
}else {
result[insertIndex] = arr2[startArr2];
startArr2 += 1;
}
insertIndex += 1;
}
if( startArr1 > arr1.length - 1 ) {
for( int k = startArr2; k < arr2.length; k++ ) {
result[insertIndex] = arr2[k];
// startArr2 += 1;
insertIndex += 1;
}
}else {
for( int k = startArr1; k < arr1.length; k++ ) {
result[insertIndex] = arr1[startArr1];
startArr1 += 1;
insertIndex += 1;
}
}
return result;
}```
提示
建议使用for循环，使用递归不仅浪费存储空间也会造成安全隐患。