一、题目
题目：手写一个快速排序
例子：
输入：[1, 34, 5, 76, 8, 6, 9, 7, 6, 3]
输出：[1, 3, 5, 6, 6, 7, 8, 9, 34, 76]
二、代码实现
“快速排序”思路：
- 在数组中，选择一个元素作为“基准”；
- 所有小于“基准”的元素，都移到“基准”左边；所有大于“基准”元素，都移到“基准“的右边；
- 对应“基准”左边和右边的两个子集，不断重复第一步和第二步，知道所有的子集只剩下一个元素为止；
代码实现：
let testArr = [1, 34, 5, 76, 8, 6, 9, 7, 6, 3];
var quickSort = function (arr) {
// 检查数组的元素个数，如果小于等于1，就返回。
if (arr.length <= 1) {
return arr;
}
// 选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。
const pivotIndex = Math.floor(arr.length / 2); //Math.floor向下取整 45.11 => 45
const pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
const len = arr.length;
// 开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集。
for (let i = 0; i < len; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 使用递归不断重复这个过程，就可以得到排序后的数组
return quickSort(left).concat([pivot], quickSort(right));
};
var result = quickSort(testArr);
console.log(result);// [1, 3, 5, 6, 6, 7, 8, 9, 34, 76]
