首页 > 代码库 > 归并排序

归并排序

2024-08-16 09:49:21   217人阅读

归并平排序的思想：例如对a数组排序；

1：先二分递推至length[a]=1，此时a内元素已排序（只有1个元素嘛。。）；

2：对于区间x～y，递归时合并两个已排序的数组到临时数组t并通过合并过程排好序；

3：此时临时数组t中元素即a数组中x~y区间元素已排序状态，将其复制到a数组x~y区间，则x~y区间元素已排序；

 

对于第2步中的合并排序具体过程如下：

列如合并区间a[p~m]和a[m~y]到t数组；

依次比较两个区间中最小的数（此时两个区间已排序），将两个数中更小的移到临时数组t中，直至两个数组全部为空（当其中一个数组为空时直接将另一个数组中剩余的元素全部移到t数组中即可）,得到的t数组即两个区间合并排序后的状态；

 

代码：

 1 #include <bits/stdc++.h> 2 #define MAXN 100000+10 3 using namespace std; 4  5 //************归并排序************************** 6  7 int merge_sort(int* a, int* t, int x, int y){ 8     if(y-x>1){ 9         int m=x+(y-x)/2;     //****二分10         int p=x, q=m, i=x;11         merge_sort(a, t, p, m);  //***递归左区间12         merge_sort(a, t, q, y);  //***递归右区间13         while(p<m || q<y){       //***合并到临时数组t14             if(q>=y || p<m&&a[p]<a[q]){15                 t[i++]=a[p++];16             }else{17                 t[i++]=a[q++];18             }19         }20         for(int i=x; i<y; i++){    //***将临时数组复制到原数组，此时区间x～y已排序21             a[i]=t[i];22         }23     }24 }25 26 int main(void){27     int n, a[MAXN], t[MAXN];28     cin >> n;29     for(int i=0; i<n; i++){30         cin >> a[i];31     }32     merge_sort(a, t, 0, n);33     for(int i=0; i<n; i++){34         cout << a[i] << " ";35     }36     cout << endl;37     return 0;38 }

 

归并排序


联系
我们