Python排序算法

21. 排序算法

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)