数据结构与算法-快速排序

什么是快速排序
快速排序是对冒泡排序的一种改进，在1960年由C. A. R. Hoare提出采用划分交换排序的算法。

算法原理
1、首先选取基准元素
2、定义左右两个指针 i、j，左指针是当前分段数组最小索引，右指针是当前分段数组最大索引
3、分段数组中的左指针往右移动找到大于基准元素的索引，右指针往左移找到小于基准元素的索引
4、在左右指针未相遇之前需要交换i、j元素，左右指针相遇则将基准元素与相遇点（分隔位置）元素交换
5、重复2、3、4步骤直到所有分段数组的基准元素大于左边元素，小于右边元素

时间复杂度
1、最理想情况下O(nlogn)
2、最差情况下O(n^2)
综合时间复杂度为O(n^2)

算法稳定性（提供模拟图）
例如数组【2，2，1，3，5，8】
1、首次排序选定基准元素 2，指定左右指针 i = 0，j=5

2、左指针右移动找到不小于于2的元素 2，右指针左移动找不大于2的元素 1，此时i=1 j=2 交换IJ位置

当前数组结构为：[2, 1, 2, 3, 5, 8]

3、左指针继续右移动，右指针继续左移动，i = 3 j=2位置，满足 i>=j 结束指针移动，将基准元素插入j位置

当前数组结构为：[2, 1, 2, 3, 5, 8]
故算法不稳定

4、然后对以当前分隔点 j= 2处将左边元素为左数组进行快速排序，右边元素作为右数组进行快速排序，以此递归从而使每个分段数组都满足排序规则。

小试牛刀
1、创建快速排序工具类，每次递归找到分隔点，左右两边数组进行排序

/**
 * 快速排序
 * @author senfel
 * @version 1.0
 * @date 2022/12/9 11:29
 */
@Slf4j
public class QuickSort {

    /**
     * 快速排序升序算法入口
     * @param array
     * @author senfel
     * @date 2022/12/9 11:30
     * @return void
     */
    public static void sort(int[] array){

        if(null == array || array.length ==1){
            return;
        }
        log.error("快速排序升序开始排序,当前数组结构为：{}", Arrays.toString(array));
        quickSort(array,0,array.length-1);

    }


    /**
     * 排序逻辑
     * @param array
     * @param left
     * @param right
     * @author senfel
     * @date 2022/12/9 11:31
     * @return void
     */
    private static void quickSort(int[] array, int left, int right) {
        if(left >= right){
            //左索引大于等于右索引结束排序
            return;
        }
        //快速排序算法原理就是基准元素分隔数组，把数组分为多个小块进行排序
        //当前数组排序 + 获取分隔点
        int partition = getPartition(array, left, right);
        //分别对分隔点两边元素进行快速排序
        quickSort(array,left,partition-1);
        quickSort(array,partition+1,right);
    }


    /**
     * 当前数组排序 + 获取分隔点
     * @param array
     * @param left
     * @param right
     * @author senfel
     * @date 2022/12/9 11:35
     * @return int
     */
    private static int getPartition(int[] array, int left, int right) {
        //缓存左右指针和基准元素（默认第一个元素）
        int i = left;
        int j = right;
        int element = array[left];
        while (true){
            //左指针右移动获取大于基准元素的元素
            while (i <= j && element > array[++i]){}
            //右指针左移动获取小于基准元素的元素
            while (j >= i && element < array[j]){j--;};
            if(i >= j){
                //相遇结束移动，此时j索引或者i--索引位置就是分隔位置
                break;
            }else{
                //交换位置
                exchange(array,i,j);
                log.error("快速排序升序交换位置,当前数组结构为：{}", Arrays.toString(array));
            }
        }
        //结束时候将基准元素放置在分隔点
        exchange(array,left,j);
        log.error("快速排序升序交换位置,当前数组结构为：{}", Arrays.toString(array));
        return j;
    }


    /**
     * 交换两个索引元素位置
     * @param array
     * @param i
     * @param j
     * @author senfel
     * @date 2022/12/9 11:44
     * @return void
     */
    private static void exchange(int[] array, int i, int j) {
        if(null == array || i > array.length-1 || j > array.length -1){
            return;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

    }

}

2、提供测试方法

public static void main(String[] args) {
    int[] array = {2,2,1,3,5,8};
    sort(array);
}

3、查看测试结果并展示每次排序数组结构

09:09:48.365 快速排序升序开始排序,当前数组结构为：[2, 2, 1, 3, 5, 8]
09:09:59.393 快速排序升序交换位置,当前数组结构为：[2, 1, 2, 3, 5, 8]
09:10:07.760 快速排序升序交换位置,当前数组结构为：[2, 1, 2, 3, 5, 8]
09:10:08.279 快速排序升序交换位置,当前数组结构为：[1, 2, 2, 3, 5, 8]
09:10:08.779 快速排序升序交换位置,当前数组结构为：[1, 2, 2, 3, 5, 8]
09:10:08.821 快速排序升序交换位置,当前数组结构为：[1, 2, 2, 3, 5, 8]