有几种排序算法并说明他们的复杂度
时间: 2023-06-17 12:08:27 浏览: 78
常见的排序算法有以下几种:
1. 冒泡排序(Bubble Sort):
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:稳定
2. 插入排序(Insertion Sort):
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:稳定
3. 选择排序(Selection Sort):
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:不稳定
4. 希尔排序(Shell Sort):
时间复杂度:O(nlogn) ~ O(n^2)
空间复杂度:O(1)
稳定性:不稳定
5. 快速排序(Quick Sort):
时间复杂度:O(nlogn) ~ O(n^2)
空间复杂度:O(logn) ~ O(n)
稳定性:不稳定
6. 归并排序(Merge Sort):
时间复杂度:O(nlogn)
空间复杂度:O(n)
稳定性:稳定
7. 堆排序(Heap Sort):
时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定
8. 计数排序(Counting Sort):
时间复杂度:O(n+k)
空间复杂度:O(k)
稳定性:稳定
9. 桶排序(Bucket Sort):
时间复杂度:O(n)
空间复杂度:O(n+k)
稳定性:稳定
10. 基数排序(Radix Sort):
时间复杂度:O(d(n+k))
空间复杂度:O(n+k)
稳定性:稳定
其中,n 为数组长度,k 为桶的数量,d 为数字的位数。