快排的核心思想

在数组中随机选取一个元素 p，一次排序后使得p前面的元素都比p小，p后面的元素都比p大。

然后再将p前面和后面的元素分别进行刚才同样的排序。如此反复执行，最后将得到一个有序的数组。

算法解释

假设有数组 6 5 7 2 3 9 1

如果每次都选取第一个元素 为 p,

第一次排序

排序元素 6 5 7 2 3 9 1

选取 p = 3 排序后要求 2 1 3 5 6 9 7 3前面的顺序不重要 重要的是 3前面的元素都比3小，后面的都比3 大

第二次排序

排序元素 2 1 选取 p = 2 排序后要求 1 2

2前面的元素都比2小，后面的都比2 大

第三次排序

排序元素 5 6 9 7 选取 p = 5 排序后要求 5 6 9 7

5前面的元素都比5小，后面的都比5 大

第四次排序

排序元素 1 选取 p = 1 排序后要求 1

1前面的元素都比1小，后面的都比1 大

第 ... 次排序

单次排序

只需要排序后 使得 p前面的元素都比p小，后面的都比p大。设置两个指针 p_start 指向数组头部，p_end指向数组尾部。从尾部开始向前找到一个比p小的元素，再从头开始找一个比p大的元素，然后交换他们两个的位置。如此反复，最后总会有一个时刻 p_start = p_end,这个位置就是p应该在的位置。

代码实现 python

def sort(datas, start_index, end_index):    pivot = datas[start_index]    while start_index < end_index:        while datas[end_index] > pivot and start_index < end_index:            end_index -= 1        while datas[start_index] <= pivot and start_index < end_index:            start_index += 1        if start_index < end_index:            temp = datas[start_index]            datas[start_index] = datas[end_index]            datas[end_index] = temp    datas[start_index] = pivot    return start_index复制代码

全部实现

datas1 = [1, 2, 4, 6, 3, 1, 3, 43, 547, 123, 436, 57, 98, 976, 543, 2112, 378988, 7654321, 32]def sort(datas, start_index, end_index):    pivot = datas[start_index]    while start_index < end_index:        while datas[end_index] > pivot and start_index < end_index:            end_index -= 1        while datas[start_index] <= pivot and start_index < end_index:            start_index += 1        if start_index < end_index:            temp = datas[start_index]            datas[start_index] = datas[end_index]            datas[end_index] = temp    datas[start_index] = pivot    return start_indexdef quicSort(datas, start_index, end_index):    if start_index < end_index:        mid_index = sort(datas, start_index, end_index)        quicSort(datas, start_index, mid_index - 1)        quicSort(datas, mid_index + 1, end_index)quicSort(datas1, 0, len(datas1) - 1)print(datas1)复制代码