归并排序和快速排序用的都是分治的思想,用递归的编程技巧来实现.咱们先来看归并排序.
归并排序
归并排序的核心思想就是,如果要排序一个数组,我们先从中间把数组分成两部分,分别对两部分排序,然后把排好序的两部分再合并.
归并排序的代码:
merge(A[p...r], A[p...q], A[q+1...r]) {
var i := p，j := q+1，k := 0 // 初始化变量 i, j, k
var tmp := new array[0...r-p] // 申请一个大小跟 A[p...r] 一样的临时数组
while i<=q AND j<=r do {
if A[i] <= A[j] {
tmp[k++] = A[i++] // i++ 等于 i:=i+1
} else {
tmp[k++] = A[j++]
}
}
// 判断哪个子数组中有剩余的数据
var start := i，end := q
if j<=r then start := j, end:=r
// 将剩余的数据拷贝到临时数组 tmp
while start <= end do {
tmp[k++] = A[start++]
}
// 将 tmp 中的数组拷贝回 A[p...r]
for i:=0 to r-p do {
A[p+i] = tmp[i]
}
}
归并排序的性能分析:
1,归并排序是稳定的排序算法
2.归并排序的时间复杂度非常稳定,不管是最好情况,还是最坏情况,平均情况,时间复杂度都是O(nlogn)
3.归并排序的空间复杂度是O(n)
快速排序
快速排序的思想:如果要排序数组中下标从p到r的一组数据,我们选择p到r中的任意一点数据作为pivot(分区点).我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot的
实现代码:
// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
如果这样实现的话,空间复杂度就不是O(1),那么快排就不是原地排序算法了,如果让他是原地排序,可以这样.
partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return I
归并排序和快速排序的区别
1,快排是原地,不稳定的排序算法,时间复杂度为O(nlogn)
