Kisser Leon

这个kisser不太冷
posts - 100, comments - 102, trackbacks - 0, articles - 0

合并排序算法

Posted on 2007-03-18 22:33 kk 阅读(1932) 评论(2)  编辑 收藏 引用 所属分类: Algorithm
#include <iostream>
#include <string>
using namespace std;

void Merge(int * A, int p, int q, int r);

void output(int * A, int size)
{
    for(int i=0; i<size; i++)
        cout << A[i] << " ";
   
    cout << endl;
}

void MergeSort(int * A, int p, int r) //sort A[p,r]
{
    if(p < r)
    {
        int q = (p+r)/2;
        MergeSort(A, p, q);
        MergeSort(A, q+1, r);
        Merge(A, p, q, r);
    }
}

void Merge(int * A, int p, int q, int r) //merge A[p,q] with A[q+1,r]
{
    // array1 A[p,q]
    // array2 A[q+1,r]
    int * pp = new int[r-p+1];
    int i1=p;
    int i2=q+1;
    for(int i=0; i<r-p+1; i++)
    {
        if(i1<=q && i2<=r)
        {
            if(A[i1]<A[i2])
            {
                pp[i] = A[i1];
                i1++;
            }
            else
            {
                pp[i] = A[i2];
                i2++;
            }
        }
        else if(i1>q)
        {
            for(;i<r-p+1;i++)
            {
                pp[i] = A[i2];
                i2++;
            }
           
            break;
        }
        else if(i2>r)
        {
            for(;i<r-p+1;i++)
            {
                pp[i] = A[i1];
                i1++;
            }
           
            break;
        }
    }
   
    for(int i=p; i<=r; i++)
    {
        int t = pp[i-p];
        A[i] = pp[i-p];
    }
   
    delete [] pp;
}


int main()
{
    int Ar[] = {11,2,9,7,6,5,3,8,2,3,5,1,-5,8,7};   
    int size = sizeof(Ar)/sizeof(int);
    output(Ar, size);
   
    MergeSort(Ar,0,size-1);   
    output(Ar, size);   

    return 0;
}

Feedback

# re: 合并排序算法  回复  更多评论   

2007-03-19 09:48 by 哈哈
以前数据结构时学的,已经快还给老师了,不过现在都没用到,唉。。。

# re: 合并排序算法  回复  更多评论   

2007-08-22 08:51 by 杨建东
编程好难哦!!老师布置这个题,都还没有做出来哦

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理