【数据结构和算法实践-排序-总结】
| 排序算法 | 原理 | 时间复杂度 | 空间复杂度 | 稳定性 | 备注 |
|---|---|---|---|---|---|
| 冒泡排序 | 通过重复遍历要排序的数列，比较相邻元素的值，若发现顺序错误则交换它们的位置，直到没有需要交换的元素为止，表示数列已经排序完成。 | 平均和最坏情况：O(n^2) 最好情况：O(n)（已排序） | O(1) | 稳定 | 简单的排序算法，适用于小规模数据。 |
| 选择排序 | 遍历数组，每次从未排序的部分找到最小（或最大）的元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。 | 平均、最好和最坏情况：O(n^2) | O(1) | 不稳定 | 易于实现，但效率较低。 |
| 插入排序 | 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。 | 平均和最坏情况：O(n^2) 最好情况：O(n)（已排序） | O(1) | 稳定 | 适用于部分有序的数据集。 |
| 希尔排序 | 是插入排序的一种更高效的改进版本。希尔排序通过将原来要排序的数列分割成几个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 | 平均时间复杂度依赖于增量序列的选择，最坏情况：O(n^2) | O(1) | 不稳定 | 是一种分组插入方法。 |
| 归并排序 | 采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 | 平均、最好和最坏情况：O(nlogn) | O(n) | 稳定 | 需要额外的存储空间来合并数组。 |
| 快速排序 | 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 | 平均情况：O(nlogn) 最坏情况：O(n^2)（已排序或逆序） | O(logn)（递归栈空间，最好情况） O(n)（最坏情况） | 不稳定 | 实际应用中非常高效的排序算法。 |
| 堆排序 | 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 | 平均、最好和最坏情况：O(nlogn) | O(1) | 不稳定 | 原地排序算法，不需要额外的存储空间。 |
| 计数排序 | 是一种非比较型整数排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 | O(n+k)，其中k是整数的范围 | O(k) | 稳定 | 适用于一定范围内的整数排序。 |
| 桶排序 | 是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。 | 平均时间复杂度依赖于数据的分布和桶的数量，最好情况：O(n+k)，最坏情况：O(n^2)（极端不均匀分布） | O(n+k)（桶和内部排序空间） | 稳定（桶内排序稳定） | 适用于数据分布均匀的情况。 |
| 基数排序 | 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表示字符串（如日期或电话号码可以按位比较），所以基数排序也不是只能使用于整数。 | O(d(n+k))，其中d是最大数字的位数，k是数字的范围 | O(n+k)（计数数组或桶） | 稳定 | 适用于整数排序，且数字位数不宜过长。 |
备注
- 稳定性：如果两个相等的元素在排序前后的相对位置不变，则排序算法是稳定的；否则，排序算法是不稳定的。
- 时间复杂度和空间复杂度：这些复杂度通常基于平均情况、最好情况和最坏情况来讨论。实际性能可能因具体实现和输入数据的特性而有所不同。
- 引用来源：上述描述主要基于算法的基本概念和原理，同时参考了如百度百科等权威来源的描述。