| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 433 人关注过本帖
标题:分治法MergerSort函数里的递归我实在是不清楚 大家帮我下 讲下过程。
只看楼主 加入收藏
hacker5402
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2012-1-28
结帖率:0
收藏
已结贴  问题点数:30 回复次数:3 
分治法MergerSort函数里的递归我实在是不清楚 大家帮我下 讲下过程。
MergerSort函数里的递归我实在是不清楚

程序代码:
#include <iostream>
#include <conio.h>
#include <malloc.h>

using namespace std;


const int array_size = 5;

void Merger(int A[], int p, int q, int r); // void Merger(int * A, int p, int q, int r);
void MergerSort(int A[], int p, int r); // void MergerSort(int * A, int p, int r);

// p为数组A第一个元素位置 r为数组A最后一个元素位置

int main()
{
    int A[array_size] = {0,4,2,3,1};
    int i = 0;
    MergerSort(A, 0, array_size-1);
    for (int i = 0; i < array_size; i++)
    {
        cout << A[i] << " ";
    }
    
    getch();
    return 0;
}

//p为数组A第一个元素位置 r为数组A最后一个元素位置
void MergerSort(int A[], int p, int r) // void MergerSort(int * A, int p, int r)  就是这里的

{
        int mid = 0;
        if (p < r)
        {
                mid = (r + p) / 2;
                MergerSort(A, p, mid);
                MergerSort(A, mid + 1, r); 
                Merger(A, p, mid, r);
        }
} 

// p为数组A第一个元素位置 r为数组A最后一个元素位置 q为数组A中间位置
void Merger(int A[], int p, int q, int r) // void Merger(int * A, int p, int q, int r)
{                               
    int n1 = q - p + 1;
    int n2 = r - q ;
    int i = 0, k = 0, j = 0;    
    int L[n1 + 1]; // int * L = (int *)malloc(sizeof(int) * n1 + 1);
    int R[n2 + 1]; // int * R = (int *)malloc(sizeof(int) * n2 + 1);
    for (i = 0; i < n1; i++)
    {
        L[i] = A[p + i];
    }
    for (i = 0; i < n2; i++)
    {
        R[i] = A[q + i + 1];
    }
    i = j = 0;
    
    for (k = p; k <= r; k++)
    {
        if ((i < n1 && j == n2) || (i < n1 && j < n2 && L[i] < R[j])) 
            A[k] = L[i++];
        else if ((i == n1 &&j < n2) || (i < n1 && j < n2 && L[i] >= R[j])) 
            A[k] = R[j++];
    }
    // free(L);    // 清理L之前申请的内存
    // free(R);    // 清理L之前申请的内存
}


搜索更多相关主题的帖子: color 函数 
2012-02-29 13:16
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6815
专家分:42393
注 册:2010-12-16
收藏
得分:10 
看不懂就翻书来看看

人家给你见的时候 和书本说的也差不了多少。

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2012-03-01 15:57
chenjin1st
Rank: 2
来 自:湖南
等 级:论坛游民
帖 子:26
专家分:44
注 册:2011-5-13
收藏
得分:10 
归并排序。呵呵。就是消耗内存空间 速度挺快的。nlong2(n)

共同进步,共同收获!!!!
2012-03-03 12:07
zhoufeng1988
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:北京
等 级:贵宾
威 望:27
帖 子:1432
专家分:6329
注 册:2009-5-31
收藏
得分:10 
看到这个就想到我刚买的算法导论,哎~
同样困惑~

可以先下个算法导论看看,第一章就讲的这个~
2012-03-06 22:47
快速回复:分治法MergerSort函数里的递归我实在是不清楚 大家帮我下 讲下过程。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017263 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved