利用额外两个数组存储,数值划分的两部分。 再重新放回
定义指针(注意位置为待移动位置) 划分区间 递归排序
import java.lang.Integer;
import java.util.HashMap;
import java.util.*;
import java.lang.*;
/**
* 注意当选取j分界,则不能选取j当基准值。
* (可以选取i|一半,否则出现死循环)
* quickSort(arr, l, j);
* quickSort(arr, j+1, r);
*
*/
public class Solution {
public static void quickSort(int[] arr , int l , int r) {
if (l >= r) return;
int val = arr[l];
int i = l-1, j = r+1; // 提前预留指针空间
while (i < j) {
do i++; while (arr[i] < val);
do j--; while (arr[j] > val);
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, l, j);
quickSort(arr, j+1, r);
}
public static void main(String[] args) {
int[] arr = {1,2,3,2,2,2,5,4,2};
quickSort(arr, 0, arr.length-1);
for (int i : arr) {
System.out.println(i);
}
}
}