JavaScript中快速排序

quick-sort.md

最近前端圈闹的沸沸扬扬的快排算法，由于对算法不熟悉，先借鉴高程作者的方案在这里。

function swap(items, firstIndex, secondIndex) {
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

function partition(items, left, right) {
    var pivot = items[Math.floor((left + right) / 2)];
    var i = left;
    var j = right;

    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        left = typeof left != "number" ? 0 : left;
        right = typeof right != "number" ? items.length - 1 : right;

        index = partition(items, left, right);

        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }

        if (index < right) {
            quickSort(items, index, right);
        }
    }
    return items;
}
console.time('quick sort');
quickSort([5, 2, 20, 1, 34, 65, 7, 10]);
console.timeEnd('quick sort');

JavaScript中的计算机科学：Quicksort