目录

归并排序原理归并排序的代码实现归并排序性能分析 快速排序原理快速排序的代码实现快速排序的性能分析 归并排序和快速排序的区别

归并排序原理

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的就是分治思想。 分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

归并排序的代码实现

递推公式： merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件： p >= r 不用再继续分解

伪代码

// 归并排序算法, A是数组，n表示数组大小 merge_sort(A, n) { merge_sort_c(A, 0, n-1) } // 递归调用函数 merge_sort_c(A, p, r) { // 递归终止条件 if p >= r then return // 取p到r之间的中间位置q q = (p+r) / 2 // 分治递归 merge_sort_c(A, p, q) merge_sort_c(A, q+1, r) // 将A[p...q]和A[q+1...r]合并为A[p...r] merge(A[p...r], A[p...q], A[q+1...r]) }

下图演示的是一个merge的过程 merge() 合并函数如果借助哨兵，代码就会简洁很多，代码如何实现？？？

归并排序性能分析

稳定性排序时间复杂度为$N(n\log n)$空间复杂度为$O(n)$。归并排序不是原地排序，在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

快速排序原理

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

快速排序的代码实现

递推公式： quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r) 终止条件： p >= r

伪代码

// 快速排序，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) }

将小于 pivot 的元素都拷贝到临时数组 X，将大于 pivot 的元素都拷贝到临时数组 Y，最后再将数组 X 和数组 Y 中数据顺序拷贝到 A[p…r]。 由上图可以看到分区好函数需要临时申请空间，所以不是原地排序算法，要想成为原地排序，那么分区操作就要在原地完成。

原地分区伪代码的实现

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

快速排序的性能分析

稳定性排序时间复杂度为$N(n\log n)$空间复杂度为$O(n)$。归并排序不是原地排序，在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

归并排序和快速排序的区别

可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数， 可以实现原地排序，解决了归并排序占用太多内存的问题。