快速排序——单边循环实现方式

单边循环快排(lomuto 洛穆托分区方案)

核心思想：

选择最右元素为基准点元素j指针负责找到比基准点小的元素，一旦找到则与i进行交换i指针维护小于基准点元素的边界，也是每次交换的目标索引最后基准点与i交换，i即为分区位置

JAVA代码实现

import java.util.Arrays;public class QuickSort {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 low,int high){//当low>=high时，说明分区内只有1个或没有元素，此时分区结束，排序完成if (low>=high) {return;}//调用排序方法开始分区int p = partition(a, low, high);//拿到下一轮分区的边界//上一轮轮分区结束后，又开始下一轮分区，使用递归的方式完成quick(a,low,p-1);//左边分区的范围确定quick(a,p+1,high);//右边分区的范围确定}//排序方法private static int partition(int[] a,int low,int high){//1. 选择最右边的元素作为基准点元素int pv=a[high];//2.i维护小于基准点元素的边界，也是每次交换的目标索引，从最左边的元素开始int i= low;//3. j负责找到比基准点小的元素，一旦找到就与i交换,同时i的索引也自然加1for (int j = low; j < high; j++) {if (a[j]<pv) {//当i=j时,我们再交换其实没有意义，所以可以优化一下,减少一次交换if (i!=j) {swap(a,i,j);}i++;}}//4.最后基准点与i交换，i即为分区位置,至此一轮分区结束//同样的当i=h时交换没有意义，优化一下，减少一次交换if (i!=high) {swap(a,high,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;}}

输出结果

如果觉得《快速排序——单边循环实现方式》对你有帮助，请点赞、收藏，并留下你的观点哦！