快速排序的实战实现及其改进方法探讨

1：让小于基准点的元素进入一个分区，大于基准点的元素进入另一个分区
2：当分区完成后，基准点元素的位置就是其最终位置

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

package bin_find;
import java.util.Arrays;

public class quick_sort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        quick(a,0,a.length-1);
    }
    public static int quick(int []a,int l,int h){
        int pv=a[h];//基准点元素
        //i相当于是一个分割线，位于它左边的所有元素都是小于基准元素的，位于它右边的元素都是大于基准元素的
        int i=l;
        //j变量根据索引从左往右一旦找到比当前基准元素小的元素，则与索引值为i的元素进行交换
        for(int j=l;j<h;j++){
            if(a[j]<pv){
                swap(a,i,j);
                //交换完成，i++  --->下一个需要排序的元素
                i++;
            }
        }
        //基准点和i的元素进行交换,一轮分区完成
        swap(a,h,i);
        System.out.println(Arrays.toString(a));
        return 0;
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

[3, 2, 1, 4, 7, 9, 8, 5]

package bin_find;
import java.util.Arrays;

public class quick_sort {
    public static void main(String[] args) {
        int[] a={5,3,7,2,1,9,8,4};
        recurrence(a,0,a.length-1);
    }

    //该方法的作用是：递归实现分区排序直至整个数组有序，通过每轮排序返回的下标值进而确定这次排序的范围
    public static void recurrence(int []a,int l,int h){
        if(l>=h){//递归结束的条件:当区间只有一个元素或者没有元素时，有等号的原因是由于当l恰好等于返回的索引值，此时p再减1就使得h<l
            return;
        }
        int p=quick(a,l,h);//基准点的索引值
        recurrence(a,l,p-1);//左边分区范围：第一个元素~基准元素的前一个元素
        recurrence(a,p+1,h);//右边分区范围：基准元素的下一个元素~最后一个元素
    }
    public static int quick(int []a,int l,int h){
        int pv=a[h];
        int i=l;
        for(int j=l;j<h;j++){
            if(a[j]<pv){
                //优化1：
                if(i!=j) {//当j找到小于基准点的值和i指向的元素不是同一个元素时，发生交换，这样能够减少不必要的交换次数
                    swap(a, i, j);
                }
                i++;
            }
        }
        //优化2：
        if(i!=h){//当基准点元素和i指向的元素不是同一个元素时，发生交换，这样能够减少不必要的交换次数
        swap(a,h,i);
        }
        System.out.println(Arrays.toString(a));
        return i;
    }
    public static void swap(int arr[],int i,int j){
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}

[3, 2, 1, 4, 7, 9, 8, 5]
[1, 2, 3, 4, 7, 9, 8, 5]
[1, 2, 3, 4, 7, 9, 8, 5]
[1, 2, 3, 4, 5, 9, 8, 7]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]

1：选择最左元素作为基准点元素
2：j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至i,j相交
3:最后基准点与i(此时i与j相等)交换，i即为分区位置