JavaScript 快速排序详解

时间:2022-12-11 14:15:34

使用的是《JavaScript数据结构与算法》一书中的快速排序,并加上自己的理解。

经测试,此算法的速度比内置的 sort 更快!而阮一峰的那个快排更像是归并排序,虽然写法简单很多,但是性能很差,数组太大还会爆栈。

// 原理:快速排序也使用分治的方法,将原始数组分为较小的数组(但它没有像归并排序那样将它们分割开)
// 1、从数组中选择中间一项作为主元
// 2、创建两个指针,左边一个指向数组第一个项,右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素,接着,移动右指针直到找到一个比主元小的元素,然后交换它们,重复这个过程,直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后。这一步叫作划分操作。
// 3、接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的子数组)重复之前的两个步骤,直至数组已完全排序。
const quickSort = (arr) => {
// 排序算法。每次接收的都是整个 arr,只是 left 和 right 在改变。每次排序只是对 left 和 right 之间的数进行排序
const quick = (arr, left, right) => {
let index; // 分割数组的索引
if (arr.length > 1) {
// 核心算法:两边指针往中间移,从左边找到比主元大的数,右边找到比主元小的数,然后交换两个数
let mid = Math.floor((left + right) / 2), // 选择中间项作为主元
midNum = arr[mid];
l = left, // 初始化两个指针
r = right;
console.log(arr, l, r, mid, midNum);
// 左指针比右指针小才执行
while (l <= r) {
// 从左侧开始找,找到一个比主元大的数
while (arr[l] < midNum) {
l++;
}
// 从右侧开始找,找到一个比主元小的数
while (arr[r] > midNum) {
r--;
}
// 如果比主元大的数的索引小于比主元小的数的索引,则交换这两个数
if (l <= r) {
[arr[l], arr[r]] = [arr[r], arr[l]];
// 交换完成,移动指针
l++;
r--;
}
}
index = l; // 以上执行完成后,左指针左边的数都是较小的数,右边的数都是较大的数。我们把左指针作为分割数组的索引 // 左索引小于分割索引,则对数组中左索引到分割索引部分进行排序
if (left < index - 1) {
quick(arr, left, index - 1);
}
// 右索引大于分割索引,则对数组中分割索引到右索引部分进行排序
if (index < right) {
quick(arr, index, right);
}
}
}
// 调用 quick 进行排序,因为是要对整个数组排序,所以传入 0 和 arr.length - 1
quick(arr, 0, arr.length - 1);
} let arr = [];
for (let i = 0; i < 10; i++) {
arr.push(Math.floor(Math.random() * 100));
}
console.time();
quickSort(arr);
// arr.sort(arr);
console.timeEnd();

JavaScript 快速排序详解的更多相关文章

  1. JavaScript事件详解-jQuery的事件实现(三)

    正文 本文所涉及到的jQuery版本是3.1.1,可以在压缩包中找到event模块.该篇算是阅读笔记,jQuery代码太长.... Dean Edward的addEvent.js 相对于zepto的e ...

  2. JavaScript事件详解-Zepto的事件实现(二)【新增fastclick阅读笔记】

    正文 作者打字速度实在不咋地,源码部分就用图片代替了,都是截图,本文讲解的Zepto版本是1.2.0,在该版本中的event模块与1.1.6基本一致.此文的fastclick理解上在看过博客园各个大神 ...

  3. JavaScript正则表达式详解(一)正则表达式入门

    JavaScript正则表达式是很多JavaScript开发人员比较头疼的事情,也很多人不愿意学习,只是必要的时候上网查一下就可以啦~本文中详细的把JavaScript正则表达式的用法进行了列表,希望 ...

  4. JavaScript正则表达式详解(二)JavaScript中正则表达式函数详解

    二.JavaScript中正则表达式函数详解(exec, test, match, replace, search, split) 1.使用正则表达式的方法去匹配查找字符串 1.1. exec方法详解 ...

  5. JavaScript事件详解-zepto的事件实现

    zepto的event 可以结合上一篇JavaScript事件详解-原生事件基础(一)综合考虑源码暂且不表,github里还有中文网站都能下到最新版的zepto.整个event模块不长,274行,我们 ...

  6. javascript 函数详解2 -- arguments

    今天我们接着上篇文章来继续javascript函数这个主题.今天要讲的是函数对像中一个很重要的属性--arguments. 相关阅读: javascript 函数详解1 -- 概述 javascrip ...

  7. &lbrack;原创&rsqb;JavaScript继承详解

    原文链接:http://www.cnblogs.com/sanshi/archive/2009/07/08/1519036.html 面向对象与基于对象 几乎每个开发人员都有面向对象语言(比如C++. ...

  8. javaScript基础详解(1)

    javaScript基础详解 首先讲javaScript的摆放位置:<script> 与 </script> 可以放在head和body之间,也可以body中或者head中 J ...

  9. javascript设计模式详解之命令模式

    每种设计模式的出现都是为了弥补语言在某方面的不足,解决特定环境下的问题.思想是相通的.只不过不同的设计语言有其特定的实现.对javascript这种动态语言来说,弱类型的特性,与生俱来的多态性,导致某 ...

随机推荐

  1. nodejs&plus;express&plus;jade给我baby做个小相册

    去年年底迎来了my little star.从此人生多了一个最重要的牵挂.生了宝宝全家人都太忙了.最近宝宝稍微大点了,终于有空可以研究下技术了.这是14年第一帖.废话不多了.开始吧 1.安装NTVS ...

  2. &num;ifdef 的技巧用法

    -- int _tmain(int argc, _TCHAR* argv[]) { #ifdef DEBUG cout<<"DEBUG has been defined&quot ...

  3. ExpandableListView getChildView 不执行,不显示子列表

    原因很简单: 在 GroupView 里面不要加入 button 等可点击空间,否则 和 点击 Groupview 展开相冲突. 去掉就好了getGroupView

  4. web调试技巧

    接触web不久,遇到了一些"奇怪"的问题,现将一些调试技巧总结如下:    1.欲添加某一样式,点击右键,查看源码    2.样式有问题,点击右键,审查元素 当然,还有一些经验总结 ...

  5. sql join 用法

    SQL JOIN 的用法   关于sql语句中的连接(join)关键字,是较为常用而又不太容易理解的关键字,下面这个例子给出了一个简单的解释 --建表table1,table2:create tabl ...

  6. Intellij-工程目录下隐藏不想显示的文件和文件夹

    File-->Editor-->File Types

  7. &lbrack;BZOJ2743&rsqb; &lbrack;HEOI2012&rsqb; 采花 &lpar;树状数组&rpar;

    Description 萧芸斓是Z国的公主,平时的一大爱好是采花. 今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花.花园足够大,容纳了n朵花,花有c种颜色(用整数1-c表示),且花是排成一 ...

  8. CSS之清除浮动&lpar;span&sol;clearfix&rpar;

    一.问题描述 web网页设计中,在div元素中有时候常伴有图文结合的post组件.为了使得文本在图像周围环绕,那么需要对图像区域使用float浮动.如果不做清除浮动,则会出现如下结果: 图像比文本高, ...

  9. sex在软件开发中的运用--SIX技术

    开篇:省略xxx字 keyword:sex . female, male .SIX ,sex integer extention technolgolsl 前言: 对于sex字段的研究,国内,国际尚为 ...

  10. 开源软件架构总结之——Asterisk(DSL、组件、多线程)

    Asterisk 1是基于GPLv2协议发布的一款开源电话应用平台.简单地说,这是一个服务端程序,用于处理电话的拨出.接入以及自定义流程. 一个人使用电话A呼叫另一个使用电话B的人.在此场景下,连接到 ...