Liny_@NotePad

沉迷ACG中

合并排序实现

YOYO posted @ 2009年4月29日 07:56 in 【算法】与【数据结构】 with tags 排序 , 2058 阅读

 = =

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. /******************************************
  5. * 合并两个有序的子数组
  6. *
  7. * 输入：整数数组A[]，下标p,q,r，元素个数m
  8. *            其中A[p]~A[q]和A[q+1]~A[r]已按递增顺序排序
  9. * 输出：按递增顺序排序的子数组A[p]~A[r]
  10. ******************************************/
  11. void merge(int A[], int p, int q, int r, int m){
  12.         int *bp = new int[m];
  13.         int i,j,k;
  14.         i = p; j = q+1; k=0;
  15.         while(i<=q&&j<=r){      //    i从p开始，j从q+1开始 比较A[i]和A[j]，递减放入新数组
  16.                 if(A[i]<=A[j]){
  17.                         bp[k++] = A[i++];
  18.                 }else{
  19.                         bp[k++] = A[j++];
  20.                 }
  21.         }
  22.         if(i==q+1){     // 若A[p]~A[q]已经输入完，则将A[q+1]~A[r]中未录入的继续录入
  23.                 for(;j<=r;j++){
  24.                         bp[k++] = A[j];
  25.                 }
  26.         }else{  //        若A[q+1]~A[r]已经输入完，则A[p]~A[q]将中未录入的继续录入
  27.                 for(;i<=q;i++){
  28.                         bp[k++] = A[i];
  29.                 }
  30.         }
  31.         k = 0;
  32.         for(i=p; i<=r; i++){    //  把排序好的数存回A
  33.                 A[i] = bp[k++];
  34.         }
  35.         delete bp;
  36. }
  37.  
  38. /******************************************
  39. * 合并排序算法
  40. *
  41. * 输入：具有n个元素的数组A[]
  42. * 输出：按递增顺序排序的数组A[]
  43. ******************************************/
  44. void merge_sort(int A[], int n){
  45.         int i,s,t = 1;
  46.         while(t<n){     //   每2个含t/2个元素的数组进行合并，合并完后t*2
  47.                 s = t, t = 2*s, i = 0;
  48.                 while(i+t<n){
  49.                         merge(A,i,i+s-1,i+t-1,t);
  50.                         i = i + t;
  51.                 }
  52.                 if(i+s<n){
  53.                         merge(A,i,i+s-1,n-1,n-i);
  54.                 }
  55.         }
  56. }
  57.  
  58. int main(){
  59.         int i,n;
  60.  
  61.         cout<<"请输入数组元素个数：";
  62.         cin>>n;
  63.  
  64.         cout<<"请输入元素："<<endl;
  65.         int* A = new int[n];
  66.         for(i=0;i<n;i++){
  67.                 cin>>A[i];
  68.         }
  69.  
  70.         merge_sort(A,n);
  71.  
  72.         cout<<"排序结果："<<endl<<A[0];
  73.         for(i=1;i<n;i++){
  74.                 cout<<" "<<A[i];
  75.         }
  76.         cout<<endl;
  77.  
  78.         return 0;
  79. }
  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter