排序-快速排序（上）

快速排序算法由 TONY HOARE（1934-） 在1959年在莫斯科国立大学期间发明，于1961年发布于ACM算法存储库。霍尔的老板曾在工作中要求他实现希尔排序，霍尔认为他有比希尔排序更好的算法，为此他还和老板打赌了六便士，结果是霍尔赢了

简介

快速排序是一种不稳定的交换排序算法，它利用分治的思想将一个大的问题分解为若干小问题，然后逐一击破小问题，从而高效的解决最终问题。算法的核心是如何分，常见的分区方案有：Lomuto partition 和 Hoare partition。本文使用的是 Hoare partition 方案

原理

这里有视频图例

1. 首先选择中间值（PIVOT）
2. 以 PIVOT 分割成两部分（大于和小于）
3. 对 PIVOT 两侧部分别重复1、2操作

代码实现

使用Rust语言实现快速排序算法，Hoare partition 分区方案

fn _hoare_partition<T:Ord>(arr:&mut[T],lo:isize,hi:isize)->(isize,isize){
    let pivot = hi as usize;
    let mut lt = lo-1;
    let mut gt = hi;
    loop {
        lt +=1;
        while lt <=hi && arr[lt as usize] < arr[pivot] {
            lt +=1;
        }
        gt -=1;
        while gt >=0 && arr[gt as usize] > arr[pivot] {
            gt -=1;
        }
        if lt >=gt {
            break;
        }
        arr.swap(lt as usize, gt as usize);
    }
    arr.swap(pivot, lt as usize);
    (lt-1,lt+1)
}
fn _quick_recursive<T:Ord>(arr:&mut[T],lo:isize,hi:isize){
    if lo < hi {
        let p =_hoare_partition(arr, lo, hi);
        _quick_recursive(arr, lo, p.0);
        _quick_recursive(arr, p.1, hi);
    }
}
pub fn quick_sort<T:Ord>(arr:&mut[T]){
    let hi = arr.len()-1;
    _quick_recursive(arr, 0, hi as isize);
}

时间复杂度

问题

来看一组10W个相等整数排序算法的耗时比较

这种情况下快速排序甚至没有冒泡、插入排序快。这个问题会在 排序-快速排序（下）中优化解决

拓展

1. NULL引用的发明者是Tony Hoare
2. Tony Hoare 与 Edsger W. Dijkstra 一起提出了著名的哲学家就餐问题

参考

Quicksort
快速排序-上

If you put your mind to it, you can accomplish anything. - Doc Brown

Back to the Future