Python 实现十大经典排序算法
内容提要
本文介绍了十大经典排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。每种算法的原理、步骤、代码实现及优缺点均有详细说明，适用于不同的排序需求。
延伸解读
比较类与非比较类排序的本质区别
文章指出，比较类排序通过比较元素决定次序，时间复杂度不能突破O(nlogn)；非比较类排序则不依赖比较，可以线性时间运行。常见的非比较类排序有计数排序、桶排序和基数排序。理解这一区别有助于在特定场景下选择更高效的算法，例如当数据范围有限且为整数时，非比较类排序可能更快。
稳定性：相等元素的相对顺序
稳定性指排序后相等键值的顺序是否与排序前相同。文章表格显示，冒泡、插入、归并、计数、桶、基数排序是稳定的，而选择、希尔、快速、堆排序不稳定。若排序后仍需保持原始顺序（如按多个字段排序），应优先选择稳定算法，否则可能需额外处理。
时间与空间复杂度的权衡
不同排序算法在时间和空间上各有取舍。例如，冒泡、选择、插入排序空间复杂度为O(1)，但平均时间复杂度为O(n²)；归并排序时间复杂度为O(nlogn)，但需要O(n)额外空间；计数、桶、基数排序虽能线性时间运行，但需要额外空间且受数据范围限制。选择时需根据数据规模和内存条件权衡。
算法选择没有唯一最优解
文章强调，每种排序算法都有优缺点，适合不同环境，很难说哪一种最好。实际应用中，需考虑数据规模、数据分布、稳定性要求、内存限制等因素。例如，小规模数据可用插入排序；大规模数据常用快速排序或归并排序；特定整数范围可考虑计数排序。理解原理有助于灵活选用。
Q&A
Python中有哪些经典的排序算法？
经典的排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。
冒泡排序的基本原理是什么？
冒泡排序通过重复比较相邻元素并交换它们的位置，将最大的元素逐步“冒泡”到序列的末尾，直到整个序列有序。
快速排序的工作原理是什么？
快速排序通过选择一个基准值，将数组分为两部分，左边的元素都小于基准值，右边的元素都大于基准值，然后递归地对这两部分进行排序。
计数排序的时间复杂度是多少？
计数排序的时间复杂度为O(n+k)，其中n是待排序元素的数量，k是元素值的范围。
什么是稳定排序，哪些排序算法是稳定的？
稳定排序是指相等元素在排序后仍保持原有相对顺序的排序算法。冒泡排序、插入排序、归并排序和计数排序是稳定的。
如何选择合适的排序算法？
选择排序算法时应考虑数据规模、数据特性（如是否基本有序）和对时间复杂度及空间复杂度的要求。
