Python 快速排序(Quicksort)

思路说明

快速排序算法是一种基于交换的高效的排序算法，由C.R.A.Hoare于1962年提出，是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide and conquer algorithm)。

分治法的基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序的基本思想

从数列中取出一个数作为基准数（枢轴，pivot）。
将数组进行划分(partition)，将比基准数大的元素都移至枢轴右边，将小于等于基准数的元素都移至枢轴左边。
再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素。

操作说明

设当前待排序的无序区为R[low..high]，在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

划分的关键是要求出基准记录所在的位置pivotpos（即pivot = R[pivotpos]）。

划分的结果可以简单地表示为：

R[low..pivotpos-1].keys ≤ R[pivotpos].key ≤ R[pivotpos+1..high].keys（low ≤ pivotpos ≤ high）

然后通过递归调用快速排序对左、右子区间**R[low..pivotpos-1]和R[pivotpos+1..high]**快速排序。

实现方式

 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
# 方法1：递归，基准数为中位数
def quicksort(xs):
    if len(xs) <= 1:
        return xs
    less = []
    lst = []
    more = []
    pivot = xs[(len(xs)-1)//2]  # 将中位数做基准
    for x in xs:
        if x < pivot:
            less.append(x)
        elif x > pivot:
            more.append(x)
        else:
            lst.append(x)
    less = quicksort(less)  # 得到第一轮分组之后，继续将分组进行下去
    more = quicksort(more)

    return less + lst + more
# 方法2：递归，随机抽选基准数
import random

def quicksort(xs):
    if len(xs) <= 1:
        return xs
    pivot = random.choice(xs)
    return quicksort([x for x in xs if x < pivot]) + [pivot] * xs.count(pivot) + quicksort([x for x in xs if x > pivot])
#方法3：非递归操作
def quicksort(xs):
    if len(xs) <= 1:
        return xs
    xs = xs.copy()
    #初始化两个栈
    start_stack = [0, ]
    end_stack = [len(xs)-1, ]

    #进入循环，两个栈均为空时，排序结束
    while start_stack and end_stack:
        #得到本次循环的start 和 end
        start = start_stack.pop()
        end = end_stack.pop()
        #判断子数组是否有序
        if start > end:
            continue
        i = start
        j = end
        while i < j:
            if xs[i] > xs[j]:
                xs[i], xs[j-1], xs[j] = xs[j-1], xs[j], xs[i]
                j -= 1
            else:
                i += 1
        #将两个子数组的开始和结尾push进栈中
        start_stack.append(start)
        end_stack.append(i-1)
        start_stack.append(i+1)
        end_stack.append(end)
    return xs