JavaScript实现in-place思想的快速排序方法

快速排序，又称划分交换排序。以分治法为策略实现的快速排序算法。

本文主要要谈的是利用javascript实现in-place思想的快速排序

分治法：

在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。（摘自维基百科）

快速排序的思想

数组中指定一个元素作为标尺，比它大的放到该元素后面，比它小的放到该元素前面，如此重复直至全部正序排列。

快速排序分三步：

选基准：在数据结构中选择一个元素作为基准(pivot)

划分区：参照基准元素值的大小，划分无序区，所有小于基准元素的数据放入一个区间，所有大于基准元素的数据放入另一区间，分区操作结束后，基准元素所处的位置就是最终排序后它应该所处的位置

递归：对初次划分出来的两个无序区间，递归调用第 1步和第 2步的算法，直到所有无序区间都只剩下一个元素为止。

现在先说说普遍的实现方法（没有用到原地算法）

function quickSort(arr) {
if (arr.length <= 1) return ;
//取数组最接近中间的数位基准，奇数与偶数取值不同，但不印象，当然，你可以选取第一个，或者最后一个数为基准，这里不作过多描述
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
//左右区间，用于存放排序后的数
var left = [];
var right = [];
console.log('基准为：' + pivot + ' 时');
for (var i = 0; i < arr.length; i++) {
console.log('分区操作的第 ' + (i + 1) + ' 次循环：');
//小于基准，放于左区间，大于基准，放于右区间
if (arr[i] < pivot) {
left.push(arr[i]);
console.log('左边：' + (arr[i]))
} else {
right.push(arr[i]);
console.log('右边：' + (arr[i]))
}
}
//这里使用concat操作符，将左区间，基准，右区间拼接为一个新数组
//然后递归1，2步骤，直至所有无序区间都 只剩下一个元素 ，递归结束
return quickSort(left).concat([pivot], quickSort(right));
}
var arr = [14, 3, 15, 7, 2, 76, 11];
console.log(quickSort(arr));
/*
* 基准为7时，第一次分区得到左右两个子集[ 3, 2,] 7 [14, 15, 76, 11];
* 以基准为2，对左边的子集[3,2]进行划分区排序,得到[2] 3。左子集排序全部结束
* 以基准为76，对右边的子集进行划分区排序,得到[14, 15, 11] 76
* 此时对上面的[14, 15, 11]以基准为15再进行划分区排序， [14, 11] 15
* 此时对上面的[14, 11]以基准为11再进行划分区排序， 11 [14]
* 所有无序区间都只剩下一个元素，递归结束
*
*/

通过断点调试，可得出结果。

弊端：

它需要Ω(n)的额外存储空间，跟归并排序一样不好。在生产环境中，需要额外的内存空间，影响性能。

同时，很多人认为上边的就是真正的快速排序了。 所以，在下面，很有必要的推荐in-place算法的快速排序

有关于原地算法可参考维基百科，被墙的同学，百度也差不多。

in-place

快速排序一般是用递归实现，最关键是partition分割函数，它将数组划分为两部分，一部分小于pivot，另一部分大于pivot。具体原理上边提过

function quickSort(arr) {
// 交换
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// 分区
function partition(arr, left, right) {
/**
* 开始时不知最终pivot的存放位置，可以先将pivot交换到后面去
* 这里直接定义最右边的元素为基准
*/
var pivot = arr[right];
/**
* 存放小于pivot的元素时，是紧挨着上一元素的，否则空隙里存放的可能是大于pivot的元素，
* 故声明一个storeIndex变量，并初始化为left来依次紧挨着存放小于pivot的元素。
*/
var storeIndex = left;
for (var i = left; i < right; i++) {
if (arr[i] < pivot) {
/**
* 遍历数组，找到小于的pivot的元素，（大于pivot的元素会跳过）
* 将循环i次时得到的元素，通过swap交换放到storeIndex处，
* 并对storeIndex递增1，表示下一个可能要交换的位置
*/
swap(arr, storeIndex, i);
storeIndex++;
}
}
// 最后： 将pivot交换到storeIndex处，基准元素放置到最终正确位置上
swap(arr, right, storeIndex);
return storeIndex;
}
function sort(arr, left, right) {
if (left > right) return;
var storeIndex = partition(arr, left, right);
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
sort(arr, 0, arr.length - 1);
return arr;
}
console.log(quickSort([8, 4, 90, 8, 34, 67, 1, 26, 17]));

分区的优化

这里细心的同学可能会提出，选取不同的基准时，是否会有不同性能表现，答案是肯定的，但，因为，我是搞前端的，对算法不是很了解，所以，这个坑留给厉害的人来填补。

复杂度

快速排序是排序速度最快的算法，它的时间复杂度是O(log n)

在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较.

https://github.com/LYZ0106/

以上所述是小编给大家介绍的JavaScript实现in-place思想的快速排序方法，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的，在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • JavaScript对象数组如何按指定属性和排序方向进行排序

    引子 在以数据为中心的信息系统中,以表格形式展示数据是在常见不过的方式了.对数据进行排序是必不可少的功能.排序可以分为按单个字段排序和按多个字段不同排序方向排序.单字段排序局限性较大,不能满足用户对数据的关注点变化的需求,而多字段排序就可以较好的弥补这个缺陷. 多字段排序,实现的方式从大的层面上可以分为后端实现和前端实现. 后端排序 后端实现排序可以在数据库层面实现或者在应用程序层面实现. 数据库层面实现多字段排序非常简单,使用SQL的排序指令"Order By"即可--Order B

  • JavaScript对象数组排序实例方法浅析

    在javascript中实现多维数组.对象数组排序,基本上都是用原生的sort()方法,用于对数组的元素进行排序. 其基本的用法就不说了,先看个简单的排序例子: //Sort alphabetically and ascending: var myarray=["Bob", "Bully", "Amy"] myarray.sort() //Array now becomes ["Amy", "Bob", &

  • JS实现table表格数据排序功能(可支持动态数据+分页效果)

    asp.net会经常遇到分页的效果,尤其是希望实现静态的html分页排序(html分页相信大家都已经有自己的解决方案.在这里就不多说).我写了一个简单的Demo排序. 数据就是字母和数字两组.(汉字需要找到asc码) 原理就是利用数组自带的sort排序,进行表格重组.已在.net mvc 中测试过.支持分页.(申明一点.只对当前页面数据排序 无刷新,对所有页面排序的话,肯定需要刷新.这点我还在解决中.)希望有新想法的高手们,给下指点. 下面把html的代码贴出来: <!DOCTYPE HTML

  • JS学习之表格的排序简单实例

    JS学习之表格的排序简单实例 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title></title> </head> <body> <input id="btn1" type="button" value="排序"> <table id="

  • 基于JS实现数字+字母+中文的混合排序方法

    基于JS实现数字+字母+中文的混合排序方法

    在上篇文章给大家介绍了JavaScript sort数组排序方法和自我实现排序方法小结,用自己的方法实现了数字数组的排序. 当然,实际运用中,我还是会使用sort方法更加方便.但是,我上一篇博文,仅仅是实现了数字排序,而srot方法默认可是能给字母实现排序的哦!而我的代码只能排序数字,看起来还是弱弱的. 所以,我得加上能排字母甚至中文的排序方法. 实现代码 $(function(){ var arr = ["Jack","Book","Fung"

  • 深入理解js数组的sort排序

    废话少说直接上代码: <body> <div> sort()对数组排序,不开辟新的内存,对原有数组元素进行调换 </div> <div id="showBox"> 1.简单数组简单排序 <script type="text/javascript"> var arrSimple=new Array(1,8,7,6); arrSimple.sort(); document.writeln(arrSimple.j

  • JavaScript sort数组排序方法和自我实现排序方法小结

    JavaScript sort数组排序方法和自我实现排序方法小结

     前言 针对一个数组进行排序,一个很常见的需求.尤其在后端.当然,前端也是有这个需求的. 当然,数组排序,是有现成的方法的.就是sort()方法. 我们先开看下这个. 标准答案,sort方法 var arr = [45,98,67,57,85,6,58,83,48,18]; console.log('原数组'); console.log(arr); console.log('sort方法从小到大排序'); console.log(arr.sort(function(a,b){return a-b

  • 分享javascript实现的冒泡排序代码并优化

    冒泡排序:就是将一个数组中的元素按照从大到小或者从小到大的顺序进行排列. var array=[9,8,7,6,5,4,3,2,1]; 第一轮比较:8,7,6,5,4,3,2,1,9      交换了8次        i=0   j=array.length-1-i 第二轮比较:7,6,5,4,3,2,1,8,9      交换了7次        i=1   j=array.length-1-i 第三轮比较:6,5,4,3,2,1,7,8,9      交换了6次        i=2  

  • JavaScript实现in-place思想的快速排序方法

    快速排序,又称划分交换排序.以分治法为策略实现的快速排序算法. 本文主要要谈的是利用javascript实现in-place思想的快速排序 分治法: 在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式.字面上的解释是"分而治之",就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并.(摘自维基百科) 快速排序的思想 数组中指定一个元素作为标尺,比它大的放到该元素后面,比它小的放到该元素前面,如此重复直至全部

  • JavaScript选择排序算法原理与实现方法示例

    JavaScript选择排序算法原理与实现方法示例

    本文实例讲述了JavaScript选择排序算法原理与实现方法.分享给大家供大家参考,具体如下: 一.选择排序简介 冒泡排序.插入排序.选择排序合称为简单排序.下面是选择排序的思想: 假设有一个数组a,我们想象成有一个班级名叫a班,现在全班随意排成一排,排头的位置是a[0],排尾的位置是a[a.length-1].但高矮顺序不是有序的,我们想从矮到高排,排头最矮,排尾最高. 选择排序是这样工作的: 第一轮: (1)a[1]位置队员与a[0]位置队员比较,如果比a[0]位置队员矮,就把a[1]的位置

  • javascript先序遍历DOM树的方法

    DOM树由文档中的所有节点(元素节点.文本节点.注释节点等)所构成的一个树结构,DOM树的解析和构建是浏览器要实现的关键功能.既然DOM树是一个树结构,那么我们就可以使用遍历树结构的相关方法来对DOM树进行遍历,同时DOM2中的"Traversal"模块又提供了两种新的类型,从而可以很方便地实现DOM树的先序遍历. 注:本文中的5种方法都是对DOM的先序遍历方法(深度优先遍历),并且只关注Element类型. 1. 使用DOM1中的基础接口,递归遍历DOM树 DOM1中为基础类型Nod

  • JavaScript实现图片懒加载的方法分析

    本文实例讲述了JavaScript实现图片懒加载的方法.分享给大家供大家参考,具体如下: 懒加载是非常实用的提升网页性能的方式,当访问一个页面的时候,只显示可视区域内的图片,其它的图片只有出现在可视区域内的时候才会被请求加载. 我们现在用原生的js实现简单的图片懒加载,主要利用的原理就是先不给设置src,而是把图片的路径放在data-src中,等待图片被加载的时候将路径取出放到src中. HTML代码 <div class="container"> <div clas

  • javascript动态添加删除tabs标签的方法

    本文实例讲述了javascript动态添加删除tabs标签的方法.分享给大家供大家参考.具体实现方法如下: <html> <HEAD> <TITLE>网页对话</TITLE> <LINK href="style.css" type=text/css rel=stylesheet> <script> function $(obj) { var o = typeof(obj)=="object" ?

  • javascript正则表达式使用replace()替换手机号的方法

    本文实例讲述了javascript正则表达式使用replace()替换手机号的方法.分享给大家供大家参考. 具体实现方法如下: 复制代码 代码如下: <html> <head> <title>javascript正则表达式使用replace()替换手机号</title> <meta http-equiv="content-type" content="text/html;charset=utf-8" />

  • JavaScript动态提示输入框输入字数的方法

    本文实例讲述了JavaScript动态提示输入框输入字数的方法.分享给大家供大家参考.具体如下: 在QQ空间里有小纸条那么一个功能,随着你在文本框中输入多少字,上面会动态提示你"已经输入多少字"和"还可以输入多少字",觉得挺好的,所以自己也试着做做,呵呵.   开始,我想很多人第一感觉就是通过js的 onkeydown或者onkeyup来做,中发现还可以用focus + setInterval() +blur来达到我们需要的效果,于是很快的我利用这种方法自己粗糙的写

  • Javascript基础_标记文字的实现方法

    Javascript基础_标记文字的实现方法

    Javascript基础_标记文字的实现方法  1.用基本的文字元素标记内容 先看显示效果: 对应HTML代码: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Learn4Font</title> </head> <body> <p> 元素 b -- <b>

  • JavaScript将XML转成JSON的方法

    本文实例讲述了JavaScript将XML转成JSON的方法.分享给大家供大家参考.具体方法如下: 1. JavaScript代码如下: 复制代码 代码如下: // Changes XML to JSON function xmlToJson(xml) {     // Create the return object     var obj = {};     if (xml.nodeType == 1) { // element         // do attributes       

  • JavaScript获取当前日期是星期几的方法

    本文实例讲述了JavaScript获取当前日期是星期几的方法.分享给大家供大家参考.具体如下: JavaScript获得当前日期是星期几,主要通过getDay函数获得当前日期是一个星期的第几天 <!DOCTYPE html> <html> <body> <p id="demo"> Click the button to display todays day of the week. </p> <button onclic

随机推荐