步骤为：
- 从数列中挑出一个元素，称为 "基准"（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
快速排序算法的基本特性：
时间复杂度：O（n*lgn）
最坏：O（n^2）
空间复杂度：O（n*lgn）
不稳定。
测试结果：
数组里有10000个随机数, 执行500次后花费的毫秒数
最大毫秒数为28
最小毫秒数为9
平均毫秒数为13
示例代码：
<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>快速排序算法</title>
</head>
<body>
<script>
var count = 10000,
num = testCount = 500,
i,
exeCount,
exeTimeArr = [],
quickSort = function(a){
if(a.length <= 1) return a;
var middle = a.pop(),
before = [],
after = [];
a.forEach(function(d){
d < middle ?
before.push(d) :
after.push(d);
});
before = quickSort(before);
after = quickSort(after);
return before.concat(middle, after);
};
var body = document.getElementsByTagName('body')[0];
var log = function(s){
var p = document.createElement('p');
var ps = document.getElementsByTagName('p');
p.innerHTML = s;
ps.length ?
body.insertBefore(p, ps[0]) :
body.appendChild(p);
//document.write(s + '<br />'); 破坏文档结构
//firefox下使用console.log并开启firebug会影响执行
}
function exeTest( callback ){
function test(){
var cost,
startTime,
arr = [];
testCount--;
// 构建随机数组
for(i=0;i<count;i++){
arr.push( Math.round(Math.random() * count) ); // 0 - count
}
startTime = + new Date();
arr = quickSort(arr);
exeTimeArr.push(cost = new Date() - startTime); //花费的毫秒数
log('本次测试花费 '+ cost +' 毫秒, 还剩 '+ testCount +' 次测试');
if(testCount == 0 && typeof callback == 'function'){
callback();
}else{
// 预防浏览器挂起
setTimeout(test, 0);
}
}
test();
}
function callback(){
var sum = 0;
var result = '数组里有'+ count +'个随机数, 执行'+ num +'次后花费的毫秒数' + '<br />' +
'最大毫秒数为' + Math.max.apply(null, exeTimeArr) + '<br />' +
'最小毫秒数为' + Math.min.apply(null, exeTimeArr) + '<br />';
exeTimeArr.forEach(function(value) {
sum += value;
})
result += '平均毫秒数为' + Math.round( sum / num ) ;
log(result);
}
// 执行100次测试完成时间
exeTest(callback);
</script>
</body>
</html>
