快速排序的主要思想：
- 选择pivot，将数组分为大于和小于pivot两个部分
- 遍历其他元素，小于的放在left数组，大于的放在right数组
- 递归对left、right应用快排，最后再把left、pivot、right依次连接起来
我们可以对其进行简单优化，那就是确保pivot的随机性，避免最坏情况的发生。例如：数组已经部分有序，若按常规一样选择数组第一个元素作为pivot，则会导致分区不平衡，算法时间复杂度退化到O(n^2)
选取随机索引：Math.random()生成[0, 1)的随机浮点数，乘以length则是在[0, length)这个范围，Math.floor将结果向下取整，最终得到整数。
初步代码如下：
function quickSort (arr) {
if (arr.length <= 1) {
return arr
}
const pivot = arr[Math.floor(Math.random() * arr.length)]
const left = []
const right = []
for (let 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))
}
// Test
const arr = [1, 3, 7, 8, 4, 2, 6, 7]
console.log(quickSort(arr))
运行结果报错：RangeError: Maximum call stack size exceeded
原因是：出现了无限递归，导致超出了调用栈的最大限制。
查看元素可知，数组是存在重复元素7的，如果pivot选择的正好是7，我们也没对重复元素进行处理
那就会在每次递归过程中pivot周围的重复元素就会被分到不同的子数组中，从而导致递归无法收敛。
我们在递归的过程中遇到与pivot相等的元素时，将这些元素分到pivot的左右两侧，确保的就是在下一次递归时，这些相等元素不会再次被选择为pivot，从而避免了递归无法收敛的情况。
因此，在处理pivot周围相同元素时，我们可以选择将pivot本身跳过，确保它不会被重复选择作为基准值，从而避免出现无限递归的问题。
代码如下：
function quickSort (arr) {
if (arr.length <= 1) {
return arr
}
const pivot = arr[Math.floor(Math.random() * arr.length)]
const left = []
const right = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] === pivot) {
continue
}
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(pivot, quickSort(right))
}
// Test
const arr = [1, 3, 7, 8, 4, 2, 6, 7]
console.log(quickSort(arr))
运行结果：[1，2，3，4，6，7，8]
打印出来元素只有7个，发现重复的元素7只剩下一个了。这是怎么回事呢？原来错在用arr[i] === pivot来做的跳过判断。
- 在处理pivot周围相同的元素时，会跳过所有与pivot值相同的元素，包括pivot本身，因此在输出重复元素时会被过滤掉，只留下一个。
我们应该根据下标来做跳过判断：i === index
- 用下标来判断，在处理pivot周围相同元素时，会确保pivot本身只被处理一次
- 因为只有在
i === index才会被跳过输出，而其他重复元素因为与pivot值相同，就会被保留下来 - 所以用index来判断pivot的位置，那么输出时重复的元素就会保留下来，pivot本身只会被输出一次
最终代码如下：
function quickSort (arr) {
if (arr.length <= 1) {
return arr
}
const index = Math.floor(Math.random() * arr.length)
const pivot = arr[index]
const left = []
const right = []
for (let i = 0; i < arr.length; i++) {
if (i === index) {
continue
}
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(pivot, quickSort(right))
}
// Test
const arr = [1, 3, 7, 8, 4, 2, 6, 7]
console.log(quickSort(arr))
输出结果：[1，2，3，4，6，7，7，8]
