单边循环快排(lomuto 洛穆托分区方案 )
选择最右元素作为基准点元素
j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
i 指针维护小于基准点元素的边界，也是每次交换的目标索引
最后基准点与 i 交换，i 即为分区位置
public static void main(String[] args) {int[] a = {5, 3, 7, 2, 9, 8, 1, 4};quick(a, 0, a.length-1);}public static void quick(int[] a, int l, int h) {if (l >= h) {return;}int p = partition(a, l, h);quick(a, l, p-1);quick(a, p+1, h);}public static int partition(int[] a, int l, int h) {int pv = a[h]; // 基准点元素int i = l;for(int j = l; j < h; j++) {if (a[j] < pv) {if (i != j) {swap (a, i , j);}i++;}}if (i != h) {swap (a, h, i);}System.out.println(Arrays.toString(a)+ "i=" + i);// 返回值代表了基准点元素的正确索引，用它确定下一轮分区的边界return i;}public static void swap(int[] a, int i, int j) {int t = a[i];a[i] = a[j];a[j] = t;}
双边循环快排（不完全等价于hoare 霍尔分区方案）
1.选择最左元素作为基准点元素
2.j指针负责从右到左找比基准点小的元素，i指针负责从左到右找比基准点大的元素，一旦找到，二者交换，直到i=j
3.最后基准点要与i（此时i，j 相交）交换元素，i即为分区位置
注意：基准点元素在最左边 ，在循环时一定要保证 j >i
public static void main(String[] args) {int[] a = {5, 3, 7, 2, 9, 8, 1, 4};quick(a, 0, a.length-1);}public static void quick(int[] a, int l, int h) {if (l >= h) {return;}int p = partition(a, l, h);quick(a, l, p-1);quick(a, p+1, h);}public static int partition(int[] a, int l, int h) {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++;}if(i != j) {swap(a,i,j);}}swap(a,l,i);System.out.println(Arrays.toString(a)+ "j=" +j);return j;}public static void swap(int[] a, int i, int j) {int t = a[i];a[i] = a[j];a[j] = t;}
如果觉得《单边 双边循环快速排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
