您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

你应该知道的常用排序算法之快速排序

时间:2021-03-04 16:13:48  来源:  作者:

人生有涯,学海无涯

今天跟大家分享一个常用的排序算法——快速排序。我想大家在日常的工作或者面试的时候肯定经常会遇到很多排序算法,而且快速排序算法往往是这里面相对更好的排序算法,并且实现也非常简单。下面我们一起看下吧。

01、快速排序

我们先看看维基百科的解释:

快速排序(英语:QuickSort),又称划分交换排序(partition-exchange sort),简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序 n 个项目要 O(nlogn) 次比较。在最坏状况下则需要 O(n^2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。

02、算法思想

快速排序的算法思想是分而治之,将一个大的待排序列,分成两个子序列,然后采用递归的方式,依次将子序列也分成更小的子序列,依次进行,最后得到排序好的序列。算法的实现主要分成三步

  1. 找到基准点:
  2. 排列序列,将比基准点小的放在左边的子序列,将比基准点大的放在右边的子序列;
  3. 采用递归,依次重新选取基准点,在重复进行 1,2 步骤,得到最终的顺序序列

03、算法实现

/**
 * <br>
 * <b>Function:</b><br>
 * <b>Author:</b>@author 子悠<br>
 * <b>Date:</b>2019-09-23 01:07<br>
 * <b>Desc:</b>无<br>
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /**
     * 递归排序
     *
     * @param array 待排序列
     * @param left  左边起始位置
     * @param right 右边结束位置
     */
    private static void quickSort(int[] array, int left, int right) {
        if (left < right) {
            //根据基准点,找到分隔左右子序列的位置索引
            int position = position(array, left, right);
            //分别进行左右的递归
            quickSort(array, left, position - 1);
            quickSort(array, position + 1, right);
        }
    }

    /**
     * 找到中间
     *
     * @param array 待排序列
     * @param left  左边起始位置
     * @param right 右边结束位置
     * @return
     */
    private static int position(int[] array, int left, int right) {
        //找到基准点, 这里使用的是序列的第一个元素
        int base = array[left];
        while (left < right) {
            while (right > left && array[right] >= base) {
                right--;
            }
            //交互位置
            array[left] = array[right];
            while (left < right && array[left] <= base) {
                left++;
            }
            //交互位置
            array[right] = array[left];
        }
        //此时 left 与 right 是相等的
        array[left] = base;
        return left;
    }
}

运行结果:

1 1 2 2 3 3 4 5 6 7 8 8 9

从运行的结果我们看到,已经正常的排序结束了,说明这个算法已经满足了我们的要求,而且详细的代码分析也已经加上了注释,我想大家应该都能看懂。只要记住核心的几个点就可以了,这里我在重复说明一下:

  1. 先找基准点 base;
  2. 比较大小,比 base 小的放在左边序列,比 base 大的放在右边序列;
  3. 递归左右序列。

注意上面内部的两个 while 循环,这里是使用类似两个指针,分别从序列的左右两个端点开始往中间进行遍历,主要进行的第二步比较和赋值的操作。



Tags:快速排序   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
人生有涯,学海无涯今天跟大家分享一个常用的排序算法&mdash;&mdash;快速排序。我想大家在日常的工作或者面试的时候肯定经常会遇到很多排序算法,而且快速排序算法往往是这里面...【详细内容】
2021-03-04  Tags: 快速排序  点击:(182)  评论:(0)  加入收藏
1、引言今天的运气不是很好,再加上项目的压力。准备停止学习一周,等把项目这一关过了,再继续深入学习分享算法。后来吧今天遇到的事情都比较郁闷,也无心情继续开发项目。便想转...【详细内容】
2020-11-12  Tags: 快速排序  点击:(234)  评论:(0)  加入收藏
算法05:Golang快速排序Quick Sort1.什么是快速排序(Quick Sort)快速排序是由东尼&middot;霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要 &Omicron;(nlogn) 次比...【详细内容】
2020-10-12  Tags: 快速排序  点击:(78)  评论:(0)  加入收藏
在很多大厂的面试中,算法是最基本的要求,像基础的算法,冒泡,选择,插入等,基本上都会问到。很多同学往往忽略了其重要程度,只注重编程语言,小编并不建议这样子,今天我们来梳理一下算法...【详细内容】
2020-05-03  Tags: 快速排序  点击:(46)  评论:(0)  加入收藏
看似青铜实则王者很多人提起快排和二分都觉得很容易的样子,但是让现场Code很多就翻车了,就算可以写出个递归版本的代码,但是对其中的复杂度分析、边界条件的考虑、非递归改造、...【详细内容】
2019-11-27  Tags: 快速排序  点击:(68)  评论:(0)  加入收藏
冒泡排序时间之所以效率低,就是因为将所有数都一视同仁不做区分挨个比较,这是最普通的做事方法,所以效率也是最普通的,时间复杂度为N的平方;而归并排序效率高,则是采用了分治的思...【详细内容】
2019-10-22  Tags: 快速排序  点击:(93)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条