算法入门-排序算法-快速排序-详解

一、核心思想

基本思想：从数组中选取一个元素f作为排序的参照物，除f之外的元素与f做比较，如果元素大于f，则将元素放到f后面，如果元素小于f，则将元素放到f前面。
参照物为f的排序完成后，将f之前、之后的元素作为新数组并按照上述基本思想进行同样的排序；
可以发现：每轮排序之后都可以确定一个元素的所属位置

二、过程分析

int[] nums={7,5,3,9,6,8,4};
将第0个元素作为参照物f，同时需要确定的是大于f元素与小于f的元素的边界lt（即lt表示小于f的元素的最右边的元素，lt的右边即为大于f的元素）；
初始情况f=nums[0]=7；lt=0
从i=1开始遍历数组与参照物f作比较，如果nums[i]<f则lt右移一位，如果i与lt不等，则交换i位置的元素与lt位置的元素（i与lt不相等是因为遍历过程中出现过大于f的元素，而lt表示的是小于f的元素的最右边的元素；将lt加一并交换lt与i位置的元素同样是因为lt表示的是小于f的元素的最右边的元素）；此过程遍历完成后的结果为：lt及lt之前的元素是小于f的，f之后的元素都是大于f的
以上遍历完成之后对f之前的数组及f之后的数组做同样的操作即可

三、代码

    @Test
    public void test13(){
        int[] nums={7,5,3,9,6,8,4};
        quickSort(nums,0,nums.length-1);
    }
    // 交换元素位置
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
    
    public void quickSort(int[] nums,int left,int right){
        if (left>=right){
            return;
        }
        int index=partition(nums,left,right);
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);
    }
    
    public int partition(int[] nums,int left,int right){
        int f=nums[left];       
        int lt=left;
        for (int i=left+1;i<=right;i++){
            if (nums[i]<f){
                // 当前元素小于f，则将lt右移，保证lt是小于f的最右侧的元素
                lt++;              
                // i与lt不相等是因为遍历过程中出现过大于f的元素，lt经过自增之后指向大于f的第一个元素
                if (lt!=i){         
                    // 交换lt与i位置的元素，保证lt指向小于f的最右侧元素
                    swap(nums,lt,i);   
                }
            }
        }
        swap(nums,left,lt);
        return lt;
    }