排序方法_排序
冒泡排序
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
时间复杂度：O(n^2)
空间复杂度：O(1)
选择排序
选择排序的主要思想是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
时间复杂度：O(n^2)
空间复杂度：O(1)
插入排序
插入排序的思想是每次将一个待排序的记录，按其关键字大小插入到前面已经排序的序列中的适当位置，直到全部记录插入完成为止。
时间复杂度：O(n^2)
空间复杂度：O(1)
快速排序
快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。
时间复杂度：O(nlogn)
空间复杂度：O(logn)
归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
时间复杂度：O(nlogn)
空间复杂度：O(n)
堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进，堆的定义如下：具有n个元素的序列（h1,h2,…，hn),当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=h2i+1）(i=1,2,…，n/2)时称之为堆。
时间复杂度：O(nlogn)
空间复杂度：O(1)
下面是一个简单的介绍，包含了常见的排序方法及其特点：
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
| 冒泡排序 | 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 log n) | O(n^2) | O(n log n) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 希尔排序 | O(n log^2 n) | O(n^2) | O(n) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n + k) | 稳定 |
| 桶排序 | O(n + k) | O(n^2) | O(n) | O(n + k) | 稳定 |
注：
n 为要排序的元素个数。
k 为输入范围的大小，例如计数排序中k为最大值与最小值的差。
稳定性指的是相等的元素在排序后是否保持原来的顺序。
时间复杂度和空间复杂度是针对排序算法的执行效率的度量。
原创文章，作者：未希，如若转载，请注明出处：https://www.kdun.com/ask/704180.html
微信扫一扫