基于分治编程思想的归并排序和快速排序
1. 分治
前面讲到的三种排序算法，平均时间复杂度都是 O(n2)，只是适合规模较小的数剧集，接下来要讲的归并排序和快速排序，平均时间复杂度都是 O(nlogn)，它们都用到了分治思想。
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。分治与我们前面提到的递归很像，分治算法一般都是通过递归实现的。
虽然快排和归并排序都采用了分治的思想，但是它们完全不一样。归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，快排的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的但是它是非原地排序算法。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。正因为此，归并排序没有快排应用广泛。
2. 实现
2.1 归并排序
归并排序的核心是将数组从中间分成前后两个部分，然后对前后两个部分分别排序，再将它们合并起来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def merge(a, b, c):
i = j = 0
while i + j < len(c):
if i == len(a) or (j < len(b) and a[i] > b[j]):
c[i + j] = b[j]
j += 1
else:
c[i + j] = a[i]
i += 1
def sort_merge(alist):
if len(alist) <= 1:
return alist
mid = len(alist) // 2
left = alist[:mid]
right = alist[mid:]
sort_merge(left)
sort_merge(right)
merge(left, right, alist)
|
归并排序并不是原地排序算法，原因很简单 merge 函数在合并两个已排序数组时使用了额外的存储空间，其空间复杂度为 O(n)。最好最坏和平均时间复杂度都是 O(nlogn)，在整个比较过程并没有发生数据交换，只要 merge 函数保持元素的相对顺序，归并排序是稳定的排序算法。
2.2 快速排序
快排的算法描述
快排排序由以下 3 个步骤组成:
- 分解: 如果待排序列 S 有至少两个元素，从 S 中选择一个特定的元素 x 作为基准，将 S 中的元素分别放置在 3 个序列中:
- L 存储 S 中小于 x 的元素
- E 存储 S 中等于 x 的元素
- G 存储 S 中大于 x 的元素
- 递归: 递归的排序序列 L 和 G
- 合并: 按照 L,E,G 的顺序将元素放回 S 中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
def sort_quick(S):
n = len(S)
if len(S) <= 1:
return
x = S.first() # 基准 x
L = LinkedQueue()
E = LinkedQueue()
G = LinkedQueue()
# 分解
while not S.empty():
if S.first() < x:
L.enqueue(S.dequeue())
elif S.first() > x:
G.enqueue(S.dequeue())
else:
E.enqueue(S.dequeue())
# 递归
sort_quick(L)
sort_quick(G)
# 合并
while not L.is_empty():
S.enqueue(L.dequeue())
while not E.is_empty():
S.enqueue(E.dequeue())
while not G.is_empty():
S.enqueue(G.dequeue())
|
快排的原地排序
快排的原地排序的核心是选择数组中的一个数据项作为分区点 x，然后遍历数组通过数据交换，使得 x 左边的数据都小于 x，x 右边的数据都大于 x。x 将数组分成了两个区间，然后对这两个区间递归执行此过程直至区间长度为 1 ，完成排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def sort_quick(alist, left, right):
if left >= right:
return alist
l = left + 1
r = right
x = alist[left]
while l <= r:
while l <= r and alist[l] < x:
l += 1
while l <= r and alist[r] > x:
r -= 1
if l <= r:
alist[l], alist[r] = alist[r], alist[l]
alist[left], alist[r] = alist[r], alist[left]
sort_quick(alist, left, r - 1)
sort_quick(alist, r + 1, right)
|
显然这个过程发生了数据交换，但是并没有使用额外的存储空间，所以快排并不是稳定的排序算法，但是原地排序算法。
快排的最好和平均时间复杂度都是O(nlogn)，但是极端情况下，如果数组本身是有序的，并且我们选择最大或者最小(两端)的数据作为分区点，我们需要大约 n 次分区才能完成排序过程。快排的时间复杂度就会退化为 O(n2)。但是退化到 O(n2) 的概率非常小，我们可以通过合理的选择分区点来避免这种情况。
3. 算法
3.1 求无序数组中的第 K 大元素
利用快排的分区思想，我们可以在O(n) 时间复杂度内求无序数组中的第 K 大元素。
我们选择数组区间 A[0…n-1] 的最后一个元素 A[n-1] 作为 pivot，对数组 A[0…n-1] 原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K，那 A[p] 就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间，我们再按照上面的思路递归地在 A[p+1…n-1] 这个区间内查找。同理，如果 K<p+1，那我们就在 A[0…p-1] 区间查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def quick_select(S, left, right, k):
r = right
l = left + 1
pivot = S[left]
while l <= r:
while l <= r and S[l] <= pivot:
l += 1
while l <= r and S[r] >= pivot:
r -= 1
if l <= r:
S[l], S[r] = S[r], S[l]
S[left], S[r] = S[r], S[left]
if r + 1 == k:
return S[r]
elif r + 1 > k:
return quick_select(S, left, r - 1, k)
else:
return quick_select(S, r + 1, right, k)
|
参考:
基于分治编程思想的归并排序和快速排序