快速排序 Quicksort

与归并排序类似, 快速排序也是分治算法 的经典实践.

选择基准值 pivot 的方法有多种, 比如:

  • 总是选择第一个元素
  • 总是选择最后一个元素
  • 从数组中随机选择一个元素
  • 选择数组中的中值 median

快速排序的步骤

快速排序的关键在于基准值 pivot 的选择.

  1. 我们选取数组的最后一个元素作为基准值 pivot, 分隔数组为左右两部分
    1. 使用变量 i 标记当前比基准值大的元素位置
    2. 遍历数组, 把比基准值小的元素交换到 i 的左侧, 比基准值大的元素留在元素 i 的右侧
    3. 最后, 把元素 i 与数组最右侧的基准值元素交换位置, 这样就把基准值放在了它的最终位置
  2. 将数组分成两部分, 左侧部分的元素值都比基准值小, 右侧部分比基准值大
  3. 然后递归调用快速排序算法, 对左右两侧子数组进行排序

下面以 arr = [1, 8, 3, 9, 4]; 为例子展示如何对数组分区.

首先选择最后一个元素 4 作为基准值 pivot. 将第一个元素 1 与基准值比较, 它比基准值小, 就需要交换元素 swap(i, j), 并将索引 i 右移一位:

quicksort partition pass1

将第二个元素 8 与基准值比较, 它比基准值大, 就什么都不做:

quicksort partition pass2

将第三个元素 3 与基准值比较, 它比基准值小, 就需要交换元素 swap(i, j), 并将索引 i 右移一位:

quicksort partition pass3

将第四个元素 9 与基准值比较, 它比基准值大, 就什么都不做:

quicksort partition pass4

最后一步, 将基准值 pivot 元素与当前的元素 i 进行交换, 这样的话 pivot 就被移动到了它的最终位置:

quicksort partition pass5

快速排序的实现

默认使用最后一个元素作为基准值 pivot. 如果是已排序好的数组, 这种算法是最差情况, 时间复杂度是 O(n^2).

#![allow(unused)]
fn main() {
/// 使用最后一个元素作为基准值 pivot
///
/// 如果是已排序好的数组, 这种算法是最差情况
#[inline]
pub fn quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    tail_quicksort_helper(arr, 0, arr.len() - 1);
}

fn tail_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_pivot_at_right(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        tail_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        tail_quicksort_helper(arr, pivot_index + 1, high);
    }
}

// 选择最右侧的元素作为基准值
fn partition_pivot_at_right<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = high;

    // 以 pivot 为基准, 把数组划分成三部分: 小于 pivot, pivot, 大于等于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = low;
    // j 用于遍历整个数组
    for j in low..high {
        if arr[j] < arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于 pivot, pivot, 大于等于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}
}

快速排序的特点

  • 最好情况的时间复杂度是 O(n log(n)), 平均情况下的时间复杂度是 O(n log(n))
  • 最差情况的时间复杂度是 O(n^2), 因为选择的基准值 pivot 很不合适
  • 如果不考虑递归调用的栈空间, 快速排序的空间复要度是 O(1)
  • 如果考虑递归调用的栈空间, 最好情况下的空间复杂度是 O(log(n)), 最差情况下的空间复杂度是 O(n)
  • 不是稳定排序 (stable sort). 如果所需的排序算法不要求是稳定排序的, 那么我们应该优先考虑快速排序及其变体
  • 是原地排序 (in-place sort), 不需要辅助数组
  • 比归并排序 (merge sort) 要快, 不需要一个额外的数组来保存中间值
  • 它适对对大数据集做排序, 效率高; 不适合排序小的数据集
  • 快速排序是缓存友好型的 (cache-friendly), 能充分发挥缓存的局部性优势, 因为它是顺序遍历数组的

使用第一个元素作为基准值

上面我实现的分区算法, 使用最后一个元素作为基准值 pivot. 我们也可以选取数组的第一个元素作为基准值, 但如果数组已经是逆序排序的, 这种算法是最差情况, 时间复杂度是 O(n^2).

算法实现如下:

#![allow(unused)]
fn main() {
/// 总是选择第一个元素作为基准值
///
/// 果数组已经是逆序排序的, 这种算法是最差情况, 时间复杂度是 `O(n^2)`
#[inline]
pub fn head_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    head_quicksort_helper(arr, 0, arr.len() - 1);
}

fn head_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_pivot_at_left(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        head_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        head_quicksort_helper(arr, pivot_index + 1, high);
    }
}

/// 选择最左侧的元素作为基准值
fn partition_pivot_at_left<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = low;

    // 以 pivot 为基准, 把数组划分成三部分: 小于等于 pivot, pivot, 大于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = high;
    // j 用于遍历整个数组
    for j in ((low + 1)..=high).rev() {
        if arr[j] > arr[pivot_index] {
            arr.swap(i, j);
            i -= 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于等于 pivot, pivot, 大于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}
}

双指针风格的分区算法

上面的代码中, 我们都使用变量 j 来遍历数组, 这里我们也可以使用靠拢型双指针的写法遍历数组.

#![allow(unused)]
fn main() {
/// 总是选择第一个元素作为基准值, 并使用双指针法进行数组分区.
#[inline]
pub fn two_pointer_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    two_pointer_quicksort_helper(arr, 0, arr.len() - 1);
}

fn two_pointer_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_with_two_pointers(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        two_pointer_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        two_pointer_quicksort_helper(arr, pivot_index + 1, high);
    }
}

/// 使用双指针法选择最左侧的元素作为基准值
fn partition_with_two_pointers<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = low;

    // 使用双指针法遍历数组, 以 pivot 为基准, 把数组划分成三部分:
    // 小于等于 pivot, pivot, 大于 pivot
    let mut left: usize = low;
    let mut right: usize = high;
    while left < right {
        // right 的位置左移, 直到 arr[right] 小于等于 pivot
        while left < right && arr[right] > arr[pivot_index] {
            right -= 1;
        }

        // left 的位置右移, 直到 arr[left] 大于 pivot
        while left < right && arr[left] <= arr[pivot_index] {
            left += 1;
        }

        // 交换元素
        arr.swap(left, right);
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于等于 pivot, pivot, 大于 pivot
    arr.swap(left, pivot_index);
    // 返回的是 pivot 所在的位置
    left
}
}

当元素较少时, 使用插入排序

当元素较少时, 递归调用快速排序算法会产生非常多的调用分支, 效率很低. 跟之前的优化方法类似, 当元素个数较少时, 我们直接调用插入排序.

#![allow(unused)]
fn main() {
/// 如果元素较少, 就使用插入排序
#[inline]
pub fn insertion_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    insertion_quicksort_helper(arr, 0, arr.len() - 1);
}

fn insertion_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    const CUTOFF: usize = 24;

    if low >= high {
        return;
    }

    // 数组中的元数个数低于一个阈值时, 使用插入排序
    if high - low + 1 < CUTOFF {
        insertion_sort(&mut arr[low..=high]);
        return;
    }

    // 按照基数的位置, 将数组划分成左右两个子数组.
    let pivot_index = partition_pivot_at_right(arr, low, high);
    // 对左右两个子数组分别执行快速排序
    if pivot_index > low + 1 {
        insertion_quicksort_helper(arr, low, pivot_index - 1);
    }
    if pivot_index + 1 < high {
        insertion_quicksort_helper(arr, pivot_index + 1, high);
    }
}

// 选择最右侧的元素作为基准值
fn partition_pivot_at_right<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = high;

    // 以 pivot 为基准, 把数组划分成三部分: 小于 pivot, pivot, 大于等于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = low;
    // j 用于遍历整个数组
    for j in low..high {
        if arr[j] < arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于 pivot, pivot, 大于等于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

迭代形式的快速排序

默认情况下实现的快速排序使用了递归形式, 它用了尾递归调用来保存数组的左右边界值. 我们也可以显式地使用一个栈结构来手动保存它们, 就可以将快速排序改写成迭代形式:

#![allow(unused)]
fn main() {
/// 迭代形式的快速排序
///
/// 空间复杂度是 `O(n)`
#[inline]
pub fn iterative_quicksort<T: PartialOrd>(arr: &mut [T]) {
    if arr.len() < 2 {
        return;
    }
    iterative_quicksort_helper(arr, 0, arr.len() - 1);
}

fn iterative_quicksort_helper<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) {
    if low >= high {
        return;
    }

    let len = high - low + 1;
    let mut stack = vec![0; len];

    // 入栈顺序是 (low, high)
    stack.push(low);
    stack.push(high);

    // 出栈顺序是 (high, low)
    while let (Some(high), Some(low)) = (stack.pop(), stack.pop()) {
        // 按照基数的位置, 将数组划分成左右两个子数组.
        let pivot_index = partition_pivot_at_right(arr, low, high);
        // 对左右两个子数组分别执行快速排序
        // 如果左侧子数组还有元素, 就入栈
        if pivot_index > low + 1 {
            stack.push(low);
            stack.push(pivot_index - 1);
        }
        // 如果 pivot 的右侧还有元素, 就入栈
        if pivot_index + 1 < high {
            stack.push(pivot_index + 1);
            stack.push(high);
        }
    }
}

// 选择最右侧的元素作为基准值
fn partition_pivot_at_right<T: PartialOrd>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot_index = high;

    // 以 pivot 为基准, 把数组划分成三部分: 小于 pivot, pivot, 大于等于 pivot
    // i 用于标记比 pivot 大的元素
    let mut i = low;
    // j 用于遍历整个数组
    for j in low..high {
        if arr[j] < arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }

    // 最后把基准值 pivot 移到合适的位置.
    // 此时, 数组中元素的顺序满足以下条件: 小于 pivot, pivot, 大于等于 pivot
    arr.swap(i, pivot_index);
    // 返回的是 pivot 所在的位置
    i
}

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

随机选择一个元素作为基准值 pivot

尾递归优化 Tail call optimization

稳定快速排序 Stable Quicksort

双轴快速排序 Dual pivot Quicksort

三路快速排序 3-way Quicksort

参考