基础排序算法之快速排序

快速排序（快排）贯彻了分治思想，将待排序的数组逻辑上（只是逻辑上分割，实际上一切操作都是在原数组上进行的，没有产生任何新数组）分割为小数组，再将小数组逻辑上分割为更小的数组，这些小数组与小数组之间是有序的，小数组中的元素也是有序的，那么原数组自然而然也是有序的

package com.scaler7.list;

import java.util.Arrays;

public class Sort {
    public static void main(String []args){
        int []arr = {4,6,1,3,9,10,7,2,8,5};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr){
        // 快速排序是基于分治思想，选取一个目标数，将所有比目标数小的置于数组左边，比它大的置于数组右边，然后再递归地对数组左右两边执行相同操作，直至每个子数组中只有一个元素

        quickSort(arr,0,arr.length-1);
    }
    
    public static void quickSort(int[] arr, int low, int high){
        // 当快慢指针指向同一个元素，说明此时只有一个元素，排序已经完成，退出递归
        if(low>=high)
            return;
        // 具体实现：选取一个目标数，快慢指针分别从尾部和头部扫描每个元素
        // 选取最左边的数为目标数
        int pivot=arr[low];
        int i=low;
        int j=high;
        // 当快慢指针重合时退出循环
        while(ipivot)
            	// 如果快指针指向的元素大于pivot，那么什么也不做，只将快指针向前移动一位
                j--;
            if(i