各种排序的时间复杂度和空间复杂度
时间: 2024-01-02 09:22:00 浏览: 83
多种排序时间复杂度的比较
以下是各种排序算法的时间复杂度和空间复杂度:
1. 冒泡排序:
- 时间复杂度:最好情况下,数组已经有序,时间复杂度为O(n);最坏情况下,数组逆序,时间复杂度为O(n^2);平均情况下,时间复杂度为O(n^2)。
- 空间复杂度:O(1)。
2. 选择排序:
- 时间复杂度:无论数组是否有序,时间复杂度都为O(n^2)。
- 空间复杂度:O(1)。
3. 插入排序:
- 时间复杂度:最好情况下,数组已经有序,时间复杂度为O(n);最坏情况下,数组逆序,时间复杂度为O(n^2);平均情况下,时间复杂度为O(n^2)。
- 空间复杂度:O(1)。
4. 快速排序:
- 时间复杂度:最好情况下,每次划分都能均匀地将数组分成两部分,时间复杂度为O(nlogn);最坏情况下,每次划分都只能将数组分成一部分和剩余的元素,时间复杂度为O(n^2);平均情况下,时间复杂度为O(nlogn)。
- 空间复杂度:最好情况下,递归调用的栈空间为O(logn);最坏情况下,递归调用的栈空间为O(n)。
5. 归并排序:
- 时间复杂度:归并排序的时间复杂度为O(nlogn)。
- 空间复杂度:归并排序的空间复杂度为O(n)。
6. 基数排序:
- 时间复杂度:基数排序的时间复杂度为O(d(n+r)),其中d为关键码的位数,r为关键码的取值范围。
- 空间复杂度:基数排序的空间复杂度为O(n)。
阅读全文