package com.dhcc.project;
public class Demo9 {
public static void main(String[] args) {
int[] arr = { 1, 3, 7, 9, 2, 4, 6 };
// 归并排序，一个数组分成两份，这两份都是有序的数组，对着两份进行排序。排序规则，当两边数组有相等元素的时候将左边数组元素位置不变，这样稳定。
// 排序的时候，用左边数组和右边数组比较。
Demo9.sort(arr, 0, 6);
}
public static void sort(int[] arr, int left, int right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid + 1, right);
}
public static void merge(int[] arr, int leftPtr, int rightPtr,
int rightBound) {
int i = leftPtr;
int j = rightPtr;
int k = 0;
int[] brr = new int[rightBound - leftPtr + 1];
while (i <= rightPtr - 1 && j < rightBound) {
brr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= rightPtr - 1)
brr[k++] = arr[i++];
while (j < rightBound)
brr[k++] = arr[j++];
for (int l = 0; l < rightBound; l++) {
System.out.println(brr[l]);
}
}
}
这个好难，代码也是有问题的，但是思路大致如此
