package com.jiucaiyuan.net.algrithm.sort;

/**

 * <pre>

 * 快速排序

 *  一个数组arr，选择一个数做为基准m，小于等于m的数放在数组左边，大于m的数放在数组右边

 *  左侧递归上述过程

 *  右侧递归上述过程

 *

 *  荷兰国旗问题：  <m,=m,>m

 *

 * 时间复杂度 O(N*logN)，空间复杂度 O(logN)

 * 如果选择的基准数比较偏时，时间复杂度O(N^2)  空间复杂度O(N)

 * </pre>

 * Created by jiucaiyuan on 2022/3/5.

 */



public class QuickSort {

    /**

     * 快速排序算法

     * @param arr

     * @param l

     * @param r

     * @return

     */

    public static void quickSort(int[] arr,int l,int r){

        if(l<r){

            swap(arr,l+(int)(Math.random()*(r-l+1)),r);

            //分成左右两块，左侧比某个数小，右侧比某个数大

            int[] p = partition(arr,l,r);

            //对左侧进行快排

            quickSort(arr,l,p[0]);

            //对右侧进行快排

            quickSort(arr,p[1],r);

        }

    }



    /*

     * 对数组进行分区：左侧比

     * @param arr  数组

     * @param l  左元素

     * @param r  右元素

     * @return   小于某个数的有边界和大于某个数的左边界下标

     */

    private static int[] partition(int[] arr, int l, int r) {

        if(arr == null || arr.length<2){

            return new int[]{l,l};

        }

        //小于基准数的右边界

        int less = l-1;

        //大于基准数的左边界

        int more = r;

        while(l<more){

            if(arr[l]<arr[r]){

                swap(arr,++less,l++);

            }else if (arr[l] == arr[r]){

                l++;

            }else{

                swap(arr,l,--more);

            }

        }

        return new int[]{less,more};

    }



    /**

     * 交换两个不相等的数，如果相等，会都变成0

     * @param arr

     * @param l

     * @param r

     */

    private static void swap(int[] arr,int l,int r){

        if(l==r){

            return;

        }

        //交换两个不同数

        arr[l] = arr[l]^arr[r];

        arr[r] = arr[l]^arr[r];

        arr[l] = arr[l]^arr[r];

    }



    public static void main(String[] args){

        int[] arr = {12,5,3,7,3,8,4,3,2,2,6,8,6,0,9,5,3};

        print(arr);

        quickSort(arr, 0,arr.length-1);

        print(arr);

    }

    private static void print(int[] arr) {

        if(arr == null ){

            return;

        }

        for(int a : arr){

            System.out.print(a+"\t");

        }

        System.out.println();

    }

}