[数据结构与算法]【Java 快速排序】

这是一个从网上找到的图解。

先设置一个基准数，这个基准数可以是任意位置的，这里我们选择第一个数为基准数，即6，然后进行一个类似归并的操作分成左子组和右子组 然后分别再对两边进行同样的操作。

```Java

import java.util.Arrays;
import java.util.Scanner;

public class Quick {
   
    /*
    数组元素i与j交换位置
     */
    public static void exch(Comparable[] a,int i,int j){
         Comparable t =a[i];
         a[i] =a[j];
         a[j] =t;
    }
 /*
        比较v元素是否小于w元素
     */
    public static boolean less (Comparable v,Comparable w){
        return v.compareTo(w) <0;
    }
    //对数组内的元素进行排序
    public static void sort (Comparable[] a){
        int lo =0;
        int hi =a.length-1;
        sort(a,lo,hi);
    }
    //对数组内的元素进行排序lo 到hi之间的元素排序
    public static void sort (Comparable[] a,int lo ,int hi){
    if (hi<=lo){
        return;
    }
    //需要对数组中lo元素索引到hi索引处的元素进行分组（左边和右边）；
        int partition = partition(a, lo, hi);//返回的分界值的索引
        //左偏排序
         sort(a,lo,partition-1);

        //右边排序
        sort(a,partition+1,hi);
    }
    public static int partition(Comparable[] a,int lo,  int hi){
        //确定分界值
     Comparable key = a[lo];
        //定义两个指针，分别指向第一个待切分元素的最小索引处和最大索引处的下一个位置
         int left =lo;
         int right =hi+1;
         //切分
        while (true){
            //先从右边往左边扫描，移动right指针，找到一个比分解值小的元素，停止
            while(less(key,a[--right])){
              if (right==lo){
                  break;
              }
            }
            //再从左边往右边扫描，移动left指针，找到一个比分界值大的元素，停止
            while(less(a[++left],key)){
                 if (left==hi){
                     break;
                 }
            }
            //判断left>=right，如果是则证明扫描完毕结束循环，不是则进行元素交换
            if (left>=right){
                break;
            }else {
                exch(a,left,right);
            }
        }
      //交换分界值
        exch(a,lo,right);
        return right;

    }

    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
         Integer n =sc.nextInt();
      Integer  [] arr = new Integer[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] =sc.nextInt();
        }
        sc.close();
        Quick.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

6
6 5 6 4 32 1
[1, 4, 5, 6, 6, 32]

```