首页 > 其他 > 详细

归并排序

时间:2014-05-26 11:22:49      阅读:337      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
#include<iostream>
using namespace std;
///算法重要,但是思想更重要
 
void MemeryArray(int a[],int n,int b[],int m,int c[])///经典框架,be careful!
{
 int i,j,k;
 i = j = k = 0;
 while(i<=n && j<= m)
 {
  if(a[i] < b[j])
      c[k++] = a[i++];
  else
      c[k++] = b[i++];
 }
 while(i<=n) c[k++] = a[i++];
 while(j<=m) c[k++] = b[j++];
}

void mergearray(int a[],int first,int mid,int last,int temp[])
{
    int i = first,j = mid+1;
    int m = mid, n=last;
    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(i = 0;i<k;i++)
        a[first + i] = temp[i];
}

void mergesort(int a[],int first,int last,int temp[])
{
    if(first<last)
    {
        int middle = (first + last) /2;
        mergesort(a,first,middle,temp);
        mergesort(a,middle+1,last,temp);
        mergearray(a,first,middle,last,temp);
    }
}

bool MergeSort(int a[],int n)
{
 int *p = new int[n];
 if(p == NULL) return false;///有可能申请的范围很大,所以最好报错一下
 mergesort(a,0,n-1,p);
 return true;
}
int main()
{
    int a[] = {1,9,5,3,7,2,6,3,4};
    MergeSort(a,8);
    for(int i = 0;i< 8;i++)
        cout<<a[i]<<" ";
}
bubuko.com,布布扣

 

归并排序,布布扣,bubuko.com

归并排序

原文:http://www.cnblogs.com/berkeleysong/p/3747011.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!