python实现快速排序¶

快速排序的原理和归并排序很像，通过把大的序列不断一分为二，分而治之，实现高效排序。

快排的分而治之的思路¶

接下来说人话，假设有一个数组，由n个数字构成，我们希望它按从小到大的顺序排列。快排的做法是：

1. 在给定数组中任选一个数X，比X小的排到X前面，比X大的排到X后面。
2. 将数组分成两块，X前面的假设叫数组A，X后面的假设叫数组B。
3. 对数组A、数组B分别进行快排（递归操作），那么，[A-X-B]序列就是一个从小到大排序的序列了。

简单的实现¶

接下来是代码，注意，为了方便理解，下面的代码牺牲了性能。

def quick_sort_easy_to_understand(arr):
    size = len(arr)
    # 递归的退出条件是，数组只有1个元素，1个元素的数组有什么好排序的呢？
    if size <= 1:
        return arr
    # 任选一个基准数X，这里取第一个，其实选哪个都可以
    base = arr[0]
    # 元素都比基准数小的数组
    arr_low = []
    # 元素都比基准数大的数组
    arr_high = []
    for i in range(1, size):
        value = arr[i]
        # 小的放第一个数组，大的放第二个数组
        if value <= base:
            arr_low.append(value)
        else:
            arr_high.append(value)
    return quick_sort_easy_to_understand(arr_low) + [base] + quick_sort_easy_to_understand(arr_high)

高效的实现¶

上面的代码完全可以正常排序，但是，效率不高，原因是，每次递归，都要动态创建数组（arr_low、arr_high以及return的数组），也就是说，我们的排序并不是在原数组上进行的，存在空间的浪费自不必说，数组的创建、合并也很耗时。

以下代码做了改进，通过直接在原数组上交换元素实现排序。

def quick_sort_smart(arr, start, end):
    # 新函数引入了参数start、end，因为我们所有的操作都是在原始数组上进行的，
    # 只能通过start、end两个下标来确定子数组的范围
    if start >= end:
        return
    # 我们取最后一个元素作为基准数，这样做的好处是，下面的for循环中，最后一轮迭代完成时，pivot刚好指向base值。
    base = arr[end]
    # middle用于记录基准数的下标，必须保证“middle及其之前位置的元素都不大于基准数”
    # middle初始为-1
    middle = start - 1
    for i in range(start, end + 1):
        if arr[i] <= base:
            # 一旦发现比基准数小的元素，就把middle后移（腾位置），并把发现的元素和middle上的元素交换
            middle += 1
            arr[i], arr[middle] = arr[middle], arr[i]
    # 一趟循环下来，“middle及其之前位置的元素都不大于基准数”得到了保证。
    # 因此，只要middle左边和右边的序列都是从小到大排列的，
    # 那么[middle左边，middle，middle右边]这个整体就是从小大大排列的。
    quick_sort_smart(arr, start, middle - 1)
    quick_sort_smart(arr, middle + 1, end)
    return arr

验证效果¶

arr = [4, 2, 1, 6, 3, 7, 5]
print quick_sort_smart(arr, 0, len(arr) - 1)

本文为kyleblog.cn原创，转载请注明出处：https://www.kyleblog.cn/posts/python_qsort