前言
排序算法，是程序开发中最基本的一项任务。教科课上讲的排序算法大概有7-8种，快速排序(QuickSort)是使用最广泛的一种基于比较排序的算法。网上已经有了各种语言的实现。本文则是利用快速排序的原理，实现对数组对象中的属性进行排序，利用Nodejs来实现。
目录
- 快速排序介绍
- 快速排序算法演示
- 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有时候写写算法，感觉又回到了学生时代，还是挺有意思的。
作者介绍：
张丹，R语言中文社区专栏特邀作者，《R的极客理想》系列图书作者，民生银行大数据中心数据分析师，前况客创始人兼CTO。
10年IT编程背景，精通R ,Java, Nodejs 编程，获得10项SUN及IBM技术认证。丰富的互联网应用开发架构经验，金融大数据专家。个人博客 http://fens.me， Alexa全球排名70k。
著有《R的极客理想-工具篇》、《R的极客理想-高级开发篇》，合著《数据实践之美》，新书《R的极客理想-量化投资篇》(即将出版)。
《R的极客理想-工具篇》京东购买快速通道：https://item.jd.com/11524750.html
《R的极客理想-高级开发篇》京东购买快速通道：https://item.jd.com/11731967.html
《数据实践之美》京东购买快速通道：https://item.jd.com/12106224.html
