quick sort

quicksort.js

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));

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

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 ]

@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.

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);