javascript - 这个快速排序逻辑正确吗?
问题描述
我试图在 Javascript 中实现快速排序,而不参考伪代码。这是正确的实现吗?如果不是,我该如何改进它。
const quickSort = (arr = []) => {
const length = arr.length;
if (length === 0 || length === 1) {
return arr;
}
const pivot = arr[0];
const leftArray = [];
const rightArray = [];
for (let i = 1; i < length; i++) {
if (arr[i] < pivot) {
leftArray.push(arr[i]);
} else {
rightArray.push(arr[i]);
}
}
return [...quickSort(leftArray), pivot, ...quickSort(rightArray)];
};
console.log(quickSort([2, 45, 6, 7, 8, 1]));
我已经添加了测试用例的代码并执行了超过 250000 次。
// Function to generate random array.
const generateRandomArray = n =>
Array.from({
length: n
}, () => Math.floor(Math.random() * n));
// Function to check whether array is sorted.
const checkSorted = (arr = []) => {
let sorted = true;
for (let i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
sorted = false;
break;
}
}
return sorted;
};
// Testing Quick-Sort
const testQuickSort = () => {
for (let i = 1; true; i++) {
const sortedArray = quickSort(generateRandomArray(Date.now() % 100000));
const isSorted = checkSorted(sortedArray);
if (!isSorted) {
console.log("error");
break;
}
console.log("pass", i);
}
};
testQuickSort();
解决方案
您可以尝试以下解决方案
function pivot(arr, start = 0, end = arr.length - 1) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// We are assuming the pivot is always the first element
let pivot = arr[start];
let swapIdx = start;
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIdx++;
swap(arr, swapIdx, i);
}
}
// Swap the pivot from the start the swapPoint
swap(arr, start, swapIdx);
return swapIdx;
}
function quickSort(arr, left = 0, right = arr.length -1){
if(left < right){
let pivotIndex = pivot(arr, left, right) //3
//left
quickSort(arr,left,pivotIndex-1);
//right
quickSort(arr,pivotIndex+1,right);
}
return arr;
}
console.log(quickSort([100,-3,2,4,6,9,1,2,5,3,23]));
推荐阅读
- python - 只要按住拍摄按钮,如何继续拍摄
- node.js - 写入 cookie 时发送后无法设置标头
- unit-testing - 如何在 Salesforce 中执行“lastmodified”日期的测试类覆盖?
- php - 如何获取当前页面菜单项祖先名称wordpress
- xcode - 在 Xcode 中向 UITest Target 添加 aps-environment 权利
- vb.net - VB.NET - 如何添加我的扩展
- java - BPXWUNIX:尝试运行 Regina Rexx 脚本时未发现错误
- html - 在另一个 HTML 文件中包含一个 HTML 文件
- python - 来自圆柱坐标的 Numpy 掩码
- c++ - 作为模板参数c ++给出的类的别名模板