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

def quickSort(arr, left=None, right=None):
    # 如果 left 不是整数或浮点数，那么将 left 设置为 0；否则保留 left 的原值。
    left = 0 if not isinstance(left, (int, float)) else left

    # 如果 right 不是一个整数或浮点数，那么 right 的值会被设置为数组 arr 的最后一个索引。
    # 如果 right 已经是一个整数或浮点数，那么它的值将保持不变。
    right = len(arr) - 1 if not isinstance(right, (int, float)) else right

    if left < right:
        # 执行分区操作，将数组分为两部分，左边都小于等于基准值，右边都大于基准值
        partition_index = partition(arr, left, right)
        # 对左半部分进行递归排序
        quickSort(arr, left, partition_index - 1)
        # 对右半部分进行递归排序
        quickSort(arr, partition_index + 1, right)
    return arr


def partition(arr, left, right):
    # 将第一个元素设为基准
    pivot = left
    # 初始化基准最终位置的索引
    index = pivot + 1

    # 从基准的下一个元素开始遍历数组
    i = index
    while i <= right:
        # 如果当前元素小于基准，将其与索引位置的元素交换，并递增索引
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1

    # 将基准与索引 -1 位置的元素交换，以将基准放置在其正确位置
    swap(arr, pivot, index - 1)
    return index - 1


def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]