何为快速排序？

    快速排序是指从集合中，选出一个轴，对数组的所有元素，以轴为标准，左右两边分别比轴大或小的数，然后再已左右两边的数据作为子集合，选出子集合的轴，子集合再以轴为核心，进行排序，如此递归，知道每个集合仅有一个元素未知，然后就完成了数据排序。

快速排序从小到大代码样例

package com.booby.algorithm.quick;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 单轴快排，从小到大。
 *
 * 思路：左右两个指针，左指针向右，右指针向左，当发现左边指针所指的数比右边大。则进行交换。
 *
 * @author: lizt
 * @date: 2020/8/24 08:55
 **/

public class MinToMax {
//    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};
    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};
//    public static final Integer[] arr = {1,3,8,7,4,5};

    public static void sorted(Integer[] arr, int leftBound, int rightBound){
        if (leftBound >= rightBound){
            return;
        }
        int mid = partition(arr, leftBound, rightBound);
//        Utils.print(arr);
        sorted(arr, leftBound, mid - 1);
        sorted(arr, mid + 1, rightBound);
    }
// [1,3,8,7,4,5]  [1,3,4,7,8,5]
    public static int partition(Integer[] arr, int leftBound, int rightBound){
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound -1;
        // =决定首元素是否交换
        while (left <= right){
            // left <= right  = 决定轴的交换
            // arr[left] <= pivot 决定如果集合元素和轴的值相等，则跳过不处理
            while (left <= right && arr[left] <= pivot){
                left++;
            }
            while (left <= right && arr[right] > pivot){
                right--;
            }
            if (left < right){
                Utils.swap(arr, left, right);
            }
        }
        // 交换轴
        Utils.swap(arr, left, rightBound);
        return left;
    }

    public static void main(String[] args) {
        sorted(arr, 0, arr.length-1);
        Utils.print(arr);
    }
}

快速排序从大到小代码样例

package com.booby.algorithm.quick;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 单轴快排，从大到小
 *
 * @author: lizt
 * @date: 2020/8/28 08:42
 **/

public class MaxToMIn {
    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};

    public static void sorted(Integer[] arr, int leftBound, int rightBound){
        if (leftBound >= rightBound){
            return;
        }
        int mid = partition(arr, leftBound, rightBound);
        sorted(arr, leftBound, mid -1);
        sorted(arr, mid + 1, rightBound);
    }

    /**
     * 功能描述:
     *
     * @param arr
     * @param leftBound  左边界集合索引值
     * @param rightBound 用边界结合索引值
     * @return: java.lang.Integer 左边界
     * @author: lizt
     * @date: 2020/8/28 09:08
    **/
    public static Integer partition(Integer[] arr, int leftBound, int rightBound){
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound - 1;
        while (left <= right){
            while (left <= right && arr[left] >= pivot){
                left++;
            }
            while (left <= right && arr[right] < pivot){
                right--;
            }
            if (left < right){
                Utils.swap(arr, left, right);
            }
        }
        // 交换轴
        Utils.swap(arr, left, rightBound);

        return left;
    }

    public static void main(String[] args) {
        sorted(arr, 0, arr.length - 1);
        Utils.print(arr);
    }
}

快速排序稳定性？

    快速排序需要轴两边的数据交换位置，不能保证相同数字相对顺序，所以为排序不稳定。

快速排序复杂度

快速排序注意点

    快速排序先全部集合数据选中轴，然后部分集合，再集合。集合逐步缩小。而归并排序，先递归到小集合归并，然后弹出上一级再归并。

、