归并排序
先上伪代码:
def MERGE(A, p, q, r):
n1 = q-p+1
n2 = r-q
new L[],r[]
for i=1 to n1:
L[i] = A[p+i-1]
for j=1 to n2:
R[j] = A[q+j]
L[n1+1] = INF //INF即正无穷
L[n2+1] = INF
i=1
j=1
for k=p to r
if L[i]<=R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
def MERGE_SORT(A,p,r):
if p < r
q = floor((p+r)/2) //向下取整
MERGE_SORT(A, p, q)
MERGE_SORT(A, q+1, r)
MERGE(A, p, q, r)
else:
return
再来Python:
import math
arr = [0,4,3,5,4,5,6,5,1,9] #待排序数组
INF = 99999999
def merge_sort(arr, p, r):
if p < r:
q = math.floor((p + r) / 2)
merge_sort(arr, p, q)
merge_sort(arr, q + 1, r)
merge(arr, p, q, r)
def merge(arr, p, q, r):
n1 = q - p + 1
n2 = r - q
L = []
R = []
for i in range(n1):
L.append(arr[p+i])
for j in range(n2):
R.append(arr[q+j+1])
L.append(INF)
R.append(INF)
i = j = 0
for k in range(r - p + 1):
if L[i] <= R[j]:
arr[p+k] = L[i]
i += 1
else:
arr[p+k] = R[j]
j += 1
merge_sort(arr,0,9)
print(arr)
算法分析
归并排序顾名思义,就是把两个数列合并成一个,其中MERGE()
函数就是这个作用。
MERGE()
函数解析
行数 | 作用 |
---|---|
参数 |
A 指待排序数列,p 指数列最小下标,q 指数列中间下标,r 指数列最大下标 |
1~2 |
p~n1 指的是对半分后靠左的子序列,同样的,n2~q 指的是靠右的子序列 |
3 |
新建靠左的子序列和靠右的子序列 |
4~7 |
把A[p..n1] 与A[n2~r] 复制到L[] 和R[]
|
8~9 |
把L[] 和R[] 的最后一个数设为正无穷,方便比较 |
10~11 |
略 |
12 |
进入一层循环,用于归并数列 |
13~18 |
比较L[i] 和R[j] ,把比较小的先放入数列 |
MERGE_SORT()
函数解析
行数 | 作用 |
---|---|
1 |
如果p < r 为真,则代表数列存在 |
2 |
确定q ,也就是数列中间下标 |
3~4 |
如果还能分,则继续分,不能的话,就是第7 行的事了 |
5 |
归并 |
6 |
略 |
7 |
如果数列没了,返回,进行归并 |
时间复杂度
归并排序的时间复杂度为: