排序(下):归并排序、快速排序

  • A+
所属分类:算法与数据结构

归并排序

思想

分而治之。递归处理。将数据分为前后两个部分。保证这两部分分别是有序的,然后再有序地合并这两部分。从下到上。

递归公式:

mergeSort(p...r) = merge(mergeSort(p...q), mergeSort(q...r))

终止条件:

p>=r,不用再继续分解。

代码

分析

空间复杂度。每次运行merge函数都需O(n)额外空间,运行完后此空间释放。因此空间复杂度为O(n)。

时间复杂度。最好、最坏、平均时间复杂度都为O(nlogn)。因为用到递归,其分析时间复杂度也可用递归完成。

T(n) = 2*T(n/2) + K

迭代深度为logn,需要logn次merge,所以时间复杂度为O(nlogn)。

稳定性:关键在merge函数,稳定的。

快速排序

思想

从上到下。选一个分界点,将数据分为左右两部分,保证左边部分小于分界点,右边部分大于分界点。将这两部分(不包括分界点)再递归分界下去。

递推公式:

quickSort(p...r) = quickSort(p...q-1) + quickSort(q+1...r)

终止条件:

p>=r,不用再继续分解。

代码

分析

空间复杂度:O(1)

时间复杂度:最好、平均为O(nlogn),最坏为O(n^2)。如果正好将数组分成大小接近相等的两个小区间,即分区极其均衡,时间复杂度为O(nlogn)。如果分区极端不均衡,如1,2,3,4,5,则需要进行n次分区操作,每次分区平均要扫描n/2个元素,时间复杂度退化为O(n^2)。

稳定性:如果两个相等的值一个是pivot,则有可能互换。快速排序是不稳定的。

其他排序(下):归并排序、快速排序 这就是二分法的应用,比简单地从第一个开始比较要快很多。

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: