以下为ChatGPT自动生成的解答,正确与否请自行判断。
BFE.devAI解答 - JavaScript 代码题
43. 手写 Quick Sort
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
时间复杂度为O(nlogn),空间复杂度为O(logn)。Quick Sort不是稳定的排序,因为在交换元素时可能改变了两个相等元素之间的顺序。