本文主要介绍了快速排序的基本思路,包括伪代码和 Python 实现。同时,也介绍了快速排序的优化方式,如随机锚点和三路快排。

与归并排序一样,快速排序同样使用了分治的思想。在执行时,选取一个锚点(pivot),比如数组位置 0 的元素,然后遍历剩下的部分,如果元素小于或等于锚点,则将其移至锚点左侧。遍历完成后,锚点左侧的元素都不大于锚点位置的值,锚点右侧的元素都大于锚点。接下来,递归地对锚点左侧的部分以及锚点右侧的部分(子问题)执行快速排序,直到子问题的数组长度为 1,此时说明数组已排好序。

下图中的实现方式,直接修改了原数组,没有返回值。

伪代码:


QuickSort(A, l, r)
    if l >= r:
        return
    m = Partition(A, l, r)
    QuickSort(A, l, m - 1)
    QuickSort(A, m + 1, r)

Partition(A, l, r)
    x = a[l] // use first element as pivot
    j = l
    for i from l + 1 to r:
        if A[i] <= x:
            j += 1
            swap A[i] and A[j]
    swap A[l] and A[j]
    return j

Python 实现:

def quick_sort(A, l, r):
    if l >= r:
        return
    m = partition(A, l, r)
    quick_sort(A, l, m - 1)
    quick_sort(A, m + 1, r)

def partition(A, l, r):
    x = A[l]
    j = l
    for i in range(l + 1, r):
        if A[i] <= x:
            j = j + 1
            A[i], A[j] = A[j], A[i]
    A[j], A[l] = A[l], A[j]
    return j

if __name__ == '__main__':
    n = 5
    a = [2,3,9,2,2]
    quick_sort(a, 0, n)
    for x in a:
        print(x, end=' ')

优化:随机锚点
伪代码:

RandomizedQuickSort(A, l, r)
    if l >= r
        return
    k = random int between l and r
    swap A[l] and A[k] // 将锚点位置与起始位置的元素交换,于是就转换成了基础版本的快速排序
    m = Partition(A, l, r)
    QuickSort(A, l, m - 1)
    QuickSort(A, m + 1, r)

Python 实现:
partition 函数不变。使用 random 库需要引入: import random

import random
def randomized_quick_sort(A, l, r):
    if l >= r:
        return
    k = random.randint(l, r - 1)
    A[l], A[k] = A[k], A[l]
    m = partition(A, l, r)
    randomized_quick_sort(A, l, m - 1)
    randomized_quick_sort(A, m + 1, r)

在上述随机锚点的基础上,如果数组中有很多大小相等的元素,还可以进一步优化性能。方法是将双路快排变为三路快排。选取锚点之后,进行遍历时,将小于锚点值的元素移至锚点左边,大于锚点的值移至数组末尾。

伪代码

Partition3(a, l, r)
    x, j, t = a[l], l, r
    i = j
    while i <= t:
        if a[i] < x:
            swap a[i] and a[j]
            m1 += 1 // [l...j-1] elements are all less than x
        else if a[i] > x:
            swap a[t] and a[i]
            t -= 1 // [t-1...r] elements are all greater than x
            i -= 1 // i need to remain at the same index, since an uncompared element was just swapped here
        i += 1

Python 实现:

def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    k = random.randint(l, r)
    a[l], a[k] = a[k], a[l]
    #use partition3
    m1, m2 = partition3(a, l, r) // uses 3-way partition
    randomized_quick_sort(a, l, m1 - 1);
    randomized_quick_sort(a, m2 + 1, r);

def partition3(a, l, r):
    x, j, t = a[l], l, r
    i = j

    while i <= t :
      if a[i] < x:
         a[j], a[i] = a[i], a[j]
         j += 1

      elif a[i] > x:
         a[t], a[i] = a[i], a[t]
         t -= 1
         i -= 1 # remain in the same i in this case
      i += 1   
    return j, t

三路快排的 JavaScript 实现:

function quickSort(array) {
  // change code below this line
  let arr = array
  myQuickSort(arr, 0, arr.length - 1)

  function myQuickSort(a, l, r) {
    if (l >= r) return
    let k = Math.floor(Math.random()*(r-l) + l)
    swap(a, l, k)
    let [m1, m2] = partition3(a, l, r)
    myQuickSort(a, l, m1 - 1)
    myQuickSort(a, m2 + 1, r)
  }

  function swap(a, i, j) {
    let tmp = a[i]
    a[i] = a[j]
    a[j] = tmp
  }

  function partition3(a, l, r){
    let x = a[l]
    let j = l
    let t = r
    let i = j
    while(i <= t){
      if(a[i] < x){
        swap(a, i, j)
        j ++
      } else if(a[i] > x){
        swap(a, i, t)
        i --
        t --
      }
      i ++
    }
    return [j, t]
  }
  // change code above this line
  return arr;
}

console.log(quickSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]))

// test array:
// [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]