排序算法(六)--快速排序

快速排序的思想：先在整个数列中找到一个基准（pivot），以这个基准为参照，重新排列整个数列，将其中的项目小于基准的排在基准的一边，将大于基准的排在基准的另一侧。等于基准排在哪边无所谓。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

quickSort (arr, l, r) {
    //  一个元素不需要排序，直接返回
    if (l >= r) return arr
    //  找到基准的下标
    let partitionIndex = partition(arr, l, r)
    //  对基准左侧的数组排序,同时基准向左移动
    quickSort(arr, l, partitionIndex - 1)
    //  对基准右侧的数组排序,同时基准向右移动
    quickSort(arr, partitionIndex + 1, r)
}
partition (arr, l, r) {
    //  取每段数组的最右边的元素为基准值
    let pivot = arr[r]
    let left = l
    let right = r - 1
    while (left < right) {
        while (left <= right && arr[left] <= pivot) {
            left++
        }
        while (left <= right && arr[right] > pivot) {
            right--
        }
        if (left < right) {
            this.swap(arr, left, right)
        }
    }
    //  最后剩下的元素做交换
    swap(arr, left, r)
    //  这里返回的是left,不是right
    return left
}
swap (arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
},
let arr = [7,9,4,2,6,1,5,2,3,8]
quickSort(arr, 0, arr.length - 1)
console.log(arr)
//  [1,2,3,4,5,6,7,8,9]

注：快速排序稳定，且效率高，所以使用也比较多。