您现在的位置是:首页 > 正文

【数据结构与算法】:交换排序之快速排序(手绘图解+LeetCode原题)

2024-02-01 00:55:16阅读 2

一、快速排序

1.什么是快速排序?

快速排序是交换排序的一种,本质上快速排序就是采用“分而治之”的策略(分治法),将问题规模减小,再而对问题分别进行处理的排序算法。

2.快速排序的基本原理。

快速排序的原理:在已有元素中,任选一个元素作为“基准”,根据“基准”,将未排序元素划分为两个子序列,一个子序列的元素均小于基准元素,而另一个子序列的元素均大于基准元素,然后递归地对这两个子序列进行排序。

快速排序示意图(44为基准):
在这里插入图片描述

3.实现快速排序的具体过程。

①选取一个元素作为基准,与末尾元素交换位置。
②设置两个指针(Low和High),分别指向首元素与倒数第二个元素。
在这里插入图片描述
③Low指针由左向右扫描,其位置左侧放置的都是遍历过的或交换过的小于基准的元素;
—High指针从右向左扫描,其位置右侧放置的都是遍历过的或交换过的大于基准的元素。
—首先是Low指针向后扫描,遇到大于基准的元素停止;
—然后是High指针向前扫描,遇到小于基准的元素停止。
④在指针还未错位时(在 Low < High 时),将 High 和 Low 指向的元素交换位置。
在这里插入图片描述
⑤重复上述操作,直至 High指针 和 Low指针 错位
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
⑥错位后停止,将基准元素与指针Low指向元素交换位置,至此,我们成功将小于基准的元素放在其左,大于基准的元素放于其右!
——这代表我们成功完成了一次划分,以基准为边界分别划分成小于和大于基准的两个子序列。
在这里插入图片描述
⑦递归地对两个子序列,用同样的方法进行快速排序即可。

二、算法优化

需注意:
—在特殊情况下,比如在序列基本有序的情况下,若每次划分得到的两个子序列都是1比(N-1)的情况时,快速排序执行时间复杂度接近于冒泡排序的O(N²)。
—为了避免最坏结果,我们需要在下标为Low,High,(Low+High)/ 2的三个元素中取得中间值元素作为序列的基准,这样有可能避免最坏情况。

三、快速排序代码实现(优化后)。

import java.util.Arrays;

/**
 * @author .29.
 * @create 2022-09-09 21:37
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {85,12,59,36,62,44,43,94,7,35,52};//案例
        String str1 = Arrays.toString(arr);
        Qsort(arr,0,arr.length - 1);        //进行快速排序
        String str2 = Arrays.toString(arr);            //转换为字符串方便输出展示

        System.out.println(str1);                      //原序列输出
        System.out.println(str2);                      //快速排序后
    }

    public static void Qsort(int[] arr,int left,int right){
        if(left < right){
            int Low;                             //左边界
            int High;                            //右边界
            int Pivote;                          //基准
            Pivote = Median3(arr,left,right);    //获取基准

            Low = left;                          //需排序首元素的前一位(后续指针会优先向后移动)
            High = right - 1;                    //需排序尾元素的后一位(后续指针会优先向前移动)
            while(true){
                //指针优先向后移动,指向需排序首元素,若元素小于基准,继续后移
                while(arr[++Low] < Pivote);       
                //指针优先向前移动,指向需排序尾元素,若元素大于基准,继续前移
                while((Low<High) && arr[--High] > Pivote);
                
                if(Low < High) swap(arr,Low,High);//指针未错位,停止扫描后,元素交换位置
                else break;                       //指针错位,结束循环
            }

            if(Low < right)
            swap(arr,right-1,Low);              //将基准与错位后的Low指向元素交换位置

            Qsort(arr,left,Low-1);          //递归地对划分好的左序列用同样方法快速排序
            Qsort(arr,Low+1,right);          //递归地对划分好的右序列用同样方法快速排序
        }
        }

    //用来交换元素的方法(函数)
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static int Median3(int[] arr,int left,int right){
        int center = left + ((right-left) >> 1);      //相当于(left+right)/2
        if(arr[left] > arr[center])         //如果首元素小于中间元素
            swap(arr,left,center);           //交换位置

        if(arr[left] > arr[right])          //如果首元素小于尾元素
            swap(arr,left,right);            //交换位置

        if(arr[center] > arr[right])        //如果中间元素小于尾元素
            swap(arr,center,right);          //交换位置
        
        //经过上述操作,此时arr[left] <= arr[center] <= arr[right]
        //将基准放置在倒数倒数第一个元素(不放在最后是因为末尾的arr[right]大于基准
        swap(arr,center,right - 1);
        //现在首元素小于基准,尾元素大于基准,只需要考虑left+1到right-2的情况(right-1是基准)
        return arr[right-1];//返回被选为基准的元素
    }

控制台输出:
在这里插入图片描述

四、算法分析

时间复杂度

快速排序时间复杂度分析较为复杂。
最好情况下,每次划分都得到等长的子序列,每一层递归比较的时间复杂度为O(N),而递归层次深度为O(log2N),即最好情况是O(Nlog2N)。
最差时间复杂度上文有解释过,为O(N²)。

五、快排思想在实际题目中的运用

(更新于:2022.9.10)

题目一、剑指Offer 40.最小的k个数

LeetCode原题链接:剑指Offer 40.最小的k个数
题目描述:

输入整数数组 arr ,找出其中最小的 k 个数。
例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]

示例 2:
输入:arr = [0,1,2,1], k = 1
输出:[0]

解题思路:
经过上文的讲解,我们知道了,快速排序就是选定一个基准,通过一定操作让小于基准的元素放在基准左侧子序列,将大于基准的元素放在基准右侧子序列的排序算法。

题目的要求是:找出数组中最小的k个数,是不是觉得有什么地方十分相似?当我们的第k个数是快速排序的基准时,加上基准左侧的子序列,正是要求的最小的k个数…

所以解决问题的关键点就在于:
我们把基准及其左侧子序列的元素个数记作num
当num等于预期需要的数量k,输出划分好的序列即可。
当num大于预期需要的数量k,我们递归地对左序列进行同样的快排操作。
当num小于预期需要的数量k,我们递归地对基准之后与第k个元素之前的序列进行操作。(此时预期的数量就变为k-num了,因为num个数已经划分好,只需要划分剩下的元素,直至达到预期)

建议在理解代码时,画图辅助理解,特别是快排划分的那部分,有助于清晰地理解快排划分左子序列的具体过程。

实现代码:

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Qselect(arr,0,arr.length-1,k);//利用快排思想,将最小的k个数放在序列前列
        int[] Oput = new int[k];      //开辟一个大小为K的空间
        for(int i = 0;i < k; ++i){    //循环地将最小的k个数放入空间
            Oput[i] = arr[i];
        }
        return Oput;                 
    }

    //快速选择的递归函数(方法)
    public void Qselect(int[] arr,int L,int R,int k){
        if(L >= R)                           
        return;

        int p = getPivote(arr,L,R);      //获取基准元素下标
        int num = p-L+1;                 //左侧小于基准的子序列的元素个数
        //(基准划分的 左子序列元素 <= 基准 < 右子序列元素)
            if(num == k ){               //若左子序列元素个数等于预期的数量k
                return;                  //直接返回的就是最小的k个数
            }else if(num > k){           //若左子序列元素个数超过预期的数量k
                Qselect(arr,L,p-1,k);    //递归地用快速排序继续划分序列
            }else{                       //若左子序列元素个数低于预期的数量k
            //递归地用快速排序划分基准右侧的序列,除去已划分好的个数num,预期数量改为k-num
                Qselect(arr,p+1,R,k-num);
            }
    }

    //随机选取基准,并用于快排的函数(方法)
    public int getPivote(int[] arr,int L,int R){
        int pivote = (int)(Math.random()*(R-L+1)+L);//序列中任取元素为基准
        swap(arr,pivote,R);                         //基准与尾元素交换
        return Qsort(arr,L,R);                      //完成一次快排划分,返回基准
    }

    //快速排序的函数(只考虑左子序列的情况)
    //此方法建议画图辅佐理解
    public int Qsort(int[] arr,int L,int R){
        int Low = L-1;                      //小于区域的边界
        int High = R;                       //尾元素,即基准元素下标
        for(int l = L;l < High; l++){       //从左向右扫描
            if(arr[l] <= arr[High]){        //如果扫过元素小于基准元素,即符合要求
                Low++;                      //小于区域边界向右移动
                swap(arr,Low,l);            //交换区域边界元素与扫过的元素
 //说明:当边界内元素小于基准,相当于与自身交换,当边界内元素大于基准,相当于将小于基准的元素换进来
            }
        }
        swap(arr,R,Low+1);                 //将基准与小于区域的下一位交换位置,表示完成一次划分
            return Low+1;                  //返回记住下标。
    }

    //用于交换元素位置的函数(方法)
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

提交结果:
在这里插入图片描述
总结,只要理解了基本的解题思路,问题就不算难,重要的还是要记住快速排序的基本模式是如何的。

网站文章

  • node多版本管理 —— gnvm

    windows支持的node多版本管理 Available Commands: version :: 输出当前gnvm的版本 install :: 安装指定版本的nodejs uninstall ::...

    2024-02-01 00:55:10
  • 数据备份失败的五个原因及解决办法

    磁盘数据备份是任何数据保护策略的最重要的工作,但是,根据一些估计,一半以上的备份要么全部失败,要么就部分失败。当你在查找备份失败的原因时,相同的问题总是不断地重复出现。下面是一个关于引起备份失败的常见问题的清单,清单中所列问题的...

    2024-02-01 00:55:02
  • v-if 绑定的数组或对象属性变化不响应问题解决详解

    v-if 绑定的数组或对象属性变化不响应问题解决详解

    v-if 绑定的数组或对象属性变化不响应问题解决详解

    2024-02-01 00:54:56
  • libevent实现https服务器 热门推荐

    libevent实现https服务器 参考老外服务器代码: + https://github.com/ppelleti/https-example + 确保libevent在2.1.2之上版本。 + 确保系统安装openssl,确保libevent_openssl.so存在 + 搭建支持htt

    2024-02-01 00:54:20
  • 计数排序(counting sort)

    计数排序(Counting sort)是一种稳定的线性时间排序算法。计数排序使用一个额外的数组 C ,其中第i个元素是待排序数组A中值等于 i的元素的个数。然后根据数组 C 来将 A中的元素排到正确的位置。计数排序特征当输入的元素是n个 0 到k 之间的整数时,它的运行时间是Θ\ThetaΘ (n+k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度...

    2024-02-01 00:54:14
  • JAVA中四种线程池

    JAVA中四种线程池

    四种线程池newFixedThreadPoolnewCachedThreadPoolnewSingleThreadExecutornewScheduledThreadPool newFixedThre...

    2024-02-01 00:53:40
  • 轻量级日志管理系统-loki 简单部署

    轻量级日志管理系统-loki 简单部署

    使用grafana开发的loki工具,10分钟手动搭建一个轻量级日志管理系统

    2024-02-01 00:53:32
  • 测试开发工程师面试总结(二)——算法篇

    算法也属于常见面试内容之一,但基本不会超过《剑指offer》的范围,在此附上一篇简书上整理的内容: 第二版java解法 常见的面试题包括以下几类:字符串操作,文件输入输出流及统计,矩阵操作,单例模式等。 1.针对字符串的操作:如字符串反转、字符串去重、含有左右括号的字符串匹配。 含有左右括号的字符串匹配的题目及代码如下: 给定一个字符串,其中的字符只包含三种括号:花...

    2024-02-01 00:53:04
  • 适合 Go 新手学习的开源项目——在 GitHub 学编程

    适合 Go 新手学习的开源项目——在 GitHub 学编程

    作者:HelloGitHub-小鱼干&amp;卤蛋 故事要从 2007 年说起。因为受够了 C++ 煎熬的 Google 首席软件工程师 Rob Pike 召集 Robert Griesemer 和 ...

    2024-02-01 00:52:57
  • 怎么制作gif动态图 QQ动态表情包怎么制作

    怎么制作gif动态图 QQ动态表情包怎么制作

    在平时的聊天中经常会使用到GIF动图,不仅仅可以缓解气氛,还很有趣,那这些动态图是如何制作的呢?没有想象的那么难,今天来看看怎么制作的吧! 1、先准备好素材,要制作什么样的动图,可以是图片也可以是...

    2024-02-01 00:52:50