百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程网 > 正文

上个厕所的功夫,就学会了“快速排序”算法

yuyutoo 2024-10-12 01:09 6 浏览 0 评论

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像BAT、字节、美团等知名IT公司都喜欢考查快速排序原理和手写源码。

一、概念

快速排序,顾名思义就是一种以效率快为特色的排序算法,快速排序(Quicksort)是对冒泡排序的一种改进。由英国计算机专家:托尼·霍尔(Tony Hoare)在1960年提出。


二、基本思想

从排序数组中找出一个数,可以随机取,也可以取固定位置,一般是取第一个或最后一个,称为基准数。然后将比基准小的排在左边,比基准大的放到右边;

如何放置呢,就是和基准数进行交换,交换完左边都是比基准小的,右边都是比较基准大的,这样就将一个数组分成了两个子数组,然后再按照同样的方法把子数组再分成更小的子数组,直到不能分解(子数组只有一个值)为止。以此达到整个数据变成有序序列。

快速排序采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod),现在各种语言中自带的排序库很多使用的都是快速排序。
空间复杂度

快速排序是一种原地排序,只需要一个很小的栈作为辅助空间,空间复杂度为O(log2n),所以适合在数据集比较大的时候使用。
时间复杂度

时间复杂度比较复杂,最好的情况是O(n),最差的情况是O(n2),所以平时说的O(nlogn),为其平均时间复杂度。

  • O(n):理想的情况,每次划分所选择的中间数恰好将当前序列几乎等分,经过log2n趟划分,便可得到长度为1的子表。这样,整个算法的时间复杂度为O(nlog2n)。
  • O(n2):最坏的情况,每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子表中一个为空表,另一子表的长度为原表的长度-1。这样,长度为n的数据表的快速排序需要经过n趟划分,使得整个排序算法的时间复杂度为O(n2)。

三、算法步骤

1.选定一个基准数(一般取第一位数字)作为中心点(Pivot);2.将大于Pivot的数字放到Pivot的左边;3.将小于Pivot的数字放到Pivot的右边;4.第一次排序结束后,分别对左右子序列继续递归重复前三步操作。

四、具体示例

实例数组:arr[] = {19,97,9,17,1,8};

1.取出基准数Pivot,以该值为中心轴。

快速排序中的规则:右边有坑,就从左边Arr[L + n]取值来填,反之左边有坑,则从右边Arr[R - n]取值来填;

2.从左边取的基准值,左边的Arr[L]就空出来了,则先从右侧取值来填,从最右侧下标开始,在Arr[R] 取到第一个值“8”;

3.将取到的Arr[R]与基准值比较,发现小于基准值,则插入到Arr[R],占到了基准值Pivot的位置上。

4.然后从Arr[L+1]的位置取出值,继续向右匹配并排序,将匹配到的值(匹配规则如下)插入到右侧Arr[R]的空位置上;

匹配规则:大于基准值的插入到Arr[R],如果小于,则直接忽略并跳过,继续向右取值,直到坐标L和坐标R重合。

5.发现取出的值大于Pivot(基准值),则将其插入到Arr[R]。

6.左边有坑,从右边Arr[R-1]继续匹配,Arr[R-1] = 1,小于基准值,则插入到Arr[L]的坑中;

7.右边有坑了,继续从左边取值继续匹配,则取到Arr[L+1] = 9,小于基准值,则忽略并跳过,继续找Arr[L + 1]继续匹配。

8.继续从左边坐标 + 1 取值继续匹配,则取到Arr[L] = 17,又小于基准值,则忽略并跳过,继续找Arr[L + 1]继续匹配。

9.最后L坐标和R坐标重合了,将Pivot基准值填入

10.至此,快速排序第一轮完整流程结束,分出了左右子序列,左边都是小于Pivot基准值的,右边都是大于Pivot基准值的。

11.继续对左、右序列递归进行处理,一直缩小到左、右都是一个值,则快速排序结束,最终得出顺序数组{1,8,9,17,19,97};中间递归流程这里不再赘述。

五、快排代码

@java代码

package com.softsec.demo;
 
/**
 * Created with IDEA
 *
 * @Author Chensj
 * @Date 2020/5/17 19:04
 * @Description
 * @Version 1.0
 */
public class quickSortDemo {
 
    public static void main(String[] args) {
        // 创建测试数组
        int[] arr = new int[]{19,97,9,17,1,8};
        System.out.println("排序前:");
        showArray(arr); // 打印数组
        // 调用快排接口
        quickSort(arr);
        System.out.println("\n" + "排序后:");
        showArray(arr);// 打印数组
    }
 
    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        int len;
        if(array == null
                || (len = array.length) == 0
                || len == 1) {
            return ;
        }
        sort(array, 0, len - 1);
    }
 
    /**
     * 快排核心算法,递归实现
     * @param array
     * @param left
     * @param right
     */
    public static void sort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        // base中存放基准数
        int base = array[left];
        int i = left, j = right;
        while(i != j) {
            // 顺序很重要,先从右边开始往左找,直到找到比base值小的数
            while(array[j] >= base && i < j) {
                j--;
            }
 
            // 再从左往右边找,直到找到比base值大的数
            while(array[i] <= base && i < j) {
                i++;
            }
 
            // 上面的循环结束表示找到了位置或者(i>=j)了,交换两个数在数组中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
 
        // 将基准数放到中间的位置(基准数归位)
        array[left] = array[i];
        array[i] = base;
 
        // 递归,继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置,无需再处理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }
 
    /**
     * 数组打印
     * @param num
     */
    private static void showArray(int[] num) {
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }
}

返回结果:

排序前:
19 97 9 17 1 8 
排序后:
1 8 9 17 19 97 
Process finished with exit code 0

@python代码

#快速排序 传入列表、开始位置和结束位置
def quick_sort( li , start , end ):
    # 如果start和end碰头了,说明要我排的这个子数列就剩下一个数了,就不用排序了
    if not start < end :
        return
 
    mid = li[start] #拿出第一个数当作基准数mid
    low = start   #low来标记左侧从基准数始找比mid大的数的位置
    high = end  #high来标记右侧end向左找比mid小的数的位置
 
    # 我们要进行循环,只要low和high没有碰头就一直进行,当low和high相等说明碰头了
    while low < high :
        #从high开始向左,找到第一个比mid小或者等于mid的数,标记位置,(如果high的数比mid大,我们就左移high)
        # 并且我们要确定找到之前,如果low和high碰头了,也不找了
        while low < high and li[high] > mid :
            high -= 1
        #跳出while后,high所在的下标就是找到的右侧比mid小的数
        #把找到的数放到左侧的空位 low 标记了这个空位
        li[low] = li[high]
        # 从low开始向右,找到第一个比mid大的数,标记位置,(如果low的数小于等于mid,我们就右移low)
        # 并且我们要确定找到之前,如果low和high碰头了,也不找了
        while low < high and li[low] <= mid :
            low += 1
        #跳出while循环后low所在的下标就是左侧比mid大的数所在位置
        # 我们把找到的数放在右侧空位上,high标记了这个空位
        li[high] = li[low]
        #以上我们完成了一次 从右侧找到一个小数移到左侧,从左侧找到一个大数移动到右侧
    #当这个while跳出来之后相当于low和high碰头了,我们把mid所在位置放在这个空位
    li[low] = mid
    #这个时候mid左侧看的数都比mid小,mid右侧的数都比mid大
 
    #然后我们对mid左侧所有数进行上述的排序
    quick_sort( li , start, low-1 )
    #我们mid右侧所有数进行上述排序
    quick_sort( li , low +1 , end )
 
 
#入口函数
if __name__ == '__main__':
    li = [19,97,9,17,1,8]
    quick_sort(li , 0 , len(li) -1 )
    print(li)

六、总结

快速排序是当前最为流行的排序算法之一,各大公司面试中频频出现,希望通过这篇文章,让你对快速排序知识点有一定的了解,在日后面试或各种考试中对你有所帮助!


目前在职Java开发,如果你现在也在学习Java,在入门学习Java的过程当中缺乏基础入门的视频教程, 可以关注并私信我:01。免费领取2020年最新Java基础精讲视频教程,学习手册,面试题,开发工具,PDF文档书籍教程,以下资料截图:

关注并私信我:01。即可领取以上学习资料。

相关推荐

国产RISC-V终端Sipeed Lichee Console4A上架,1699元起

IT之家12月11日消息,国内著名开源硬件厂商Sipeed矽速科技推出RISC-V终端LicheeConsole4A,售价1699元(不带LM4A模块)-3299元。Li...

H3C交换机常用配置命令

1、配置主机名...

ThinkPad老版Bios中英文对应详解

ThinkPad老版Bios中文对应详解。解决方案:...

澳大利亚Console Connect与非洲数据中心达成战略合作,增强整个非洲的数据连接

据techafricanews网11月13日报道,在2024年非洲科技节上,澳大利亚ConsoleConnect与非洲数据中心共同宣布了一项具有里程碑意义的战略合作协议,该协议致力于提升非洲大陆关键...

多功能调焦 腾龙TAP-in Console延期发售

最新消息传出,腾龙TAP-inConsole(modeltap-01)多功能调焦器由于生产方面原因原本预计3月24日发售延迟至3月30日,腾龙的这款调焦器功能类似于适马的USBDock调焦底座,...

关于交换机上存在的不同接口介绍(一)

生活中常见的电子设备有很多,其中明交换机主要起到的是连接的作用,上面有非常多的接口,下面就一起来看看这些不同的接口作用是什么。1、RJ-45接口这是我们见的最多、应用最广的一种接口类型,它属于双绞线以...

颜值更高?微软新推精英版Xbox One手柄

本月,微软的XboxOne升级了更强大的版本——XboxOneEliteconsole(精英版?),升级版的控制手柄功能更强大,可以主导你的客厅;从曝光的图片上看得出,新版XboxOneE...

“全球首个”:Console Connect为全球物联网项目推出连接解决方案

据DevelopingTelecoms2月27日报道,在MWC2023上,全球网络即服务(NaaS)平台ConsoleConnect推出了“全球首个”私有连接解决方案,可帮助企业在全球范围内动态...

密码遗忘专题——Console口密码遗忘

如果忘记了Console口密码,用户可以通过以下两种方式来设置新的Console口密码:方法一:通过STelnet/Telnet登录设备修改Console口密码。...

为锐捷路由器交换机开启web和telnet,实现轻松管理

笔者上一篇文章写了关于锐捷二层交换机配置教程,那么接下来讲一下锐捷的路由交换设备配置web、telnet技巧。同样,今天的教程也是基于命令行,比较简单,适合新手小白进行学习。准备工作配置前准备:con...

C# - 类文件构成,C#基本语法,Console属性与方法 007

类文件(.cs)构成类文件主要分为引用命名空间与自己项目的命名空间...

Console OS系统帮你在PC上自由切换Windows和安卓应用

通过ConsoleOS你可以在你的PC上安装自己喜欢的安卓游戏,需要时之间切换回Windows进行其他工作,ConsoleOS能够完全利用你的PC硬件配置,该系统可以安装在PC的内置硬盘里,也可以...

交换机通过串口线console口登录设备

一、功能简介:PC端通过设备的Console口登录,实现对第一次上电的设备进行基本配置和管理。...

(每日持续更新)jdk api之Console基础、应用、实战

博主18年的互联网软件开发经验,从一名程序员小白逐步成为了一名架构师,我想通过平台将经验分享给大家,因此博主每天会在各个大牛网站点赞量超高的博客等寻找该技术栈的资料结合自己的经验,晚上进行用心精简、整...

KFC推出“真正的次世代主机”KFConsole!真4K/120帧

今天KFCGaming官方推特发布了一则“主机”宣传片,正式公布了旗下名为KFConsole的全新主机产品。并宣称:游戏的未来就在这里,介绍真正的次世代主机!根据官方介绍,本款KFC主机功能强大,支...

取消回复欢迎 发表评论: