快速排序的详解

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

@快速排序详解

提示：以下是本篇文章正文内容，下面案例可供参考

1.首先选定待排序数组的第一个元素为基准值val

2.当 i 向后遍历过程中，分情况讨论
<2.1>如果当前遍历到的元素arr[i] > v 时，i++，红色区域增加即可；

i++后，就把大于等于v的元素加入到红色区域，i继续向后遍历；
<2.2>如果在遍历的过程中，arr[i]

 for (int i = l+1; i <=r ; i++) {
            if (arr[i]  
3.整个集合扫描完毕，整个区间就被我们分隔为以下情况：
 
 4.经过以上步骤，arr[j]左侧元素均小于v，arr[j]之后的元素均 大于等于v，分区完成。继续在小于v的区间和大于v的区间继续递归上述过程，直至整个集合有序。
 
二、代码实现 
代码如下（示例）：
 
import java.util.Arrays;


public class QuickSort {
    
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length-1);
    }
    
    private static void quickSortInternal(int[] arr, int l, int r) {
        //先获取分区点：经过分区函数后，某个元素落在了最终的位置
        //分区点左侧元素均小于该元素，分区点右侧元素均大于等于该元素
        if (r-l<=15){
            //优化点，在元素小于15时，直接插入排序优化算法
            insertSort(arr,l,r);        
            return;
        }
        //分区函数,最终返回在[l，r]区间上分区点元素索引
        int p=partition(arr,l,r);
        //在分区元素左侧区间递归
        quickSortInternal(arr,l,p-1);
        //在分区元素右侧区间递归
        quickSortInternal(arr,p+1,r);
    }

    
    private static int partition(int[] arr, int l, int r) {
        //基准值
        int val=arr[l];
        //arr[l+1...j] < val
        //arr[j+1...i) >= val
        // i 表示当前正在扫描的元素索引
        int j=l;
        for (int i = l+1; i <=r ; i++) {
            if (arr[i] l&& arr[j] 
总结
 1.基准值默认选择左侧区间的第一个元素，也可以是其他位置元素；
 2.在快速排序中，当数组元素小于等于15时，进行插入排序优化算法；
 3.区间的定义一定要明确，边界值的判断要清晰。