变量:
left、right、privot、temp[]、leftIndex、k
思路:
代码:
import java.util.Arrays;public class Queue8 {public static void main(String[] args) {int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};sort(arr,0,arr.length-1);System.out.print(Arrays.toString(arr)); }public static void sort(int[] arr, int left, int right) {
// if(left >= right) {
// return;
// }
// int mid = (left + right)/2;
// sort(arr,left,mid);
// sort(arr, mid + 1, right);
// int[] temp = new int[arr.length];
// int i = left;
// int j = mid + 1;
// int t = 0;
// while(i <= mid && j <= right) {
// if(arr[i] <= arr[j]) {
// temp[t] = arr[i];
// i++;
// t++;
// }else {
// temp[t] = arr[j];
// j++;
// t++;
// }
// }
// while(i <= mid) {
// temp[t] = arr[i];
// i++;
// t++;
// }
// while(j <= right) {
// temp[t] = arr[j];
// j++;
// t++;
// }
// int k = 0;
// int tempIndex = left;
// while(tempIndex <= right) {
// arr[tempIndex] = temp[k];
// k++;
// tempIndex++;
// }if(left >= right) {return;}int mid = (left + right) / 2;sort(arr,left,mid); sort(arr, mid + 1, right);int k = 0;int i = left;int j = mid + 1;int[] temp = new int[arr.length];while(i <= mid && j <= right) {if(arr[i] < arr[j]) {temp[k] = arr[i];k++;i++;}else {temp[k] = arr[j];k++;j++;}}while(i <= mid) {temp[k] = arr[i];i++;k++;}while(j <= right) {temp[k] = arr[j];j++;k++;}int leftIndex = left;int index = 0;while(leftIndex <= right) {arr[leftIndex] = temp[index];index++;leftIndex++;}}
}