快速排序_python 详细理解

快速排序（python）

思路：

在数组中随机选择一个元素，以其为基准数，将比它小的值放到它的左边，比它大的值放到它的右边。

步骤：

（1）右指针向左移动，当遇到 <= 基准数 的元素，则停止

（2）左指针向右移动，当遇到 >= 基准数 的元素，则停止

（3）将两指针所指的位置的 元素 进行交换

（4）重复上面的步骤，直到左右指针重合

（5）将基准数与左右指针重合位置的 元素进行交换

举例说明：

我们对下面10个元素进行快速排序： [ 5 3 4 7 9 1 2 6 8 10 ]

• 我们选取 5 为基准数，然后放置指针。

	5	3	4	7	9	1	2	6	8	10
左指针	☆										右指针

• 一般我们从右指针开始，以 元素5 为基准数 右指针向左寻找 <= 5 的元素，到了元素 2 的位置就停下来了；左指针向右寻找 >= 5 的元素 到了元素 7 的位置就停止下来了。

	5	3	4	7	9	1	2	6	8	10
	☆						????				右指针
左指针				????

• 将两指针的所指的元素进行位置交换我们得到：

5	3	4	2	9	1	7	6	8	10

• 继续以 元素5 为基准数，我们重述上述步骤 右指针向左寻找 <= 5 的元素 到了元素 1 的位置就停下来了，左指针向右寻找 >= 5 的元素 到了元素 9 的位置就停止下来了。

	5	3	4	2	9	1	7	6	8	10
	☆					????					右指针
左指针					????

• 将两指针的所指的元素进行位置交换我们得到：

5	3	4	2	1	9	7	6	8	10

• 继续以 元素5 为基准数，我们重述上述步骤 右指针向左寻找 <= 5 的元素 到了元素 1 的位置就停下来了，左指针向右寻找 >= 5 的元素 到了元素 9 的位置，我们发现在 元素1 的时候右指针 和 左指针重合了。

	5	3	4	2	1	9	7	6	8	10
	☆				????						右指针
左指针					????????	????

• 此时我们将 基准数 和 指针重合 的所在位置的的值进行交换得到：

1	3	4	2	5	9	7	6	8	10
				☆

---

• 此时 元素5 已经归位了，我们在以 元素5 为分界点拆分为两个数组，左边为 [ 1 3 4 2 ]， 右边为 [ 9 7 6 8 10 ]:

1	3	4	2		5		9	7	6	8	10
					☆
					归位

• 现在我们处理 元素5 左边的元素 即 [ 1 3 4 2]

• 以 元素1 为基准数 放置指针右指针向左寻找 <= 1 的元素，到了元素 1 的位置就停下来了；左指针向右寻找 >= 1 的元素 到了元素 1 的位置就停止下来了，我们发现 右指针 和 左指针重合了。

	1	3	4	2		5		9	7	6	8	10
	☆					☆
	????				右指针	归位
左指针	????
	归位

• 此时 元素1 已经归位，我们在处理 [ 3 4 2]
• 以 元素3 为基准数 放置指针,右指针向左寻找 <= 3 的元素，到了元素 2 的位置就停下来了；左指针向右寻找 >= 3 的元素 到了 元素 4 的位置就停止下来了。

1		3	4	2		5		9	7	6	8	10
☆		☆		????	右指针	☆
归位	左指针		????			归位

• 将两指针的所指的 元素进行位置交换我们得到：

1		3	2	4		5		9	7	6	8	10
☆						☆
归位						归位

• 以 元素3 为基准数 放置指针,右指针向左寻找 <= 3 的元素，到了元素 2 的位置就停下来了；左指针向右寻找 >= 3 的元素 到了元素 4 的位置就停下来了，但我们发现在 元素2 的时候右指针 和 左指针重合了。

1		3	2	4		5		9	7	6	8	10
☆		☆	????		右指针	☆
归位	左指针		????????	????		归位

• 此时我们将 基准数 和 指针重合 的所在位置的的值进行交换得到：

1		2	3	4		5		9	7	6	8	10
☆			☆			☆
归位			归位			归位

• 我们在以 元素2 为基准数，发现只有一位，因此 元素 2 以归位 得到：

1		2	3	4		5		9	7	6	8	10
☆		☆	☆			☆
归位		归位	归位			归位

• 我们在以 元素4 为基准数，发现只有一位，因此 元素 4 以归位 得到：

1		2	3	4		5		9	7	6	8	10
☆		☆	☆	☆		☆
归位		归位	归位	归位		归位

• 同理，右边的 [ 9 7 6 8 10 ] 重复左边的步骤。
• 最终我们会得到：

1	2	3	4	5	6	7	8	9	10

代码实现如下：

# 快速排序
def quick_sort(array, left, right):
    if left >= right:
        return array
    low = left
    high = right
    pivot = array[left]

    while low != high:
        while low < high and array[high] >= pivot:
            high -= 1
        array[low] = array[high]

        while low < high and array[low] <= pivot:
            low += 1
        array[high] = array[low]

        array[low] = pivot
        quick_sort(array, left, low - 1)
        quick_sort(array, low + 1, right)
    return array


li = [5, 3, 4, 7, 9, 1, 2, 6, 8, 10]
quick_sort(li, 0, len(li) - 1)
print(li)

==》[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]