快速排序从程式上看起来和归并排序特别像，都采取了递归分治的思想，将数据逐步分解。快排首先在序列中选定某一个枢轴（pivot），然后将除枢轴位置的数据与枢轴数据比较，大于的放在右边，小于的放在左边，然后分两边再次递归，直到递归数据个数趋为1，这样数据就排好序了。
- 稳定性：快排不是稳定的排序算法，快排的插入与交换取决于枢轴点的选取，比如说8，6，8，1，5，3这个数组，在第一轮的分区中第一个8就会排到第二个8后面，所以快排不是稳定的排序算法
2.空间复杂度：单单通过算法就能看出并没有像归并那样额外申请内存，仅仅只需要在同个数组内完成，因此为O(1)，属于原地排序算法
3.时间复杂度：因为采用了与归并类似的思想，假设数组每次都能完美拆分为两个对半的，这样的时间复杂度即为O(nlogN)，但是枢轴值的选取倘若很极端，极端到每次的选择要么为最大值，要么为最小值，就相当于冒泡排序那样，就会退化成为O(n²）
- 在上面的时间复杂度分析中，可以看出快排的时间复杂度并不稳定，造成这个结果的原因就是主要因为枢轴值的选择，因此对枢轴值选择的优化颇为重要，比如说三数取中，九数取中，尽量扩大采样数据的范围，这样才能优化枢轴值的选择
- 当我们在递归到某个深度的时候，数据规模较小，此时插入排序的性能可能比快排的性能还要好，则可以设置一个阈值，切换排序算法的实现，这样也能提高效率
-
归并直接首先直接二分分区，落井下石到最底层才开始执行合并排序的操作，归并由下到上
快排首先会确定位置再分区，然后递归，随着中间位置点的越分越多，数据的序列性表现的越明显，快排由上到下 -
归并的空间复杂度比快排高，尤其在大量数据面前，归并的内存占用相当可怕
-
快排的时间复杂度并不如归并的稳定
- 以上就是本篇文章【快速排序详解：原理、优化与归并比较】的全部内容了，欢迎阅览 ！ 文章地址：http://ww.kub2b.com/tnews/4965.html 栏目首页 相关文章 动态 同类文章 热门文章 网站地图 返回首页 企库往资讯移动站 http://ww.kub2b.com/mobile/ , 查看更多