Python中都有哪些常见的排序算法的具体实现方法？

本文共计1564个文字，预计阅读时间需要7分钟。

排序分为两类，比较类排序和非比较类排序。比较类排序通过比较元素来确定它们的相对顺序，如快速排序和归并排序，这类排序的时间复杂度通常不能突破O(nlogn)。非比较类排序则不依赖于比较操作，例如计数排序和基数排序，它们可以在特定条件下突破O(nlogn)的时间复杂度界限。缺点是，非比较类排序通常需要额外的空间或对数据有特定的要求。

排序分为两类，比较类排序和非比较类排序，比较类排序通过比较来决定元素间的相对次序，其时间复杂度不能突破O(nlogn)；非比较类排序可以突破基于比较排序的时间下界，缺点就是一般只能用于整型相关的数据类型，需要辅助的额外空间。

要求能够手写时间复杂度位O(nlogn)的排序算法：快速排序、归并排序、堆排序

1.冒泡排序

思想：相邻的两个数字进行比较，大的向下沉，最后一个元素是最大的。列表右边先有序。

时间复杂度$O(n^2)$，原地排序，稳定的

def bubble_sort(li:list): for i in range(len(li)-1): for j in range(i + 1, len(li)): if li[i] > li[j]: li[i], li[j] = li[j], li[i]

2.选择排序

思想：首先找到最小元素，放到排序序列的起始位置，然后再从剩余元素中继续寻找最小元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。列表左边先有序。