# 基本思路
一次归并
假设左右部分都已经排好序
def merge(li,low,mid,high): | |
i=low | |
j=mid+1 | |
tmp=[] | |
while i<=mid and j<=high: | |
if li[i]<li[j]: | |
tmp.append(li[i]) | |
i+=1 | |
else: | |
tmp.append(li[j]) | |
j+=1 | |
while i<=mid: | |
tmp.append(li[i]) | |
i+=1 | |
while j<=high: | |
tmp.append(li[j]) | |
j+=1 | |
li[low:high+1]=tmp | |
# 验证 | |
li=[2,4,6,8,1,3,5,7] | |
print(li) | |
merge(li,0,3,7) | |
print(li) |
[2, 4, 6, 8, 1, 3, 5, 7] | |
[1, 2, 3, 4, 5, 6, 7, 8] |
先分解
将列表越分越小，直至分成一个元素，使用递归
剩下合并其实就是上面的一次归并
def merge(li,low,mid,high): | |
i=low | |
j=mid+1 | |
tmp=[] | |
while i<=mid and j<=high: | |
if li[i]<li[j]: | |
tmp.append(li[i]) | |
i+=1 | |
else: | |
tmp.append(li[j]) | |
j+=1 | |
while i<=mid: | |
tmp.append(li[i]) | |
i+=1 | |
while j<=high: | |
tmp.append(li[j]) | |
j+=1 | |
li[low:high+1]=tmp | |
def merge_sort(li,low,high): | |
if low<high: #至少两个元素，递归 | |
mid=(low+high)//2 | |
merge_sort(li,low,mid) | |
merge_sort(li,mid+1,high) | |
merge(li,low,mid,high) | |
# 验证 | |
import random | |
li=list(range(16)) | |
random.shuffle(li) | |
print(li) | |
merge_sort(li,0,len(li)-1) | |
print(li) |
[14, 3, 5, 11, 6, 9, 8, 7, 4, 15, 0, 12, 1, 10, 13, 2] | |
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] |
为了更加直观地看到分解以及合并的递归过程，我们对 merge_sort() 函数稍作修改
def merge_sort(li,low,high): | |
if low<high: #至少两个元素，递归 | |
mid=(low+high)//2 | |
merge_sort(li,low,mid) | |
merge_sort(li,mid+1,high) | |
print(li[low:high+1]) | |
merge(li,low,mid,high) |
[10, 9, 8, 13, 14, 4, 1, 2, 7, 6, 15, 5, 11, 0, 3, 12] | |
[10, 9] | |
[8, 13] | |
[9, 10, 8, 13] | |
[14, 4] | |
[1, 2] | |
[4, 14, 1, 2] | |
[8, 9, 10, 13, 1, 2, 4, 14] | |
[7, 6] | |
[15, 5] | |
[6, 7, 5, 15] | |
[11, 0] | |
[3, 12] | |
[0, 11, 3, 12] | |
[5, 6, 7, 15, 0, 3, 11, 12] | |
[1, 2, 4, 8, 9, 10, 13, 14, 0, 3, 5, 6, 7, 11, 12, 15] | |
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] |
# C++
#define _CRT_SECURE_NO_WARNINGS | |
#include<iostream> | |
#include<vector> | |
using namespace std; | |
vector<int> t; | |
void mergesort(vector<int>& a, int low, int high) { | |
if (low >= high) return; | |
int mid = (low + high) >> 1; | |
mergesort(a, low, mid); | |
mergesort(a, mid + 1, high); | |
int i = low, j = mid + 1, idx = low; | |
while (i <= mid || j <= high) { | |
if (i <= mid && j <= high) { | |
if (a[i] <= a[j]) t[idx] = a[i++]; | |
else t[idx] = a[j++]; | |
} | |
else if (i <= mid) { | |
t[idx] = a[i++]; | |
} | |
else { | |
t[idx] = a[j++]; | |
} | |
idx++; | |
} | |
for (int k = low; k <= high; k++) a[k] = t[k]; | |
} | |
int main() { | |
int num; | |
vector<int> a; | |
while (cin >> num) { | |
a.push_back(num); | |
if (cin.get() == '\n')break; | |
} | |
t.resize(a.size()); | |
mergesort(a, 0, a.size() - 1); | |
for (int n : a)cout << n << " "; | |
return 0; | |
} |
# 时间复杂度
从图入手，每一层相当于把整个列表遍历一遍， O(n) ；总共 logn 层，所以合并也就是一半部分的时间复杂度为 O(nlogn) 。
还有因为归并排序不是” 原地排序”，我们开了一个临时空间 tmp ，所以空间复杂度为 O(n) 。
