归并排序(Merge Sort)
归并排序是利用归并的思想实现排序的方式,该算法采用的是经典的分治算法
归并排序过程
- 将n个元素从中间切开,分成两部分。(左边可能比右边多1个数)
- 将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1。
- 从最底层开始逐步合并两个排好序的数列。
归并排序动图
归并排序过程归并排序代码(递归)
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[10] = {33, 12, 15, 1, 5, 9, 48, 4, 13, 19};
void mergeArray(int *a, int first, int mid, int end, int *temp)
{
int i = first, j = mid + 1;
int m = mid, n = end;
int k = 0;
while(i <= m && j <= n)
{
if(a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while(i <= m) temp[k++] = a[i++];
while(j <= n) temp[k++] = a[j++];
for(int l=0; l<k; ++l) a[first + l] = temp[l];
}
void mergeSort(int *a, int first, int end, int *temp)
{
if(first < end)
{
int mid = (first + end) / 2;
mergeSort(a, first, mid, temp);
mergeSort(a, mid + 1, end, temp);
mergeArray(a, first, mid, end, temp);
}
}
void sort(int *b)
{
int temp[10];
mergeSort(b, 0, 9, temp);
}
int main()
{
for(int i=0; i<10; ++i) cout<<a[i]<<" ";
cout<<endl;
sort(a);
for(int i=0; i<10; ++i) cout<<a[i]<<" ";
cout<<endl;
}
归并排序复杂度
时间复杂度:
空间复杂度:
网友评论