快速排序的Nodejs实现

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。

算法为王的时代正式到来….

关于作者:

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/algorithm-quicksort-nodejs/

quicksort-nodejs

前言

排序算法,是程序开发中最基本的一项任务。教科课上讲的排序算法大概有7-8种,快速排序(QuickSort)是使用最广泛的一种基于比较排序的算法。网上已经有了各种语言的实现。本文则是利用快速排序的原理,实现对数组对象中的属性进行排序,利用Nodejs来实现。

目录

  1. 快速排序介绍
  2. 快速排序算法演示
  3. Nodejs程序实现

1. 快速排序算法介绍

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序的思想很简单,排序过程只需要三步:

  • 1. 从数列中挑出一个元素,称为 “基准”(pivot)
  • 2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

摘自: http://zh.wikipedia.org/wiki/快速排序

2. 快速排序算法演示

举例来说,现在有一组数据[9,23,12,11,43,54,43,2,12,66],怎么对其按从小到大顺序排序呢?

quicksort

  • Step1,选择第一个元素9作为分隔值,把小于9的数字放左边,大于等于9的数字放右边。原来的一个数组就被分成了3个部分,左边+分隔值+右边=[2]+9+[23 12 11 43 54 43 12 66]
  • Step2, 选择Step1数组左边的第一元素2作为分隔值,左边只有一个元素,左边排序完成。选择Step1数组右边的第一个元素23作为分隔值,把小于23的数字放左边,大于等于23的数字放右边,得到[ 12 11 12 ] 23 [ 43 54 43 66 ]。
  • Step3,选择Step2数组以23分隔的左边第一个元素12作为分隔值,把小于12的数字放左边,大于等于12的数字放右边,得到[ 11 ] 12 [ 12 ]。选择Step2数组以23分隔的左边第一个元素43作为分割值,把小于43的数字放左边,大于等于43的数字右边,得到 [] 43 [ 54 43 66 ]。
  • Step4,对Step3数组以12分隔的左右两边进行排序,都只有一个元素,排序完成。对Step3数组以43分隔左右两进行排序,左边无元素,右边第一个元素54作为分隔值,得到[ 43 ] 54 [ 66 ]。
  • Step5,对Step4数组以54分隔的左右两边进行排序,都只有一个元素,排序完成。
  • 最后,后整个数组拼接在一起就得到排序结果:[2 9 11 12 12 23 43 43 54 66 ]

我们看到快速排序,其实就是一种分而治之的办法。网上还有很多快速排序的优化方法,可以尽一步减少时间复杂度和空间复杂度的开销。

3. Nodejs程序实现

像快速排序这种成熟的算法,我以为在Nodejs中早就有人已经封装好了程序包。等我用到的时候竟然找不到,所以自己花了点时间,动手实现了快速排序的Node模块。

当然,除了支持对普通数组的快速排序,还支持按数组对象中的某个属性进行快速排序,已满足自己的功能需求。

3.1 普通数组的快速排序

这部分的实现就和上文中演示的思路是一样的,我另外加了方向的判断。可以从小到大排序,也可以从大到小排序。

现实代码如下:


/**
 * 普通数组快速排序
 *
 * @param arr Array 数字数组
 * @param dir asc升序、desc降序
 *
 * @example:
 * sort([1,4,2,5])
 * sort([1,4,2,5],'asc')
 * sort([1,4,2,5],'desc')
 */
exports.sort=function(arr,dir){
    dir=dir||'asc';
    if (arr.length == 0) return [];

    var left = new Array();
    var right = new Array();
    var pivot = arr[0];

    if(dir==='asc'){//升序
        for (var i = 1; i < arr.length; i++) {
            arr[i] < pivot ? left.push(arr[i]): right.push(arr[i]);
        }
    }else{//降序
        for (var i = 1; i < arr.length; i++) {
            arr[i] > pivot ? left.push(arr[i]): right.push(arr[i]);
        }
    }
    return _this.sort(left,dir).concat(pivot, _this.sort(right,dir));
}

运行程序:


var algo = require('./index.js');
var arr = [23,12,11,43,54,43,2,12,66];
console.log(arr);
console.log(algo.quicksort.sort(arr));
console.log(algo.quicksort.sort(arr,'desc'));

//output
[ 23, 12, 11, 43, 54, 43, 2, 12, 66 ]
[ 2, 11, 12, 12, 23, 43, 43, 54, 66 ]
[ 66, 54, 43, 43, 23, 12, 12, 11, 2 ]

3.2 按数组对象中的属性进行快速排序

按数组对象中的属性快速排序,是指在数组中存储的不是数字类型,而是对象类型,如[{name:’小B’,id:12},{name:’小C’,id:21},{name:’小A’,id:2}],然后想要按对象中的id属性把对象排序。这样需求,其实在程序开发中更常见。那我们怎么做呢?其实,原理是一样的,只要把分隔值(pivot)和存储值(pivotObj)分成2个变量就行了。

实现代码如下:


/**
 * 对象数组快速排序
 *
 * @param arr Array 对象数组
 * @param key string 用于排序的属性
 * @param dir asc升序、desc降序
 *
 * @example:
 * sort([{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}],'id')
 * sort([{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}],'id','asc')
 * sort([{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}],'id','desc')
 */
exports.sortObj=function(arr,key,dir){
    key=key||'id';
    dir=dir||'asc';
    if (arr.length == 0) return [];

    var left = new Array();
    var right = new Array();
    var pivot = arr[0][key];//分割值
    var pivotObj = arr[0];//存储值

    if(dir==='asc'){//升序
        for (var i = 1; i < arr.length; i++) {
            arr[i][key] < pivot ? left.push(arr[i]): right.push(arr[i]);
        }
    }else{//降序
        for (var i = 1; i < arr.length; i++) {
            arr[i][key] > pivot ? left.push(arr[i]): right.push(arr[i]);
        }
    }
    return _this.sortObj(left,key,dir).concat(pivotObj, _this.sortObj(right,key,dir));
}

运行程序:


var algo = require('./index.js');
var arrObj = [{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}];
console.log(arrObj);
console.log(algo.quicksort.sortObj(arrObj,'id','asc'));
console.log(algo.quicksort.sortObj(arrObj,'id','desc'));

//output
[ { name: 'b', id: 12 },{ name: 'c', id: 21 },{ name: 'a', id: 2 } ]
[ { name: 'a', id: 2 },{ name: 'b', id: 12 },{ name: 'c', id: 21 } ]
[ { name: 'c', id: 21 },{ name: 'b', id: 12 },{ name: 'a', id: 2 } ]

不用多少代码,就能实现快速排序。程序源代码已上传到github, https://github.com/bsspirit/ape-algorithm。下载后,可以参考example.js文件中,来调用快速排序程序。

同时也在npm发布了,安装命令:

npm install ape-algorithm

有时候写写算法,感觉又回到了学生时代,还是挺有意思的。

转载请注明出处:
http://blog.fens.me/algorithm-quicksort-nodejs/

打赏作者

This entry was posted in Javascript语言实践, 程序算法

  • kazaff

    例子里倒数第二个数应该是12,你写成1了,对吧?

    • 没找到你说的问题?在哪里?

      • kazaff

        2.快速排序算法演示中的第一张图的“原始数据”一行中的倒数第二个元素,不得不佩服我的眼尖吧~~哇哈哈哈

  • Dc Zhu

    就是二叉树排序吧

  • nicholas_xue

    快速排序本来是在原来的array上操作的,像你这样每次递归时,会创建好多new array,如果数据比较大时,内存会不会爆掉啊?

    • 你说的对,我已经发现这个问题了。

      FATAL ERROR: JS Allocation failed – process out of memory

  • wuwei

    用js写排序?太作了

    • 如果数据已经加载到网页了,需要排序,你会怎么办?

      • Shaun

        underscore: _.sort

        • _.sort,不能实现对象的任意属性排序。

    • binyoyo

      我以前也认为是这样,但是前段时间去腾讯面试的时候,就是要我用js写快排,我都蒙了,现在只好乖乖的去学会,不然我自己吃亏。

      • 编程语言只是工具,算法才是体现核心价值的精髓。

      • Qiuleo

        人家本身考的就不是语言,如果一门语言搞得久了,又怎么不会这些简单的算法?

  • 这。。

    难道V8的array的sort本身不是用的quicksort?,难道原生的sort不能支持任意对象的属性排序?

    • 这。。

      var arrObj = [{name:’b’,id:12},{name:’c’,id:21},{name:’a’,id:2}];
      arrObj.sort(function(a, b){return a.id – b.id});
      arrObj.sort(function(a, b){return b.id – a.id});

      • 这。。

        http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/

        “Quicksort is generally considered to be efficient and fast and so is used by V8 as the implementation for Array.prototype.sort() on arrays with more than 23 items. For less than 23 items, V8 uses insertion sort[2]”

        • 很详细,多谢指教!

          1. 这个包主要是自己用,快速排序只是其中一种基于比较的排序算法。

          2. V8的Array.prototype.sort()肯定比我简单实现的算法效率高,但很多的时候,还需要针对业务要扩展算法。比如 按多个变量排序之类的需求, id asc, id2 desc, id3 asc 。

  • Pingback: Nodejs学习路线图 | 粉丝日志()