什么是快速排序?

菜园前端
• 阅读 497

原文链接:https://note.noxussj.top/?source=helloworld


什么是快速排序(quickSort)?

主要分成两部分实现,分区、递归操作。

分区

从数组中任意选择一个 "基准",所有比基准小的元素放在基准前面,比基准大的元素放在基本后面。

递归

递归地对基准前后的子数组进行分区。

算法步骤

  1. 首先获取数组的第一个值(作为基准)
  2. 遍历当前数组,从第二个值开始,比基准元素小的 push 到 left 数组,比基准元素大的 push 到 right 数组。
  3. 分别对 left 和 right 数组进行快速排序(递归)
  4. 直到当前进行快排的数组长度为 1
  5. 开始合并,返回排列好的数组
  6. 完成排序

动画演示链接

https://visualgo.net/zh/sorting

什么是快速排序?

示意图

什么是快速排序?

基础案例

  • 时间复杂度:O (n * logn)
  • 空间复杂度:O (1)
Array.prototype.quickSort = function () {
    const rec = (arr) => {
        if (arr.length <= 1) return arr

        const mid = arr[0]
        const left = []
        const right = []

        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < mid) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }

        return [...rec(left), mid, ...rec(right)]
    }

    const res = rec(this)

    res.forEach((n, i) => {
        this[i] = n
    })
}

const arr = [5, 4, 3, 2, 1]

arr.quickSort() // [1, 2, 3, 4, 5]

上方代码中递归的复杂度是 O (logn),只要是涉及到分成两半的都是 logn 。分区操作的时间复杂度为 O (n),因为循环遍历了 arr 数组。所以整体的时间复杂度为 O (n * logn)。空间复杂度为 O (1),因为没有线性增长的变量。

点赞
收藏
评论区
推荐文章
22 22
3年前
【排序算法动画解】简单选择排序
本文为系列专题的第13篇文章。1.2.3.4.5.6.7.8.9.10.11.12.在文章【】中,我们介绍了暴力排序和冒泡排序这两种排序算法,算是一个引子。同时指出暴力排序和冒泡排序的缺点硬伤。本文介绍的简单选择排序则“医治”了上面提到的暴力排序和冒泡排序的“硬伤”。核心思想:从数组的第一个元素开始,将其作为基准元素,然后找出基准
Wesley13 Wesley13
3年前
java常用类(2)
三、时间处理相关类Date类:计算机世界把1970年1月1号定为基准时间,每个度量单位是毫秒(1秒的千分之一),用long类型的变量表示时间。Date分配Date对象并初始化对象,以表示自从标准基准时间(称为“历元”(epoch),即1970年1月1日08:00:00GMT)以来的指定毫秒数。示例:packagecn.tanjian
Stella981 Stella981
3年前
C语言 快速排序 Quick Sort
算法描述:快速排序一般是选择数组的第一个数据为对称轴参考值pivot。按照大小数组分割成左右两个区间。然后对左右两个区间再进行递归排序,知道结束为止。例子演示:数组:43251,长度:5,对称轴参考值选择第一个数据4。比它小的我们放到它的右边,比它大的我们放到左边。设置左右两个工作位置。指向开头和末尾。第一轮:4325
Wesley13 Wesley13
3年前
Java面试总结(排序算法)
1.冒泡排序算法描述:两两比较,大的放后面2.选择排序算法描述:在m元数组中找到最小值的位置,然后将最小值的位置和第n(n0,1,2,....m1)位的值对调,排序k次则m元数组中前k(k<m)位的值已经排序好,m元数组中前k位的值不需要再进行排序,此时需要排序的元素只有mk个3.插入排序算
Wesley13 Wesley13
3年前
Mysql 表分区分类
针对Mysql数据库,表分区类型简析。【1】表分区类型(1)Range分区:按范围分区。按列值的范围区间进行分区存储;比如:id小于10存储在一个分区;id大于10小于20存储在另外一个分区;(2)List分区:按离散值集合分区。与range分区类似,不过它是按离散值进行分区。(3)Hash分区:按hash算法结果分区。对用户定义的表达式所返
Wesley13 Wesley13
3年前
C语言自学《五》
什么是数组数组是一组数目固定、类型相同的数据项数组中的数据称为元素比如longnumbers\10\;方括号中的数字定义了要存放在数组中的元素个数,称为数组维度数组有一个类型,它组合了元素的类型和数组中的元素个数,因此如果两个数组的元素个数、类型相同,这两个数组的类型就相同可以在数组名称后的方括号内使用索引值,索引值是从0开始
Wesley13 Wesley13
3年前
PHP
<?php/\\ \数据分析引擎 \分析向量的元素必须和基准向量的元素一致,取最大个数,分析向量不足元素以0填补。 \求出分析向量与基准向量的余弦值 \@author(http://my.oschina.net/arthor)Foyon \//\\ \获得向量的模 \
Wesley13 Wesley13
3年前
PHP快速排序(原地切分)
        快速排序是一种分治的排序算法,采用递归的思想,将数组元素分为两部分,选择切分元素,左右扫描数组,将大于切分元素的数据放在右边,小于切分元素的数据放在左边,直到扫描指针相遇,切分结束,同时递归调用,直到数组有序。      代码如下:<?phpfunctionquick_sort(array&$array,$l
菜园前端 菜园前端
1年前
什么是归并排序?
原文链接:什么是归并排序(mergeSort)?主要分成两部分实现,分、合操作:分:把数组分成两半,在递归地对子数组进行"分"操作,直到分成一个个单独的数合:把两个数组合并为有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组归并排序就是采用了
京东云开发者 京东云开发者
11个月前
时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队
归并排序归并排序遵循分治的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下:划分:分解待排序的n个元素的序列成各具n/2个元素的两个子序列,将长数组的排序问题转换为短数