我用了蒂莫西·拉夫花园的隔板,他选择了第一个元素,但并没有完全按照我想要的方式工作。
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
function partition(arr, left, right) {
left = left || 0;
right = right || arr.length - 1;
var pivot = arr[0];
var i = left + 1;
for (var j = left + 1; j < right; j++) {
if (arr[j] < pivot) {
swap(arr, j, i); //need to swap with left most array entry which is currently bigger than pivot
i++;
}
}
//swap pivot with right most element smaller than the pivot (i-1)
swap(arr, left, i-1)
// console.log(arr);
// return i;
return i - 1;
}
function quickSort(arr, start, end) {
start = start || 0;
end = end || arr.length - 1;
var pivotNewIndex = partition(arr, start, end);
if (start < end) {
quickSort(arr, start, pivotNewIndex - 1);
quickSort(arr, pivotNewIndex + 1, end);
}
return arr;
}
var arr4 = [3, 8, 2, 1, 5];
console.log(quickSort(arr4)); --- > [ 1, 2, 3, 8, 5 ];
我在这里做错什么了?我想结局是从最初的结局被重新分配的,我该如何阻止
最佳答案
在此处选择整个数组的第一个元素作为工作范围的轴:var pivot = arr[0];
但必须使用当前段的第一个元素var pivot = arr[left];
检查并调试分区周期必须有两个指针,一个从段的左端开始,另一个从段的右端开始。但我看到两个人都是从左向右走的(对JS的了解不足以纠正这个问题)
关于javascript - 在javascript中实现quickSort时遇到麻烦,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/33460003/