Python排序算法

21. 排序算法

文章目錄

• • 21. 排序算法
  • • 21.1 算法穩定性
    • 21.2 分類
    • • 21.2.1 穩定的排序算法
      • 21.2.2 不穩定的排序算法
    • 21.3 冒泡排序
    • • 21.3.1 代碼實現
      • 21.3.2 時間復雜度
    • 21.4 選擇排序
    • • 21.4.1 代碼實現
      • 21.4.2 時間復雜度
    • 21.5 插入排序
    • • 21.5.1 代碼實現
      • 21.5.2 時間復雜度
    • 21.6 快速排序
    • • 21.6.1 代碼實現
      • 21.6.2 時間復雜度

21.1 算法穩定性

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄,若經過排序，這些記錄的相對次序保持不變,則稱這種排序算法是穩定的，否則稱為不穩定的

21.2 分類

21.2.1 穩定的排序算法

• 冒泡排序
• 插入排序
• 歸並排序
• 基數排序

21.2.2 不穩定的排序算法

• 選擇排序
• 快速排序
• 希爾排序
• 堆排序

21.3 冒泡排序

21.3.1 代碼實現

21.3.2 時間復雜度

• 最差

  • O(n2)

• 最優

  • O(n)

21.4 選擇排序

21.4.1 代碼實現

21.4.2 時間復雜度

• 最優

  • O(n2)

• 最差

  • O(n2)

21.5 插入排序

21.5.1 代碼實現

21.5.2 時間復雜度

• 最優

  • O(n)

• 最壞

  • O(n2)

21.6 快速排序

21.6.1 代碼實現

21.6.2 時間復雜度

• 最優

  • O(nlogn)

• 最壞

  • O(n2)