/**
* 归并排序
* 归并就是合并的意思
*
* @author 小流慢影
* @date 2023年3月17日
*/
public class MergeSort {
public static void main(String[] args) {
int[] array = {5, 4, 3, 1, 2, 13, 12, 10, 11, 9, 7, 8, 6, 3, 5};
System.out.println("原数组:" + Arrays.toString(array));
int[] newArray = mergeSort(array, 0, array.length - 1);
System.out.println("新数组:" + Arrays.toString(newArray));
}
/**
* 归并排序
* @param array 待排数组
* @param start 开始位置
* @param end 结束位置
* @return 排好序的新数组
*/
public static int[] mergeSort(int[] array, int start, int end) {
// 边界条件判断:如果开始位置和结束位置相等,直接把值放到新的数组返回
if (start == end) {
return new int[]{array[start]};
}
// 取中间点
int middle = (start + end) / 2;
// 递归操作:对中间点左边的数组进行排序
int[] leftArray = mergeSort(array, start, middle);
// 递归操作:对中间点右边的数组进行排序
int[] rightArray = mergeSort(array, middle + 1, end);
// 对上面左边和右边排好序的数组最后再进行一次合并排序操作
return lastMergeSort(leftArray, rightArray);
}
/**
* 最后合并排序
* @param leftArray 左边排好序的数组
* @param rightArray 右边排好序的数组
* @return 合并后排好序的新数组
*/
private static int[] lastMergeSort(int[] leftArray, int[] rightArray) {
// 创建一个新数组,长度等于左右数组之和
int[] newArray = new int[leftArray.length + rightArray.length];
// 新数组的下标,从0开始
int newIndex = 0;
// 左边数组的下标,从0开始
int leftIndex = 0;
// 右边数组的下标,从0开始
int rightIndex = 0;
// 左下标的值与右下标的值进行比较,更小的值赋给新的数组
while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
newArray[newIndex++] =
leftArray[leftIndex] <= rightArray[rightIndex]
? leftArray[leftIndex++]
: rightArray[rightIndex++];
}
// 如果右数组弄完了,则直接把左数组剩下的都赋给新的数组
while (leftIndex < leftArray.length) {
newArray[newIndex++] = leftArray[leftIndex++];
}
// 如果左数组弄完了,则直接把右数组剩下的都赋给新的数组
while (rightIndex < rightArray.length) {
newArray[newIndex++] = rightArray[rightIndex++];
}
return newArray;
}
}
还没有评论,来说两句吧...