Blog Archives

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

前言

排序算法，是程序开发中最基本的一项任务。教科课上讲的排序算法大概有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]，怎么对其按从小到大顺序排序呢？

• 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/