快速排序和归并排序的分析比较
|
快速排序 |
归并排序 |
| 设计思想 |
快速排序算法是在分治算法基础上设计出来的一种排序算法，从待排序序列中任选一个元素x作为哨点，（以按从小到大排序为例）将所有比x大的元素放到哨点右边，将所有比x小的元素放到哨点左边。再将x左右两边的子序列看做两个待排序序列，重复上一步操作，直至子序列都不可再分，整个序列就已有序。 |
采用分治策略， 先递归的把数组划分为两个子数组，一直递归到数组中只有一个元素，然后再调用函数把两个子数组排好序，因为该函数在递归划分数组时会被压入栈，所以这个函数真正的作用是对两个有序的子数组进行排序。 |
| 时间复杂性 |
最好：O(nlogn) 最坏：O(n*n) 平均: O(nlogn) |
最好：O(nlogn) 最坏：O(nlogn) 平均: O(nlogn) |
| 空间复杂性 |
最好：O(logn) 最坏：O(n) 平均: O(logn) |
最好：O(n) 最坏：O(n) 平均: O(n) |
| 稳定性 |
快速排序的时间复杂度和空间复杂度会根据原始数据的排列情况而变化，所以快速排序的时间复杂度和空间复杂度都不是稳定的。 |
时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。虽然递归次数是O(logn)，但每次递归都会释放掉所占的辅助空间，因而空间复杂度是O(n)。 |
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
