编辑代码

/* 随机区间[min, max] */
function rand(min: number, max: number): number {
    return Math.trunc(Math.random() * (max - min + 1) + min);
}

/* 交换两数 */
function swap(arr: number[], x: number, y: number) {
    let temp: number = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

/**
 * @brief 快速排序
 * @param arr
 * @param left
 * @param right
 * @returns
 */
function quickSort(arr: number[], left: number, right: number) {
    if (left >= right) return;
    swap(arr, left, rand(left, right));
    let privot: number = arr[left];
    let mark: number = left;
    for (let i: number = left + 1; i <= right; i++) {
        if (arr[i] < privot) {
            mark++;
            swap(arr, mark, i);
        }
    }
    swap(arr, mark, left);
    quickSort(arr, left, mark - 1);
    quickSort(arr, mark + 1, right);
}

const arr: number[] = [4, 5, 1, 3, 2, 8, 6, 7];
const left: number = 0;
const right: number = arr.length - 1;
console.log('排序前:\n');
console.log(arr);
quickSort(arr, left, right);
console.log('排序后:\n');
console.log(arr);