快速排序
简单实现：
注：快排的时间复杂度为O(nlgn)~O(n^2) ,由于使用递归调用栈空间复杂度为O(lgn),快排中相等数值排序之后前后位置可能发生变化，因此为非稳定排序。123456789101112131415161718function quicksort(arr) { if (arr.length <= 1) { return arr; } else { var key = Math.floor(arr.length / 2), left = [], right = []; var key = arr.splice(key, 1)[0]; for (var i = 0; i < arr.length; i++) { if (arr[i] < key) { left.push(arr[i]); } else { right.push(arr[i]); } } return quicksort(left).concat([key], quicksort(right)); }}
小结：
它是图灵奖得主C. A. R. Hoare（1934–）于1960时提出来的。
排序的思路分为三步：
- 选择基准值；
- 遍历整个数组，小于基准值的数放在基准左边，否则放在基准右边；
- 左右两边的子集进一步分别进行以上两步，直到所有子集数组中只有一个数字为止。
上例中为方便起见选取了数据的中间值为基准，下图为网上下载图片，可见到基准值从左到右依次选择，个人还是觉得选择中间值更具有普遍意义，更易理解。
图解：
