快速排序函数中的调用堆栈超过

Question

我正在为学校做一个练习，试图写我的第一个快速排序。它对一个随机整数数组进行排序。当我叫它时，我得到一个"；调用堆栈超出"；错误有人能指出我的错误吗？

const quickSort = (unsorted) => {
//let median = Math.floor(Math.random() * unsorted.length -1);
let median = Math.floor(unsorted.length -1 /2);
let greater = [];
let lesser = [];
let sorted = [];

if(unsorted.length < 2) {
return unsorted;
}
for (let i = 0; i < unsorted.length; i++) {
const element = unsorted[i];
const pivot = unsorted[median]
if (element > pivot) {
greater.push(element)
} else {
lesser.push(element);
}
}

let sortedLesser = quickSort(lesser);
let sortedGreater = quickSort(greater);
sorted = [...sortedLesser, ...sortedGreater];
return sorted;
}

Answer 1

QuickSort的一个想法是从递归调用中排除pivot元素。通过这种方式，您可以绝对确定递归调用总是会得到一个较小的数组，即使轴心位于原始数组的极端。

正如注释中所指出的，您除以2只适用于1(因为除法优先于减法(，这意味着您的数据透视索引始终是数组中的最后一个索引。由于您没有将该索引从递归调用中排除，因此您得到了一个永远不会缩短数组的递归树。

我建议进行以下更改：

const quickSort = (unsorted) => {
let median = unsorted.length >> 1; // 1 bit shift is integer division by 2
let greater = [];
let lesser = [];
if (unsorted.length < 2) {
return unsorted;
}
const pivot = unsorted[median]; // Do this once only
for (let i = 0; i < unsorted.length; i++) {
if (i === median) continue; // exclude the pivot itself
const element = unsorted[i];
if (element > pivot) {
greater.push(element)
} else {
lesser.push(element);
}
}
let sortedLesser = quickSort(lesser);
let sortedGreater = quickSort(greater);
// Include the pivot here
sorted = [...sortedLesser, pivot, ...sortedGreater];
return sorted;
}

尽管这纠正了问题，但请注意，快速排序的目的不是创建额外的数组，而是将原始数组重新排序。