Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
215 lines (176 sloc) 6.96 KB
layout title date categories
post
五种常见快排
2018-09-04 09:00:05 +0800
算法

In short

最近开始重新复习算法,从最基本的数据结构开始,到排序和查找,动态规划,将最常见算法问题使用代码写一遍。每次写快排或看快排代码实现时都觉得特别凌乱。[《暗时间》中说道,快排是一个很简单的算法,很多人之所以觉得难是因为没有理解好它背后的思路;在《编程珠玑》里也有对快排的分析,不同质量的快排代码有好几倍的性能差距。以下我分析一下常见的四种快排算法。

快排思想:从数组中随机选择一个数 pivot,将所有小于等于 pivot 的数移动到数组左边,将所有大于 pivot 的数移动到右边,分别对左右两边的子数组重复进行上述操作,直到子数组的长度小于等于 1。

def qsort(arr: list, low: int, high: int):
    if low >= high:
        return
    pos = partition(arr, low, high)
    qsort(arr, low, pos - 1)
    qsort(arr, pos + 1, high)

partition 函数的功能:将所有小于等于 pivot 的数移动到数组左边,将所有大于 pivot 的数移动到右边,并且返回最终 pivot 元素的位置 pos,满足: arr[low : pos] <= pivot and arr[pos + 1 : high] > pivot

以下函数声明 def partition(arr: list, low: int, high: int) 均为左闭右闭,当前数组为 arr[low:high+1]

第一种

边界条件:

  1. 选择当前数组的最后一个元素作为分界值
  2. 选择 index 满足 arr[low:index] <= pivot
def partition(arr: list, low: int, high: int):
    # choose the last elem as pivot.
    pivot = arr[high]
    # make sure arr[low:index] <= pivot
    index = low
    for i in range(low, high):
        if arr[i] <= pivot:
            arr[index], arr[i] = arr[i], arr[index]
            index += 1
    # if pivot == max(arr[low:high+1]):
    #       index == high
    # else:
    #       index < high and arr[index] > pivot
    arr[index], arr[high] = pivot, arr[index]
    return index

第二种

边界条件:

  1. 选择当前数组的第 0 号元素作为分界值
  2. arr[:head] <= pivot and arr[tail:high] > pivot
  3. scanner == head + 1
def partition(arr: list, low: int, high: int):
    # choose the first elem as pivot
    pivot = arr[low]
    # arr[low:head] <= pivot
    # arr[tail+1:high+1] > pivot
    # head point to the empty position
    head = low
    tail = high
    # always scanner == head + 1
    scanner = head + 1
    while scanner <= tail:
        if arr[scanner] > pivot:
            arr[tail], arr[scanner] = arr[scanner], arr[tail]
            tail -= 1
        else:
            arr[head] = arr[scanner]
            head += 1
            scanner += 1
    # head point to the empty position. and satisfy:
    # arr[low:head] <= pivot and arr[tail+1:high+1] > pivot and head == tail
    # so arr[head+1:high+1] > pivot, arr[head] is the position for pivot.
    arr[head] = pivot
    return head

第三种

边界条件:

  1. 选择当前数组第 0 号元素作为分界值
  2. 同时发起从左到右、从右到左扫描,将大于 pivot 的放在右边,小于等于 pivot 的放在左边
  3. arr[low:l] <= pivot and arr[h+1:high+1] > pivot
def partition(arr: list, low: int, high: int):
    # choose the first elem as pivot
    pivot = arr[low]
    # arr[low:l] <= pivot
    # arr[h+1:high+1] >= pivot
    l = low + 1
    h = high
    while l <= h:
        while l <= h and arr[l] <= pivot:
            l += 1
        while l <= h and arr[h] > pivot:
            h -= 1
        if l < h:
            #  arr[l] > pivot and arr[h] <= pivot, switch them.
            arr[l], arr[h] = arr[h], arr[l]
    # satisfy l == h + 1 and arr[low:l] <= pivot and arr[l:high+1] > pivot
    # so arr[h] <= pivot
    arr[low], arr[h] = arr[h], pivot
    return h

三种快排实现选择了不同的方法,但核心思想是一样的。

前三种快排实现的思路:选择当前数组中的一个元素作为 pivot,将大于 pivot 的元素移到右边,将小于等于 pivot 的元素移到左边。

更好的实现是随机地选择一个的元素作为 pivot。

第四种

如果当前数组中重复的元素特别多的时候,上述的快排实现性能会快速下降。快排最理想的情况是,每次都均分地切分数组,树的高度为 logN,时间复杂度为:O(NlogN),其中 N 为数组长度。快排最不理想的情况是,每次选择的 pivot 为数组的最大值,每次都将数组切割为 arr[low:high] 与 arr[high](arr[high] == pivot),树的高度为 O(N),时间复杂度:O(N^2)。

三路快排:将当前数组分为三部分 low <= l <= h <= high 满足 arr[low:l] < pivot and arr[l:h+1] == pivot and arr[h+1:high+1] > pivot

边界条件:

  1. 选择当前数组第 0 个元素作为分界值
  2. arr[low:l] < pivot and arr[l:scanner] == pivot and arr[h+1:high+1] > pivot and arr[scanner:h+1] to scan
def qsort3(arr: list, low: int, high: int):
    if low >= high:
        return
    pivot = arr[low]
    # arr[low:l] < pivot
    # arr[l] == pivot
    # arr[h+1:high+1] > pivot
    l = low
    h = high
    scanner = low + 1
    while scanner <= h:
        if arr[scanner] < pivot:
            arr[l], arr[scanner] = arr[scanner], arr[l]
            l += 1
            scanner += 1
        elif arr[scanner] > pivot:
            arr[h], arr[scanner] = arr[scanner], arr[h]
            h -= 1
        else:
            scanner += 1
    # scanner == h + 1
    # arr[l] == pivot
    # arr[h] == pivot
    # arr[low:l] < pivot and arr[h+1:high+1]
    # so split the arr to three part: arr[low:l] + arr[l:h+1] + arr[h+1:high+1]
    qsort3(arr, low, l - 1)
    qsort3(arr, h + 1, high)

在我理解过程中,三路快排是最容易的。

第五种

单向链表的快速排序。

单链表能够访问一个节点的下一个节点,但是链表中节点的交换位置操作比较复杂,涉及到比较多边界条件,比如是否是头结点之类的,所以交换节点位置的操作改为交换节点中 key-value。代码如下:

type Node struct {
    v    interface{}
    k    int
    next *Node
}

// Quick sort for list [start, end)
func qsortList(start, end *Node) {
    if start == end {
        return
    }
    p, q := start, start.next
    for q != end {
        if q.k < p.k {
        // swap the value, not change list structure
            swap(p, q)
            p = p.next
            swap(p, q)
        }
        q = q.next
    }
    // sort [start, p)
    qsortList(start, p)
    // sort (p, end)
    qsortList(p.next, end)
}

func swap(p, q *Node) {
    p.v, q.v = q.v, p.v
    p.k, q.k = q.k, p.k
}

Conclusion

写代码前先确保几件事:

  1. 掌握算法的核心思想
  2. 设定几个边界条件
  3. 变量在变化过程中严格遵守边界条件

按照上述要求,我们在理解代码离开循环或选择语句时就不会陷入迷惑。