分治 + 填数
先从后向前找,再从前向后找
package com.ykk.StrategyFarm.CacheManager.Factor;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("");
sort(0, arr.length - 1, arr);
}
public static void sort(int start, int end, int[] arr) {
if (start >= end) {
return;
}
System.out.println(" " + start + " > " + end);
int X = arr[start];
int i = start;
int j = end;
while (i < j) {
//从后向前
for (; j > start && i < j; j--) {
if (arr[j] < X) {
arr[i] = arr[j];
break;
}
}
//从后向前
for (; i < end && i < j; i++) {
if (arr[i] > X) {
arr[j] = arr[i];
break;
}
}
}
arr[i] = X;
for (int n = 0; n < arr.length; n++) {
System.out.print(arr[n] + " ");
}
System.out.println("");
sort(start, i - 1, arr);
sort(i + 1, end, arr);
}
}