排序算法（Sorting algorithm）是计算机科学最古老、最基本的课题之一。要想成为合格的程序员，就必须理解和掌握各种排序算法。
目前，最常见的排序算法大概有七八种，其中"快速排序"（Quicksort）使用得最广泛，速度也较快。它是图灵奖得主C. A. R. Hoare（1934--）于1960时提出来的。
"快速排序"的思想很简单，整个排序过程只需要三步：
（1）在数据集之中，选择一个元素作为"基准"（pivot）。
（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
代码实现：
阮一峰版（个人比较喜欢这个版本，比较好理解，用中间值作为flag）：
var quickSort = function(arr) {
// 检查数组的元素个数，如果小于等于1，就返回
if (arr.length <= 1) { return arr; }
// 选择"基准"（pivot）,这里选择的是中间的值
//（基准值可以任意选择，但是选择中间的值比较容易理解。）
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
// 定义两个空数组，用来存放一左一右的两个子集。
var left = [];
var right = [];
// 开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 使用递归不断重复这个过程，就可以得到排序后的数组
return quickSort(left).concat([pivot], quickSort(right));
};
quickSort([2, 5, 3, 1, 4]) // 调用实例
其他实现版本（来自百度百科）：
const quickSort = (array) = >{
const sort = (arr, left = 0, right = arr.length - 1) = >{
if (left >= right) { //如果左边的索引大于等于右边的索引说明整理完毕
return
}
let i = left
let j = right
const baseVal = arr[j] // 取无序数组最后一个数为基准值
while (i < j) { //把所有比基准值小的数放在左边大的数放在右边
while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
i++
}
arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
j--
}
arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
}
arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
}
const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
sort(newArr) return newArr
}
quickSort([2, 5, 3, 1, 4]) // 调用实例
时间复杂度
无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言，最坏情况和最好情况都是相同的。
最优：O(nlogn)（如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了）
最差：O(n^2)（最坏情况运行时间与插入排序是一样的）
平均：O(nlogn)
优化
1.如果有很多相同元素： 对于这种情况的一种改进办法就是将分区分为三块而不是原来的两块：一块是小于中轴值的所有元素，一块是等于中轴值的所有元素，另一块是大于中轴值的所有元素。另一种简单的改进方法是，当分区完成后，如果发现最左和最右两个元素值相等的话就避免递归调用而采用其他的排序算法来完成。
2.分区小的时候快速排序的效率不够： 当分区的规模达到一定小时，便停止快速排序算法，改用插入排序。因为插入排序对于这种“几乎”完成的排序数列有着接近线性的复杂度。这一改进被证明比持续使用快速排序算法要有效的多。
3.大分区带来的空间消耗 在递归排序子分区的时候，总是选择优先排序那个最小的分区。这个选择能够更加有效的利用存储空间从而从整体上加速算法的执行。
4.分区的这一步骤总是要在子序列并行处理之前完成，这就限制了整个算法的并行程度 改进后的并行快速排序算法使用2n个指针来并行处理分区这一步骤，从而增加算法的并行程度。
参考文档：
