快速排序

Python 中的数据结构与算法

Miriam Antona

Software engineer

快速排序

遵循分而治之思想
被多种编程语言实现
分区技术
- 枢轴
- 小于枢轴的元素 -> 左
- 大于枢轴的元素 -> 右
左侧元素将递归排序
右侧元素将递归排序

快速排序 - 演示

一个无序数字列表的示意图。

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。

Hoare 分区

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第二个元素，右指针指向最后一个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第三个元素，右指针指向最后一个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第三个元素，右指针指向第五个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第三个元素，右指针指向第五个元素。有两条箭头表示将交换第三和第五个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第三个元素，右指针指向第五个元素。第三和第五个元素已交换。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第四个元素，右指针指向第五个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第四个元素，右指针指向第四个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第四个元素，右指针指向第三个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色。有两个指针。左指针指向第四个元素，右指针指向第三个元素。有两条箭头表示将交换第一个和第三个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第三个元素为蓝色。第一个和第三个元素已交换。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第三个元素为绿色。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第三个元素为绿色，前两个元素为橙色，表示列表的左半部分。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色，第二个为橙色，第三个为绿色。左右指针都指向第二个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色，第二个为橙色，第三个为绿色。左右指针都指向第二个元素。有两条箭头表示将交换第一和第二个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为蓝色，第二个为橙色，第三个为绿色。左右指针都指向第二个元素。第一和第二个元素已交换。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一个元素为橙色，第二和第三个为绿色。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三个元素为绿色。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三个元素为绿色。列表右半部分为橙色。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三个元素为绿色。右半部分的第一个元素为蓝色。左指针指向右半部分的第二个元素，右指针指向右半部分的最后一个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三个元素为绿色。右半部分的第一个元素为蓝色。左右指针都指向右半部分的第二个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三个元素为绿色。右半部分的第一个元素为蓝色。左指针指向右半部分的第一个元素，右指针指向右半部分的第二个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三、四个元素为绿色，第五和第六个为橙色。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三、四个元素为绿色。某个元素为蓝色。左右指针都指向最后一个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三、四个元素为绿色。某个元素为蓝色。左右指针都指向最后一个元素。有两条箭头表示将交换第五和第六个元素。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。第一、二、三、四个元素为绿色。某个元素为蓝色。左右指针都指向最后一个元素。第五和第六个元素已交换。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 演示

一个无序数字列表的示意图。所有元素为绿色，表示已排序。

Hoare 分区
- 移动左指针，直到找到大于枢轴的值
- 移动右指针，直到找到小于枢轴的值

快速排序 - 实现

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)

快速排序 - 实现

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer

快速排序 - 实现

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

快速排序 - 复杂度

最坏情况：$O(n^2)$
非常高效！
- 平均情况：$\Theta(n\log{}n)$
- 最好情况：$\Omega(n\log{}n)$
空间复杂度：$O(n\log{}n)$

Ayo berlatih!

Python 中的数据结构与算法