> # 相关排序 | 排序算法 | 最坏情况时间复杂度 | 平均情况时间复杂度 | 最好情况时间复杂度 | 空间复杂度 | 稳定性 | | --- | --- | --- | --- | --- | --- | | 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 | | 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | | 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 | | 快速排序 | O(n^2) | O(nlogn) | O(nlogn) | O(nlog) | 不稳定 | | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | | 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 | | 桶排序 | O(n^2) | O(n + k) | O(n + k) | O(n + k) | 稳定 | | 基数排序 | O(n \* k) | O(n \* k) | O(n \* k) | O(n + k) | 稳定 | - O(n^2) > O(n * k) > O(nlogn) > O(n + k) > O(n) > O(k) > O(1) 1. **最坏情况时间复杂度**：这是指在给定算法的所有可能输入中，所需执行步骤的最大数量。最坏情况时间复杂度给出了算法在最不利情况下的性能。例如，对于快速排序，最坏情况时间复杂度是O(n^2)，这发生在每次选择的基准元素都是最大或最小元素的情况下。 2. **平均情况时间复杂度**：这是指在给定算法的所有可能输入中，所需执行步骤的平均数量。平均情况时间复杂度考虑了算法在各种情况下的性能，并给出了一个对算法性能的更全面的评估。例如，对于快速排序，平均情况时间复杂度是O(nlogn)，这是因为在大多数情况下，分区的过程能够将数组均匀地分割成两部分。 3. **最好情况时间复杂度**：这是指在给定算法的所有可能输入中，所需执行步骤的最小数量。最好情况时间复杂度描述了算法在最理想情况下的性能。例如，对于插入排序，最好情况时间复杂度是O(n)，这发生在数组已经是部分有序的情况下。 4. **空间复杂度**：这是指算法在执行时所需的额外空间或内存量。空间复杂度考虑了算法所使用的额外空间与输入规模之间的关系。例如，对于归并排序，空间复杂度是O(n)，因为它需要一个与原始数组大小相同的辅助数组来合并子数组。 5. **稳定性**：这是指算法在排序过程中能否保持相等元素的相对顺序不变。如果排序算法能够保持相等元素的相对顺序不变，则称该算法是稳定的；否则称为不稳定的。例如，如果对一组学生成绩按照姓名进行排序，排序后相同成绩的学生应该按照他们原始的顺序排列，这就需要一个稳定的排序算法。插入排序和归并排序是稳定的排序算法，而快速排序和堆排序是不稳定的排序算法。 > 选择 1. **数据规模**：对于小规模数据集，简单的排序算法如冒泡排序、选择排序、插入排序可能更适合，而对于大规模数据集，则更复杂的算法如快速排序、归并排序、堆排序更高效。 2. **数据分布**：如果数据分布近乎有序，插入排序可能更快；如果数据分布随机，快速排序可能更适合。 3. **内存限制**：某些排序算法需要额外的内存空间，如归并排序的递归实现，而某些算法是原地排序算法，如快速排序、堆排序。 4. **稳定性**：某些情况下，需要保持相等元素的相对顺序不变，这时稳定排序算法如归并排序、计数排序更适合。 5. **时间限制**：对于需要更快排序的场景，可以考虑时间复杂度较低的算法，如快速排序、堆排序 > # 相关阅读 [十大经典排序算法（动图演示）](https://www.cnblogs.com/onepixel/p/7674659.html)