Array.prototype.quickSort = async function quickSort(fn) {
let arr = this;
let len = arr.length;
_quickSort(arr, 0, len - 1);
function _quickSort(arr, left, right) {
if (left >= right) return;
let j = partition(arr, left, right);
_quickSort(arr, left, j - 1);
_quickSort(arr, j + 1, right);
}
function partition(arr, left, right) {
let v = arr[left];
let j = left;
for (let i = left + 1; i <= right; i++) {
if (fn(v, arr[i]) > 0) {
swap(arr, i, j + 1);
j++;
}
}
swap(arr, left, j); // 把 v 放到正确的位置上
return j;
}
};
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
双路快排
三路快排