快速排序：Python语言实现-六虎

快速排序：Python言语完成

什么是快速排序？

快速排序是一种常用的排序算法，比挑选排序快得多。例如，C言语标准库中的函数qsort 完成的就是快速排序。像归并排序（merge sort）相同，快速排序也是一种分治的递归算法。

快速排序算法的进程和阐明

将数组 $S$ 排序的根本算法由下列简略的四步组成：

假如 $S$ 中的元素个数是 $0$ 和 $1$ ，则回来。
取 $S$ 中任一元素 $v$ ，称之为纽带元（pivot）。
将 $S – {v}$ （即S中其余元素）区分红两个不相交的调集： $S1={x∈S−{v}∣x≤v}S_{1} = { x in S – {v} | x le v }$ ， $S2={x∈S−{v}∣x≥v}S_{2} = { x in S – {v} | x ge v }$ 。
回来 ${quicksort(S_{1})，后跟v，继而再quicksort(S_{2})}$ 。

下图给出快速排序算法的直观阐明：

快速排序算法的伪码和阐明

下面是对一个典型的子数组 $A [l .. r]$ 进行快速排序的伪代码：

QuickSort(A, l, r)
1 if l >= r
2 return
3 i = Partition(A, l, r)
4 QuickSort(A, l, i – 1)
5 QuickSort(A, i 1, r)

而算法的核心是Partition进程：

Partition(A, l, r)
1 p = A[r]
2 i = l – 1
3 for j = l to r – 1
4 if A[j] <= p
5 i = i 1
6 exchange A[i] with A[j]
7 exchange A[i 1] with A[r]
8 return i 1

下图显示了Partition如安在一个包括8个元素的数组上进行操作的进程。

Partition总是挑选一个 $p = A [r]$ 作为纽带元（pivot），并环绕它来区分子数组 $A [l .. r]$ 。跟着程序的执行，数组被区分红4个（可能有空的）区域。在Partition伪码的第3～6行的for循环的每一轮迭代的开始，每一个区域都满意一定的性质，咱们将这些性质作为循环不变量：

在第3～6行循环体的每一轮迭代开始时，关于恣意数组下标 $k$ ，有：

若 $l \leq k \leq i$ ，则 $A [k] \leq p$ 。
若 $i 1 \leq k \leq j - 1$ ，则 $A [k] > p$ 。
若 $k = r$ ，则 $A [k] = p$ 。

可是上述三种状况没有覆盖下标 $j$ 到 $r - 1$ ，对应方位的值与纽带元之间也不存在特定的巨细关系。如下图所示：

下图给出第3～6行循环体的每一轮迭代中，根据第4行中条件判别的不同结果，算法的不同处理。

快速排序算法的Python完成

根据快速排序算法的伪码，咱们能够轻松的给出Python版别的完成。

首先是给出测验驱动代码：

test_quicksort.py

#!/usr/bin/env python3
# test_quicksort.py
from quicksort import quicksort
import random
def main(size = 1000):
    lyst = []
    for count in range(size):
        lyst.append(random.randint(1, size   1))
    answer = sorted(lyst)
    print(lyst)
    quicksort(lyst)
    print(lyst)
    if answer == lyst:
        print("quicksort is correct!")
    else:
        print("quicksort is not correct!")
if __name__ == "__main__":
    main()

然后是quicksort的完成代码：

quicksort.py

#!/usr/bin/env python3
# quicksort.py
def quicksort(lyst):
    quicksortHelper(lyst, 0, len(lyst) - 1)
def quicksortHelper(lyst, left, right):
    if left >= right:
        return
    pivotLocation = partition(lyst, left, right)
    quicksortHelper(lyst, left, pivotLocation - 1)
    quicksortHelper(lyst, pivotLocation   1, right)
def partition(lyst, left, right):
    pivot = lyst[right]
    i = left - 1
    for j in range(left, right):    # left to right - 1
        if lyst[j] <= pivot:
            i = i   1
            swap(lyst, i, j)
    swap(lyst, i   1, right)
    return i   1
def swap(lyst, i, j):
    """Exchanges the items at positions i and j."""
    # You could say lyst[i], lyst[j] = lyst[j], lyst[i]
    # but the following code shows what is really going on
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp

快速排序算法的改进和优化

接下来，咱们逐步改进和优化快速排序，终究的算法接近于C 标准库中std::sort的完成。

STEP1

首先咱们把Partition进程批改成最早由C.A.R.Hoare提出时的模样，当然这儿的伪码可能与最原始Hoare版别有所出入：

Hoare-Partition(A, l, r)
01 p = A[r]
02 i = l – 1
03 j = r
04 while TRUE
05 repeat
06 i = i 1
07 until A[i] >= p
08 repeat
09 j = j – 1
10 until j == l or A[j] <= p
11 if i < j
12 exchange A[i] with A[j]
13 else
14 break
15 exchange A[i] with A[r]
16 return i

下图显示了Hoare-Partition如安在一个包括10个元素的数组上进行操作的进程。

更新了Partition进程的完好代码如下：

quicksort.py

#!/usr/bin/env python3
# quicksort.py
def quicksort(lyst):
    quicksortHelper(lyst, 0, len(lyst) - 1)
def quicksortHelper(lyst, left, right):
    if left >= right:
        return
    pivotLocation = partition(lyst, left, right)
    quicksortHelper(lyst, left, pivotLocation - 1)
    quicksortHelper(lyst, pivotLocation   1, right)
def partition(lyst, left, right):
    pivot = lyst[right]
    i = left - 1
    j = right
    while True:
        while True:
            i = i   1
            if lyst[i] >= pivot:
                break
        while True:
            j = j - 1
            if j == left or lyst[j] <= pivot:
                break
        if i < j:
            swap(lyst, i, j)
        else:
            break
    swap(lyst, i, right)
    return i
def swap(lyst, i, j):
    """Exchanges the items at positions i and j."""
    # You could say lyst[i], lyst[j] = lyst[j], lyst[i]
    # but the following code shows what is really going on
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp

STEP2

听说，关于很小的数组（ $N \leq 20$ ），快速排序不如插入排序。所以，咱们批改QuickSort算法，当数组长度小于某个值（这儿选了10）时，改成调用插入排序：

QuickSort(A, l, r)
1 if r – l <= 10
2 return InsertionSort(A, l, r)
3 i = Partition(A, l, r)
4 QuickSort(A, l, i – 1)
5 QuickSort(A, i 1, r)

由于批改一目了然，且这儿也不计划介绍插入排序算法，就直接给出Python完成：

quicksort.py

#!/usr/bin/env python3
# quicksort.py
def quicksort(lyst):
    quicksortHelper(lyst, 0, len(lyst) - 1)
def quicksortHelper(lyst, left, right):
    if right - left <= 10:
        return insertionSort(lyst, left, right)
    pivotLocation = partition(lyst, left, right)
    quicksortHelper(lyst, left, pivotLocation - 1)
    quicksortHelper(lyst, pivotLocation   1, right)
def partition(lyst, left, right):
    pivot = lyst[right]
    i = left - 1
    j = right
    while True:
        while True:
            i = i   1
            if lyst[i] >= pivot:
                break
        while True:
            j = j - 1
            if j == left or lyst[j] <= pivot:
                break
        if i < j:
            swap(lyst, i, j)
        else:
            break
    swap(lyst, i, right)
    return i
def swap(lyst, i, j):
    """Exchanges the items at positions i and j."""
    # You could say lyst[i], lyst[j] = lyst[j], lyst[i]
    # but the following code shows what is really going on
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp
def insertionSort(lyst, left, right):
    i = left   1
    while i <= right:
        itemToInsert = lyst[i]
        j = i - 1
        while j >= 0:
            if itemToInsert < lyst[j]:
                lyst[j   1] = lyst[j]
                j -= 1
            else:
                break
        lyst[j   1] = itemToInsert
        i  = 1

STEP3

当Partition（区分）n个元素的子数组，产生包括了 $n - 1$ 个元素和 $0$ 个元素时，快速排序的最坏状况发生了。为了防止这种状况，通常会采用随机挑选纽带元的办法。

这儿给出一个叫Median-of-Three Partitioning（三数中值分隔法）的办法，一句话来描绘：将子数组的左端、右端和中心方位上的三个元素的中值作为纽带元。

这次先给出Python完成代码，稍后再给出解说阐明：

quicksort.py

#!/usr/bin/env python3
# quicksort.py
def quicksort(lyst):
    quicksortHelper(lyst, 0, len(lyst) - 1)
def quicksortHelper(lyst, left, right):
    if right - left <= 10:
        return insertionSort(lyst, left, right)
    pivotLocation = partition(lyst, left, right)
    quicksortHelper(lyst, left, pivotLocation - 1)
    quicksortHelper(lyst, pivotLocation   1, right)
def partition(lyst, left, right):
    median3(lyst, left, right)
    pivot = lyst[right - 1]
    i = left
    j = right - 1
    while True:
        while True:
            i = i   1
            if lyst[i] >= pivot:
                break
        while True:
            j = j - 1
            if lyst[j] <= pivot:
                break
        if i < j:
            swap(lyst, i, j)
        else:
            break
    swap(lyst, i, right - 1)
    return i
def median3(lyst, left, right):
    center = (left   right) // 2
    if lyst[center] < lyst[left]:
        swap(lyst, center, left)
    if lyst[right] < lyst[left]:
        swap(lyst, left, right)
    if lyst[right] < lyst[center]:
        swap(lyst, center, right)
    swap(lyst, center, right - 1)
def swap(lyst, i, j):
    """Exchanges the items at positions i and j."""
    # You could say lyst[i], lyst[j] = lyst[j], lyst[i]
    # but the following code shows what is really going on
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp
def insertionSort(lyst, left, right):
    i = left   1
    while i <= right:
        itemToInsert = lyst[i]
        j = i - 1
        while j >= 0:
            if itemToInsert < lyst[j]:
                lyst[j   1] = lyst[j]
                j -= 1
            else:
                break
        lyst[j   1] = itemToInsert
        i  = 1

下图显示了median3（Median-of-Three）如安在一个包括10个元素的数组上进行操作的进程。

当median3调用完，纽带元在子数组的从右数第二个元素（索引为 $r - 1$ ），
子数组的左端元素（索引为 $l$ ）小于纽带元，
子数组的右端元素（索引为 $r$ ）大于纽带元，
所以Partition进程需求处理的区间就从本来的 $[l, r - 1]$ （索引 $r$ 为pivot）
变成 $[l 1, r - 2]$ （索引 $r - 1$ 为pivoit），并且由于左右端的元素能够作为岗兵元素，
所以关于索引 $j$ 是否跳过子数组左端的判别也能够去掉了。

至此，咱们就用Python完成了一个相对完好快速排序算法。

最后给出所有完成的工程代码路径：

参阅文档：

《算法导论（原书第3版）》
《算法详解（卷1）——算法根底》
《算法：C言语完成(第1-4部分)根底知识、数据结构、排序及查找（原书第3版）》
《算法Ⅰ～Ⅳ（C 完成）——根底、数据结构、排序和查找（第三版）》
《数据结构与算法剖析——C言语描绘（原书第2版）》
《数据结构与算法剖析——C 言语描绘（第四版）》
《数据结构（Python言语描绘）》

快速排序：Python语言实现

快速排序：Python言语完成

什么是快速排序？

快速排序算法的进程和阐明

快速排序算法的伪码和阐明

快速排序算法的Python完成

快速排序算法的改进和优化

参阅文档：

作者信息

推广

快速排序：Python语言实现

快速排序：Python言语完成

什么是快速排序？

快速排序算法的进程和阐明

快速排序算法的伪码和阐明

快速排序算法的Python完成

快速排序算法的改进和优化

参阅文档：

相关文章

种一棵树最好的时间是10年前，其次是现在

SQL Optimizer 解析 | 青训营笔记

使用 GPG 签名提交

聊聊JAVA中的并发工具类

作者信息

推广