归并排序(MERGE-SORT):是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。
- 时间复杂度:O(n log n)
- 空间复杂度:T(n)
- 发明者:约翰·冯·诺伊曼
输入:
8
23 13 49 6 31 19 28 4
输出:
4 6 13 19 23 28 31 49
代码:
#include<iostream> using namespace std; // left 下标起点 // right 下标终点 void merge_sort(int left,int right,int a[],int keep[]) { if(left>=right) { return; } int mid=(left+right)/2;//数组分成两部分 merge_sort(left,mid,a,keep);//左递归 merge_sort(mid+1,right,a,keep);//右递归 int i=left,j=mid+1,k=0;// i为左边的数 , j为右边的数 , k为keep数组的下标 while(i<=mid && j<=right) { if(a[i]<=a[j])// 哪边的数小就存入keep中 { keep[k++]=a[i++]; } else { keep[k++]=a[j++]; } } //将没有存入keep数组中的数存进去 while(i<=mid) { keep[k++]=a[i++]; } while(j<=right) { keep[k++]=a[j++]; } //将已排序好的数组再赋值给原数组 for(i=0;i<k;i++) { a[left+i]=keep[i];//left是针对右边的数 } } int main () { int a[100]; int keep[100]; int n; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } merge_sort(0,n-1,a,keep); //输出 for(int i=0;i<n;i++) { cout<<a[i]<<" "; } return 0; }