快速排序

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

快速排序

  • 採用 分而治之 原則
  • 由多種 程式語言 實作
  • 分割 技巧
    • 樞紐（pivot）
    • 比樞紐小的項目 -> 左側
    • 比樞紐大的項目 -> 右側
  • 左側元素以遞迴排序
  • 右側元素以遞迴排序
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。

Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。

  • Hoare 分割法
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第二個元素，右指標指向最後一個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第三個元素，右指標指向最後一個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第三個元素，右指標指向第五個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第三個元素，右指標指向第五個元素。兩個箭頭表示將交換第三與第五個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第三個元素，右指標指向第五個元素。第三與第五個元素已交換。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第四個元素，右指標指向第五個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第四個元素，右指標指向第四個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第四個元素，右指標指向第三個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素以藍色標示。有兩個指標。左指標指向第四個元素，右指標指向第三個元素。兩個箭頭表示將交換第一與第三個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第三個元素以藍色標示。第一與第三個元素已交換。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第三個元素以綠色標示。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第三個元素為綠色，前兩個元素為橘色，代表清單左半部。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素藍色，第二個橘色，第三個綠色。左右指標皆指向第二個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素藍色，第二個橘色，第三個綠色。左右指標皆指向第二個元素。兩個箭頭表示將交換第一與第二個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素藍色，第二個橘色，第三個綠色。左右指標皆指向第二個元素。第一與第二個元素已交換。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一個元素橘色，第二與第三個元素綠色。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三個元素為綠色。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三個元素為綠色。清單右半部為橘色。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三個元素為綠色。右半部的第一個元素為藍色。左指標指向右半部的第二個元素，右指標指向右半部的最後一個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三個元素為綠色。右半部的第一個元素為藍色。左右指標皆指向右半部的第二個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三個元素為綠色。右半部的第一個元素為藍色。左指標指向右半部第一個元素，右指標指向右半部第二個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三、第四個元素為綠色，第五與第六個元素為橘色。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三、第四個元素為綠色。某元素為藍色。左右指標指向最後一個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三、第四個元素為綠色。某元素為藍色。左右指標指向最後一個元素。兩個箭頭表示將交換第五與第六個元素。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。第一、第二、第三、第四個元素為綠色。某元素為藍色。左右指標指向最後一個元素。第五與第六個元素已交換。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實際運作

未排序數字清單的示意圖。所有元素皆為綠色，表示已排序完成。

  • Hoare 分割法
    • 移動左指標，直到遇到比樞紐大的值
    • 移動右指標，直到遇到比樞紐小的值
Data Structures and Algorithms in Python

快速排序：實作

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)
Data Structures and Algorithms in Python

快速排序：實作

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
Data Structures and Algorithms in Python

快速排序：實作

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]
Data Structures and Algorithms in Python

快速排序：複雜度

  • 最差情況：$O(n^2)$
  • 效率極高！
    • 平均情況：$\Theta(n\log{}n)$
    • 最佳情況：$\Omega(n\log{}n)$
  • 空間複雜度：$O(n\log{}n)$
Data Structures and Algorithms in Python

一起來練習吧！

Data Structures and Algorithms in Python

Preparing Video For Download...