内容纲要
归并排序的理解和实现
原理
- 将整个序列看成是 n 个长度为1的有序子序列
- 然后两两归并,得到 n/2 个长度为2的有序子序列
- 继续按照该策略归并,直到得到 1 个长度为n的有序子序列
上述过程即一次反向递归,也是归并排序的基本思想
可视化归并排序
代码实现
C++代码实现
迭代版本
迭代版本的理解需要一定的时间
// 迭代法
void merge_sort_iteration(vector<int> &v){
int n = v.size();
vector<int> *seq = &v;
vector<int> result(n,0);
vector<int> *res = &result; //通过交换指针完成迭代
for(int step = 1; step < n;step*=2){ //元素间距(递归层次)
for(int beg = 0;beg < n;beg += 2*step){ //子序列区间
int left = beg;
int mid = min(beg + step,n); //考虑最后的子区间长度不够的情况
int right = min(beg+ 2*step,n);
int k = left;
int beg_1 = left,end_1 = mid;
int beg_2 = mid,end_2 = right;
while(beg_1 < end_1 && beg_2 < end_2){ //择小存入res
(*res)[k++] = (*seq)[beg_1] < (*seq)[beg_2] ? (*seq)[beg_1++] : (*seq)[beg_2++];
}
while(beg_1 < end_1){
(*res)[k++] = (*seq)[beg_1++];
}
while (beg_2 < end_2){
(*res)[k++] = (*seq)[beg_2++];
}
}
// 交换指针变量(迭代)
vector<int> *T = seq;
seq = res;
res = T;
}
if (seq != &v) {
for (int i = 0; i < n; i++)
res[i] = seq[i];
res = seq;
}
}
递归版本
#include <iostream>
#include <vector>
using namespace std;
// 递归法
vector<int> merge_recursion(vector<int> left,vector<int> right){
vector<int> res;
int beg_1 = 0,beg_2 = 0;
while(beg_1 < left.size() && beg_2 < right.size()){
res.push_back(left[beg_1] < right[beg_2] ? left[beg_1++] : right[beg_2++]);
}
while(beg_1 < left.size()){
res.push_back(left[beg_1++]);
}
while(beg_2 < right.size()){
res.push_back(right[beg_2++]);
}
return res;
}
vector<int> merge_sort_recursion(vector<int> v){
if(v.size() < 2) return v;
else{
int mid = v.size()/2;
vector<int> left(v.begin(),v.begin()+mid);
vector<int> right(v.begin()+mid,v.end());
return merge_recursion(merge_sort_recursion(left),merge_sort_recursion(right));
}
}
int main()
{
vector<int> v;
v.push_back(9);
v.push_back(-1);
v.push_back(7);
v.push_back(5);
//merge_sort_iteration(v);
v = merge_sort_recursion(v);
for(int i = 0;i < 4;i++) cout << v[i] << " ";
cout << endl;
return 0;
}
Python代码实现
def merge_method(left,right):
result = [] # 临时列表,保存排序后的序列
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while(left):
result.append(left.pop(0))
while(right):
result.append(right.pop(0))
return result
def merge_sort(seq):
if(len(seq) < 2):
return seq
else:
mid = len(seq)//2
left,right = seq[0:mid],seq[mid:]
return merge_method(merge_sort(left),merge_sort(right))
# 排序测试
if __name__ == '__main__':
seq = [3,-4,22,-8,47,15,36,26,27,50]
seq = merge_sort(seq)
print(seq)