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

旧城等待， 2024-03-31 17:48 65阅读 0赞

**什么是快速排序**  
快速排序是对冒泡排序的一种改进，在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  
![在这里插入图片描述][7e2b8b6e636144ba8b656148e579b75b.png]

2、左指针右移动找到不小于于2的元素 2，右指针左移动找不大于2的元素 1，此时i=1 j=2 交换IJ位置  
![在这里插入图片描述][2be6fbe0537e4b47a2c0aeb9e76e11a1.png]

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

3、左指针继续右移动，右指针继续左移动，i = 3 j=2位置，满足 i>=j 结束指针移动，将基准元素插入j位置  
![在这里插入图片描述][2e48f99e8d9c43e692a4ee1f793c4841.png]

当前数组结构为：\[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\]

[7e2b8b6e636144ba8b656148e579b75b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/492ec090eb42420eb4ed8dcbc1b5af85.png
[2be6fbe0537e4b47a2c0aeb9e76e11a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/138c92e9c6544dc1b09c6d6209e47800.png
[2e48f99e8d9c43e692a4ee1f793c4841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3a68e3b9305d412d8d050538b0271a81.png