排序-快速排序（下） | 8lovelife's life

8lovelife's life

M&M

0%

排序-快速排序（下）

发表于 更新于 分类于
本文字数： 883 阅读时长 ≈ 3 分钟

本文主要针对 排序-快速排序（上） 中的问题进行常见优化

1。重复元素 2。PIVOT选择

重复元素

排序-快速排序（上）中的快速排序实现，在重复元素情况下效果不佳

image

Bentley-Mcilroy’s 3-way

使用 Bentley-Mcilroy’s 3-way 方式优化 Hoare partition 方案，这里有视频图例，代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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 le_mid = lo-1;
    let mut gt = hi;
    let mut re_mid = 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);
        if arr[lt as usize] == arr[pivot as usize] {
            le_mid +=1;
            arr.swap(le_mid as usize, lt as usize);
        }
        if arr[gt as usize] == arr[pivot as usize] {
            re_mid -=1;
            arr.swap(re_mid as usize,gt as usize);
        }
    }
    arr.swap(pivot, lt as usize);
    lt = gt+1;
    for i in lo..le_mid {
        arr.swap(i as usize,gt as usize);
        gt -=1;
    }
    for j in (re_mid+1..hi).rev(){
        arr.swap(j as usize, lt as usize);
        lt +=1;
    }
    (gt,lt)
}

优化后的结果如下

image

PIVOT选择

再来看一组10W个有序整数的排序算法耗时情况

image

这种情况下快速排序也没有冒泡、插入排序快，同时也比希尔排序差

PIVOT的选择通常有 1。中位数 2。Tukey’s Ninther 两种方式，文章选择 中位数 的方式进行选择实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
fn _hoare_partition<T:Ord>(arr:&mut[T],lo:isize,hi:isize)->(isize,isize){
    let pivot = hi as usize;
    let mid = _median(arr, lo, hi);
    arr.swap(hi as usize, mid as usize);
    let mut lt = lo-1;
    let mut le_mid = lo-1;
    let mut gt = hi;
    let mut re_mid = 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);
        if arr[lt as usize] == arr[pivot as usize] {
            le_mid +=1;
            arr.swap(le_mid as usize, lt as usize);
        }
        if arr[gt as usize] == arr[pivot as usize] {
            re_mid -=1;
            arr.swap(re_mid as usize,gt as usize);
        }
    }
    arr.swap(pivot, lt as usize);
    lt = gt+1;
    for i in lo..le_mid {
        arr.swap(i as usize,gt as usize);
        gt -=1;
    }
    for j in (re_mid+1..hi).rev(){
        arr.swap(j as usize, lt as usize);
        lt +=1;
    }
    (gt,lt)
}

fn _median<T:Ord>(arr:&mut[T],lo:isize,hi:isize)->isize {
    let mid = lo+(hi-lo+1)/2;
    let first = &arr[lo as usize];
    let middle = &arr[mid as usize];
    let last = &arr[hi as usize];
    if first > middle {
        if middle > last {
            mid
        } else if first < last {
            lo
        } else {
            hi
        }
    } else {
        if middle < last {
            mid
        } else if first > last {
            lo
        } else {
            hi
        }
    }
}

优化后的结果如下
image

附录

快速排序完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
fn _hoare_partition<T:Ord>(arr:&mut[T],lo:isize,hi:isize)->(isize,isize){
    let pivot = hi as usize;
    let mid = _median(arr, lo, hi);
    arr.swap(hi as usize, mid as usize);
    let mut lt = lo-1;
    let mut le_mid = lo-1;
    let mut gt = hi;
    let mut re_mid = 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);
        if arr[lt as usize] == arr[pivot as usize] {
            le_mid +=1;
            arr.swap(le_mid as usize, lt as usize);
        }
        if arr[gt as usize] == arr[pivot as usize] {
            re_mid -=1;
            arr.swap(re_mid as usize,gt as usize);
        }
    }
    arr.swap(pivot, lt as usize);
    lt = gt+1;
    for i in lo..le_mid {
        arr.swap(i as usize,gt as usize);
        gt -=1;
    }
    for j in (re_mid+1..hi).rev(){
        arr.swap(j as usize, lt as usize);
        lt +=1;
    }
    (gt,lt)
}
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);
}
fn _median<T:Ord>(arr:&mut[T],lo:isize,hi:isize)->isize {
    let mid = lo+(hi-lo+1)/2;
    let first = &arr[lo as usize];
    let middle = &arr[mid as usize];
    let last = &arr[hi as usize];
    if first > middle {
        if middle > last {
            mid
        } else if first < last {
            lo
        } else {
            hi
        }
    } else {
        if middle < last {
            mid
        } else if first > last {
            lo
        } else {
            hi
        }
    }
}

参考

Quicksort
快速排序-下

All those moments will be lost in time, like tears in rain. - Roy Batty

Blade Runner