今天面试快排竟然没有写出来，囧… 再练一遍。

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
import random


def quickSort(arr, left, right):
    if left >= right:
        return
    pivot = random.randint(left, right)
    arr[pivot], arr[right] = arr[right], arr[pivot]
    q = left
    p = left - 1
    while q < right:
        if arr[q] < arr[right]:
            p += 1
            arr[p], arr[q] = arr[q], arr[p]
        q += 1
    p += 1
    arr[p], arr[right] = arr[right], arr[p]
    quickSort(arr, left, p - 1)
    quickSort(arr, p + 1, right)


def sort(arr):
    if not arr:
        return []
    lenArr = len(arr)
    quickSort(arr, 0, lenArr - 1)
    return arr


print(sort([3, 2, 1, 5, 4]))