[算法] Python 快速排序

def hoare_partition(A, p, r):
    x = A[r]
    i = p
    j = r
    while True:
        while A[j] > x: j -= 1
        while A[i] < x: i += 1
        if i < j:
            A[i], A[j] = A[j], A[i]
        else:
            return j

def quicksort(A, p, r):
    # print(A, p, r, p < r)
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)

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

if __name__ == "__main__":
    A = [2, 8, 7, 1, 3, 5, 6, 4]
    quicksort(A, 0, len(A) - 1)
    print(A)

def quicksort(A, p, r):
    # print(A, p, r, p < r)
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)


def partition(A, p, r):
    i = p
    j = r
    m = A[i]
    while True:
        while A[j] > m and i < j:
            j -= 1
        if i < j:
            A[i], A[j] = A[j], A[i]
            i += 1
        while A[i] < m and i < j:
            i += 1
        if i < j:
            A[i], A[j] = A[j], A[i]
            j -= 1
        if i == j:
            break
    return i


if __name__ == "__main__":
    A = [2, 8, 7, 1, 3, 5, 6, 4]
    quicksort(A, 0, len(A) - 1)
    print(A)

import sys
sys.setrecursionlimit(1000000)

import random

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

def randomized_partition(A, p, r):
    i = random.randint(p, r)  #
    A[r], A[i] = A[i], A[r]  #
    return partition(A, p, r)

def randomized_quicksort(A, p, r):
    if p < r:
        q = randomized_partition(A, p, r)
        randomized_quicksort(A, p, q - 1)
        randomized_quicksort(A, q + 1, r)

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)

if __name__ == "__main__":
    A = range(0, 1000)
    # random.shuffle(A)
    B = A[:]
    import timeit
    from functools import partial
    t1 = timeit.Timer(partial(quicksort, A, 0, len(A) - 1)).timeit(1)
    t2 = timeit.Timer(partial(randomized_quicksort, B, 0, len(B) - 1)).timeit(1)
    # print(A)
    # print(B)
    print(t1, t2)

def qsort(L):
     return L if len(L)<=1 else qsort([x for x in L[1:] if x < L[0]]) + L[0:1] + qsort([y for y in L[1:] if y >= L[0]])

def partition(seq):
    pi, seq = seq[0], seq[1:]         # Pick and remove the pivot
    lo = [x for x in seq if x <= pi]  # All the small elements
    hi = [x for x in seq if x > pi]   # All the large ones
    return lo, pi, hi                 # pi is "in the right place"

def quicksort(seq):
    if len(seq) <= 1:                            # Base case
        return seq
    lo, pi, hi = partition(seq)                  # pi is in its place
    return quicksort(lo) + [pi] + quicksort(hi)  # Sort lo and hi separately

from random import randrange
seq = [randrange(1000) for i in range(100000)]
import cProfile
cProfile.run('quicksort(seq)')