Quick Sort 快排#

Quick Sort的Python实现

 1def pivot(my_list, start_index, end_index):
 2
 3    pivot_index = start_index
 4    swap_index = pivot_index
 5    swap = False
 6
 7    for i in range(pivot_index + 1, end_index + 1):
 8
 9        if my_list[i] < my_list[pivot_index]:
10
11            if swap:
12                swap_index += 1
13                my_list[swap_index], my_list[i] = my_list[i], my_list[swap_index]
14            else:
15                swap_index += 1
16            i += 1
17
18        elif my_list[i] > my_list[pivot_index]:
19            i += 1
20            swap = True
21
22    my_list[pivot_index], my_list[swap_index] = (
23        my_list[swap_index],
24        my_list[pivot_index],
25    )
26
27    return swap_index
28
29
30my_list = [6, 5, 3, 1, 8, 7, 2, 4]
31
32
33def quick_sort(my_list, start_index, end_index):
34
35    if start_index < end_index:
36
37        pivot_index = pivot(my_list, start_index, end_index)
38
39        quick_sort(my_list, start_index, pivot_index)
40        quick_sort(my_list, pivot_index + 1, end_index)
41
42
43quick_sort(my_list, 0, len(my_list) - 1)
44
45print(my_list)