（五）归并排序和快速排序

最近姐妹俩回家过年去了 ，所以都不会出场，但是我画了很详细的图，应该非常好懂了！

归并排序（Merge Sort）

归并排序是典型的分治策略的运用，把问题先分为一些小的问题，递归地治这些小问题，当问题直接小到一定规模时，就可以直接求解了，最后我们再把所有小问题的解综合到一起。

首先我们通过一张图来了解这个过程（PS真的难用）：

现在我们来具体了解这种算法的细节：

（一）归并排序——分

分这一步很简单，递归地把待排数组二分，直到全部分为只有一个元素的数组（单个数字），此时我们可以把这些单个元素的数组看作一个有序数组（只有一个数字当然有序啦）。

（二）归并排序——治

考虑得到的两个有序数组，我们尝试把他合并为一个有序数组，以最后一步的[1, 3, 5, 8]和[2, 4, 6, 7]为例：

1.建立一个大小为8的临时数组，用

和

分别标记两个有序子数组；

2.比较

和

指向的元素大小，将较小的数字放到临时数组中，同时指向该元素的

或

向后移一位；

3.当一个子数组的所有数字都放到临时数组中之后，将另一个数组中的剩余元素全部放到临时数组中，合并完成，把临时数组中的元素复制回原数组。

图示如下：

从只有一个元素的待排数组开始，依次归并排序，最后我们就可以得到一个有序的数组。

（三）归并排序的可视化演示

（视频大小：210KB）

（四）归并排序的python实现

# 把两个有序数组合并为一个有序数组

defmerge(a,b):

# 临时数组

temp= []

i=j=

# 比较a[i]和b[j]，将较小的放入temp中，并把对应的i或j加1

whilei

ifa[i]

temp.append(a[i])

i+=1

else:

temp.append(b[j])

j+=1

# 把剩余的数字添加到temp中

ifi==len(a):

forkinb[j:]:

temp.append(k)

else:

forkina[i:]:

temp.append(k)

# print(temp)

returntemp

# 递归对数组进行二分并排序

defmerge_sort(array):

iflen(array)

returnarray

middle=int(len(array)/2)

# 分别对左右两个数组递归排序

left=merge_sort(array[:middle])

right=merge_sort(array[middle:])

returnmerge(left,right)

if__name__=='__main__':

a= [8,3,1,5,7,2,4,6]

print(merge_sort(a))

快速排序（Quicksort）

之所以把快速排序和归并排序放在一起，是因为两种算法有一定的相似之处——二者都用了分治策略，区别在于归并排序是先分后治，而快速排序是先治后分。

（一）快速排序的思想

治：选取数组中的一个元素作为主元，把数组中小于该元素的放在该元素的左边，大于的放在右边；

分：把数组分为3个部分，分别比主元大、小的两个数组和主元，再对那两个数组递归分治。

最后得到的数组就是有序数组。

（二）快速排序过程

1.选取最右边的元素作为主元，我们用

来标识待排数组的第一个元素位置，

用来标识主元所在位置，

用于标识比主元小的数组的最右边元素的位置，

用于标识还未进行比较的第一个元素；

对于每一次递归而言，有p=j，i=p-1，而对于第一次而言p = j = 0，i=-1；

2.使用A[j]从A[p]到A[r-1]进行遍历：

如果A[j]比主元小，将A[j]和A[i+1]交换，并将i和j加1；

如果A[j]比主元大，将j加1；

3.遍历完成后，A[p:i]内元素均比A[r]小，A[i+1:r-1]内元素均比A[r]大，此时交换A[r]和A[i+1]，得到的数组A[p:i]内元素均比A[i+1]小，数组A[i+2:r]内元素均比A[i+1]大；

4.对得到的两个数组递归快速排序。

依然以A=[8, 3, 1, 5, 7, 2, 4, 6]为例，第一次递归图解如下：

再对6左右两边的数组重复上述步骤，最后就能得到有序数组。

（三）快速排序的可视化演示

（视频大小：197KB）

（四）快速排序的python实现

# 对于给定的待排数组，把比array[r]小的元素放在左边，大的放在右边

# 最后把该元素放到两个数组之间

defpartition(array,p,r):

x=array[r]

i=p-1

forjinrange(p,r):

# 比主元x小时，交换array[i+1]和array[j]，并让i+1

ifarray[j]

array[i+1],array[j] =array[j],array[i+1]

i+=1

# 完成遍历后把主元和右侧数组最左边的元素交换

# 保证主元左边元素逗比主元小，右边元素逗比主元大

array[r],array[i+1] =array[i+1],array[r]

# print(a)

# 返回主元的位置

returni+1

# 对数组递归进行快速排序

defquick_sort(array,p,r):

# 递归直到待排数组最多只有一个元素

ifp

middle=partition(array,p,r)

# 对主元左右两边数组分别进行快排

quick_sort(array,p,middle-1)

quick_sort(array,middle+1,r)

if__name__=='__main__':

a= [8,3,1,5,7,2,4,6]

quick_sort(a,,len(a)-1)

print(a)

奉太郎说

这篇讲的两个排序算法，平均时间复杂度都是O(nlogn)，快速排序最坏情况会达到O(n2)，归并排序最坏也是O(nlogn)。不过归并排序用到了很多额外的空间，一般在实际运用中，使用快速排序比较广泛。

快速排序的最坏情况就是数组有序的情况，此时时间复杂度会达到前面说的O(n2)，原因就是每次递归，有一侧的数组一直为空，此时递归深度为n。解决这个问题的办法就是前面提过的随机化算法——把初始数组随机化（打乱），或者随机选择主元，有兴趣的可以在python上实现一下~