Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
quick sort
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
function partition(items, left, right) {
var index = Math.floor((right + left) / 2),
pivot = items[index],
i = left,
j = right;
while (i < j) { // i <= j to i < j
while (items[i] < pivot) {
i++;
}
while (items[j] > pivot) {
j--;
}
if (i < j) { // i <=j to i < j
swap(items, i, j);
if (i === index) { // update pivot pointer
index = j;
} else if (j === index) {
index = i;
}
i++;
j--;
}
}
return index; // return i to return index
}
function quickSort(items, left, right) {
var index;
if (items.length > 1) {
index = partition(items, left, right);
if (left < index - 1) {
quickSort(items, left, index - 1);
}
if (index + 1 < right) { // index < right to index + 1 < right
quickSort(items, index + 1, right); // index to index + 1
}
}
return items;
}
console.log(quickSort([1, 2, 3, 4, 5], 0, 4));
console.log(quickSort([5, 4, 3, 2, 1], 0, 4));
console.log(quickSort([2, 2, 2, 2, 2], 0, 4));
console.log(quickSort([2, 3, 1], 0, 2));
console.log(quickSort([2, 1, 3], 0, 2));
@zoubin

你的 index 返回 pivot 的位置,而 Zakas 的返回 pivot 的下一个位置。所以,我能看出来的,此处的 quickSort 和 Zakas 写的唯一的差别就是,前者不会将 pivot 列入下一次的递归中,而后者做了这部分没必要的工作。不过你们都做了一部分没必要的工作,就是 swap 中多了一次赋值。在快排中有种方法可以避免交换,节省循环中的一次赋值……

@trevnorris

Haven't been able to determine why yet, but your quick sort is failing in the following:

var arr = [ 0.13837, 0.70843, 0.63302, 0.00802, 0.00141 ];

console.log(quickSort(arr, 0, 4));

// output: [ 0.00141, 0.13837, 0.00802, 0.63302, 0.70843 ]
@springuper
Owner

@trevnorris thanks for the test case, there does exist a problem with the return value of function partition. Pointer i maybe not the right pointer to pivot when an exchange occurs between the pivot and some other item.

I have update the code to fix it, please try. Thank you so much.

@JacksonGL

Your code still has a bug, you can easily find it if you do random testing

quickSort(items, left, index-1); // here should be quickSort(items, left, index);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.