希望获得有关 Javascript 中的快速排序算法的一些帮助(它不是为了家庭作业或任何东西,只是为了好玩) - 它不起作用,我不确定我哪里出错了。
function quicksort ( arr ) {
// Launch the sorting process.
sort(arr, 0, arr.length - 1 );
/**
* swap
* takes in an array and two indexes,
* swaps the elements in the array at those indexes
*/
function swap ( arr, a, b ) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition ( arr, l, r) {
var p = arr[r],
i = l - 1,
j = l;
while ( j < r - 1) {
if (arr[j] <= p) {
swap ( arr, ++i, j );
}
j++;
}
swap (arr, i + 1, r);
return i + 1;
}
function sort ( arr, l, r ) {
var p;
if (l < r) {
p = partition( arr, l, r );
sort( arr, l, p - 1);
sort( arr, p + 1, r);
} else {
console.log(arr);
}
}
}
最佳答案
好的,我想我找到了。问题就在我的分区循环中,我太早结束了它。完整代码如下:
function quicksort ( arr ) {
// Launch the sorting process.
sort(arr, 0, arr.length - 1 );
/**
* swap
* takes in an array and two indicies,
* swaps the elements in the array at those indicies
*/
function swap ( arr, a, b ) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition ( arr, l, r) {
var p = arr[r],
i = l - 1,
j = l;
while ( j < r) {
if (arr[j] <= p) {
swap ( arr, ++i, j );
}
j++;
}
// Put the pivot in its correct place
swap (arr, i + 1, r);
return i + 1;
}
function sort ( arr, l, r ) {
var p;
if (l < r) {
p = partition( arr, l, r );
sort( arr, l, p - 1);
sort( arr, p + 1, r);
} else if (l === arr.length) {
// Output the sorted array.
console.log(arr);
}
}
}
基本测试:
快速排序( [19,12,1,2,3,123,23,2,5] ) [ 1, 2, 2, 3, 5, 12, 19, 23, 123 ]
快速排序( [8,3,2,1,5,1,3] ) [ 1, 1, 2, 3, 3, 5, 8]
接受有关如何改进的建议! :)
关于javascript - Javascript 中的快速排序 Bug,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26164490/