排序算法的时间复杂度和空间复杂度是衡量算法效率的重要指标。了解这些复杂度可以帮助我们选择合适的算法来解决特定问题。
- 时间复杂度
时间复杂度表示算法执行所需的时间与输入数据量的关系。对于排序算法，常见的有：
- 冒泡排序（Bubble Sort）：时间复杂度为O(n^2)，其中n为待排序元素数量。冒泡排序通过重复遍历待排序序列，比较相邻元素并交换顺序，使较大的元素逐渐移到序列的末尾。
- 选择排序（Selection Sort）：时间复杂度为O(n^2)。选择排序每次从未排序部分中找到最小元素，将其放到已排序部分的末尾。
- 插入排序（Insertion Sort）：时间复杂度为O(n^2)。插入排序通过将每个元素逐个插入到已排序部分的合适位置来实现排序。
- 快速排序（Quick Sort）：时间复杂度为O(nlogn)。快速排序采用分治策略，将待排序序列分成两个子序列，分别递归进行排序，最后合并结果。
- 归并排序（Merge Sort）：时间复杂度为O(nlogn)。归并排序将待排序序列分成两个子序列，分别递归进行排序，然后将两个已排序的子序列合并成一个有序序列。
- 空间复杂度
空间复杂度表示算法所需的额外存储空间。对于排序算法，常见的有：
- 冒泡排序（Bubble Sort）：空间复杂度为O(1)。冒泡排序不需要额外的存储空间，只在原数组上进行操作。
- 选择排序（Selection Sort）：空间复杂度为O(1)。选择排序也不需要额外的存储空间。
- 插入排序（Insertion Sort）：空间复杂度为O(1)。插入排序同样在原数组上进行操作，不需要额外的存储空间。
- 快速排序（Quick Sort）：空间复杂度为O(logn)。快速排序需要一个额外的存储空间来保存临时数据，通常为一个辅助数组。
- 归并排序（Merge Sort）：空间复杂度为O(n)。归并排序需要一个额外的存储空间来保存已排序的子序列。