唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

快速排序算法又称划分交换排序,简称快排,是一种排序算法。在平均状态下排序n个项目需要O(nlogn)次比较,在最坏的情况下则需要O(n^2)次比较,不过这种情况并不常见。事实上呢,快速排序通常要比其他算法更快,因为它的内部循环可以在大部分的架构上很有效率地达成。

快速排序的动画演示:

快排动画

快速排序算法采用的是分治法的思想,将一个完整的待排序的序列一分为二,分而治之,并递归的对子序列继续排序。

可以这么简单的描述快速排序的步骤:

1、从数组中随机的选择一个元素,称之为“基准” (pivot)。

2、从数组中按顺序取出元素与基准比较,如果取出的元素比基准小,则放置入基准之前的数组,而如果取出的元素比基准大,则放入基准之后的数组,如果取出的元素与基准相等,则与基准放置于同一数组中。该操作可以称之为分区(partition)操作。

3、在第一遍排序完之后,再递归的对基准之前的数组与基准之后的两个数组进行排序,直至拆分至最小的数组大小,则可视为排序完成,按照调用栈返回结果。则排序完成。

介绍完步骤之后,来看看用javaScript如何来实现快速排序:

/**
 *  快速排序算法
 *  最优时间复杂度 O(nlogn)
 *  平均时间复杂度 O(nlogn)
 *  最坏时间复杂度 O(n^2)
 *  是否稳定 否
 */
class QuickSort {
  sort(originalArray) {
    const array = [...originalArray];

    // 如果数组小于等于一个元素的时候就返回,可以理解为已经排好序
    if (array.length <= 1) {
      return array;
    }

    // 定义左右两个数组
    const leftArray = [];
    const rightArray = [];

    // 取出第一个元素作为比较对象
    const pivotElement = array.shift();
    const centerArray = [pivotElement];

    // 把数组切分为左中右三部分
    while (array.length) {
      const currentElement = array.shift();

      if (currentElement === pivotElement) {
        centerArray.push(currentElement);
      } else if (currentElement < pivotElement) {
        leftArray.push(currentElement);
      } else {
        rightArray.push(currentElement);
      }
    }

    // 对左右两个数组递归排序
    const leftSortedArray = this.sort(leftArray);
    const rightSortedArray = this.sort(rightArray);

    // 将返回的已经排好序的左中右三个数组合并 完成排序
    return leftSortedArray.concat(centerArray, rightSortedArray);
  }
}

// 排序测试
const array = [6, 10, 1, 9, 4, 8, 2, 7, 3, 5];
const quick = new QuickSort();
const res = quick.sort(array);
console.log(res);

最后温馨的提醒各位同学,一定要牢牢的掌握快速排序算法,直到能随意白板手写快排为止。

javaScript版快排源码

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

1846
来自专栏专知

关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3 题目 Rotate an array of n elements to...

3688
来自专栏欧阳大哥的轮子

常用的数学函数以及浮点数处理函数

在编程中我们总要进行一些数学运算以及数字处理,尤其是浮点数的运算和处理,这篇文章主要介绍C语言下的数学库。而其他语言中的数学库函数的定义以及最终实现也是通过对C...

1482
来自专栏小樱的经验随笔

HUST 1586 数字排列

1586 - 数字排列 时间限制:1秒 内存限制:128兆 91 次提交 36 次通过 题目描述现有n个k位的数字,你的任务是重新安排数字每一位的位置,使得...

29012
来自专栏北京马哥教育

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;...

4984
来自专栏趣谈编程

快速排序(基础版)

1583
来自专栏dalaoyang

递归基础思想

1633
来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

8009
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

1081
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

3275

扫码关注云+社区