Skip to content

Latest commit

 

History

History
113 lines (105 loc) · 4.5 KB

1C.md

File metadata and controls

113 lines (105 loc) · 4.5 KB

快速排序

　　归并排序其实已经将比较操作优化到极致了（极致就是O(NlogN)，兴趣的读者可以自行证明），但挪移操作还有改进空间。或许你还记得选择排序那霸气的O(N)，不过最先关注挪移操作的可是落魄的冒泡排序，它的后继者——快速排序则要来上演一番逆袭……

就是快

敢叫“快速”排序，怎能不快？在详细分析之前，我们先来50万的随机数列：

BubleSort:  7m54.7781557s   --被虐成狗了...
SelectSort: 1m37.8355959s   --找回个人样...
InsertSort: 35.150961669s   --打扮打扮...
HeapSort:   63.997412ms     --快!
MergeSort:  44.774008ms     --再快!
QuickSort:  33.254639ms     --更快!
RadixSort:  19.501779ms     --还能愉快地玩耍么？

鉴于神奇的基数排序在使用上有其局限性，快速排序是已知通用排序算法中最快的。

流动与分层

　　那么“快速”是怎么做到的呢？奥妙竟在从冒泡排序那里继承而来的浮沉之道。君看，水和油混到一起，不一会儿便分成了两层。这种流动比气泡逐个往上冒快多了，我们可以借鉴。

func partition[T constraints.Ordered](list []T) int {
    size := len(list)
    m, s := size/2, size/4
    a, m, b := sort3(list, m-s, m, m+s)
    s = size - 1
    pivot := list[m]
    list[0], list[a] = list[a], list[0]
    list[s], list[b] = list[b], list[s]
    a, b = 1, s-1
    for {
        for list[a] < pivot { a++ }             //不挪才是
        for list[b] > pivot { b-- }             //快的关键
        if a >= b { break }
        list[a], list[b] = list[b], list[a]     //不合适就换位
        a++; b--
    }
    return a
}

也可以分三层，有和二分相近的比较次数（以下实现偏多），比二分少两成的访存（不过写操作会增多）：

func triPartition[T constraints.Ordered](list []T) (fst, snd int) {
    size := len(list)
    m, s := size/2, size/4
    x, l, _, r, y := sort5(list, m-s, m-1, m, m+1, m+s)
    s = size - 1
    pivotL, pivotR := list[l], list[r]
    list[l], list[r] = list[0], list[s]
    list[1], list[x] = list[x], list[1]
    list[s-1], list[y] = list[y], list[s-1]
    l, r = 2, s-2
    for {
        for list[l] < pivotL { l++ }
        for list[r] > pivotR { r-- }
        if list[l] > pivotR {
            list[l], list[r] = list[r], list[l]
            r--
            if list[l] < pivotL {
                l++
                continue
        }   }
        break
    }
    for k := l + 1; k <= r; k++ {
        if list[k] > pivotR {
            for list[r] > pivotR { r-- }
            if k >= r { break }
            if list[r] < pivotL {
                list[l], list[k], list[r] = list[r], list[l], list[k]
                l++
            } else {
                list[k], list[r] = list[r], list[k]
            }
            r--
        } else if list[k] < pivotL {
            list[k], list[l] = list[l], list[k]
            l++
    }   }
    list[0], list[l-1] = list[l-1], pivotL
    list[s], list[r+1] = list[r+1], pivotR
    return l-1, r+1
}

　　分层与归并虽然方向相背，却都只需一次遍历就能完成。归并在这一次遍历中对每一个元素都进行了挪移，而分层过程仅挪移了某些元素，这点使快速排序能够比归并排序更快。

内省排序

　　如上文所述，快速排序的平均复杂度和归并排序是一个级别的，但最坏情况下却在向选择排序看齐。 幸好快速排序不是一个人在战斗，于是有了所谓的内省排序。

func IntroSortY[T constraints.Ordered](list []T) {
    life := bits.Len(uint(len(list))) * 3 / 2
    introSortY(list, life)
}
func introSortY[T constraints.Ordered](list []T, life int) {
    for len(list) > lowerBoundY {
        if life--; life < 0 {               //时辰到了还没解决
            HeapSort(list)                  //果断召唤小伙伴
            return                          //也可以召唤MergeSort
        }
        fst, snd := triPartition(list)
        introSortY(list[:fst], life)
        introSortY(list[snd+1:], life)
        if list[fst] == list[snd] { return }
        list = list[fst+1 : snd]
    }
    SimpleSort(list)
}

内省排序结合了三种排序思想（召唤堆排序的话），是排序算法之集大成者。

堆排序是选择排序的进化版，具体我们到第五章再讨论，心急的读者可以 先睹为快 。

目录　上一节　下一节