package com.xiaoxin.sort; import java.util.Arrays; public class quickSort_me { public static void main(String[] args) { int[] arr = {9,2,1,5,4,7,3,8}; quick(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } //递归方法 private static void quick(int[] arr, int l, int r) { if (l>=r){ return; } //先分区一次，得到第一次的基准点所在下标 int partition = partition2(arr, l, r); //先搞左边的 quick(arr,l,partition-1); //再搞右边的 quick(arr,partition+1,r); } //分区方法 单边循环 public static int partition(int[] arr, int l, int r){ int pv = arr[r]; // 基准点元素 int i = l; for (int j = l; j < r; j++) { if (arr[j] < pv) { if (i != j) { utils.swap(arr, i, j); } i++; } } if (i != r) { utils.swap(arr, r, i); } System.out.println(Arrays.toString(arr) + " i=" + i); // 返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界 return i; } //分区方法 双边循环 //每次返回基准点所在的数组下标，以确定下一次分区的左右区间 public static int partition2(int[] a ,int l, int h){ //基准点一直为最左边的元素pv，i，j指针在左右两头，分别寻找比pv大的和小的元素，i，j相遇时，基准点与i交换 int pv = a[l]; int i = l; int j = h; while (i < j) { // j 从右找小的 while (i < j && a[j] > pv) { j--; } // i 从左找大的 while (i < j && a[i] <= pv) { i++; } utils.swap(a, i, j); } utils.swap(a, l, j); System.out.println(Arrays.toString(a) + " j=" + j); return j; } }