归并排序与快速排序是两种有实际应用的排序算法,它们有一些共同的特点,整体思路上也比较相近。
快速排序
相对来说,快速排序可能是应用的最为广泛的一种算法,它流行的原因是实现简单,适用于各种不同的输入数据且在一般的应用中比其他排序算法都要快的多。快速排序是原地排序(只需要一个很小的辅助栈)而且所需时间跟NlgN成正比。
实现步骤:
选择一个基准元素,通常选择第一个元素或者最后一个元素
通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值均比基准值大
此时基准元素在其排好序后的正确位置
然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。
归并排序
归并排序是典型的分治法排序,将待排序元素拆成多个分组,分组内部进行排序,然后分组进行合并,最终合并成完整的数组。
比较快速排序和归并排序的速度
命令:
结果:
对比归并排序与快速排序
都用了分治的思想。相比选择排序和冒泡排序,归并排序与快速排序使用了切分而不是直接遍历,这有效减少了交换次数。
归并排序是先切分、后排序,过程可以描述为:切分、切分、切分……排序、排序、排序……
快速排序是分区、排序交替进行,过程可以描述为:分区、排序、分区、排序……
上两条所说的“排序”,在归并排序与快速排序中并非同样的操作,归并排序中的操作是将两个数组合并为一(归并操作),而快速排序中的操作是交换。
本文标题:“归并排序”与“快速排序”??简单对比两个算法的实现
本文链接:https://blog.quwenai.cn/post/351.html
版权声明:本文不使用任何协议授权,您可以任何形式自由转载或使用。















还没有评论,来说两句吧...