各个排序算法时间复杂度和空间复杂度
时间: 2023-10-30 15:06:22 浏览: 322
引用提到了归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。而引用中提到,当算法的空间复杂度为常量时,即不随数据量n的增加而改变,可以表示为O(1)。另外,引用中介绍了基数排序的时间复杂度为O(d(nr)),其中d为关键码的位数,r为关键码的取值范围。
接下来是各个排序算法的时间复杂度和空间复杂度的总结:
1. 冒泡排序:时间复杂度为O(n^2),空间复杂度为O(1)。
2. 选择排序:时间复杂度为O(n^2),空间复杂度为O(1)。
3. 插入排序:时间复杂度为O(n^2),空间复杂度为O(1)。
4. 希尔排序:时间复杂度为O(nlogn),空间复杂度为O(1)。
5. 归并排序:时间复杂度为O(nlogn),空间复杂度为O(n)。
6. 快速排序:时间复杂度为O(nlogn),空间复杂度为O(logn)。
7. 堆排序:时间复杂度为O(nlogn),空间复杂度为O(1)。
8. 计数排序:时间复杂度为O(n+r),空间复杂度为O(n+r),其中r为关键码的取值范围。
9. 桶排序:时间复杂度为O(n+k),空间复杂度为O(n+k),其中k为桶的个数。
10. 基数排序:时间复杂度为O(d(nr)),空间复杂度为O(nr),其中d为关键码的位数,r为关键码的取值范围。
阅读全文
相关推荐














