标题:分治法 合并排序算法 但是为什么输出不对呀
只看楼主
小cai鸟
Rank: 2
等 级:论坛游民
帖 子:53
专家分:25
注 册:2018-7-13
结帖率:60%
已结贴  问题点数:20 回复次数:7 
分治法 合并排序算法 但是为什么输出不对呀
#include<stdio.h>
#define M 100

int merge(int a[], int start, int mid, int end){
    int b[M];
    int i, j, k = 0;
   
    i = start;
    j = mid + 1;
    while(i<=mid && j<=mid){
        if(a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while(i <= mid)
        b[k++] = a[i++];
    while(j <= end)
        b[k++] = a[j++];
    for(i=0; i<k; i++)
        a[i] = b[i];
    return 1;
}

int mergeSort(int a[], int start, int end){
    int mid;

    if(start < end){
        mid = (start + end) / 2;
        mergeSort(a, start, mid);
        mergeSort(a, mid+1, end);
        merge(a, start, mid, end);
    }
    return 1;
}

int main(){
    int a[M];
    int i;
    int n;

    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    mergeSort(a, 0, n);
    for(i=0; i<n; i++){
        printf("%d ", a[i]);
    }

    return 0;
}
/*
    感觉写的没毛病  我想问题可能出在merge函数的最后面那个循环,可我不知道怎么改....有大佬知道我问题出在哪里吗?

*/
搜索更多相关主题的帖子: int start mid end i++ 
2018-09-26 11:31
MeandC
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:8
帖 子:245
专家分:792
注 册:2018-7-14
得分:7 
没有改你的代码,我运行的结果跟你有点不一样

请看图


C果然是有点难啊!
2018-09-26 18:12
MeandC
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:8
帖 子:245
专家分:792
注 册:2018-7-14
得分:0 
没有改你的代码,我运行的结果跟你有点不一样

请看图


C果然是有点难啊!
2018-09-26 18:12
kfyniriu
Rank: 6Rank: 6
等 级:侠之大者
威 望:9
帖 子:105
专家分:426
注 册:2018-7-6
得分:7 
需要将主函数的数组,在调用的函数中交换数值,需要用到指针
C语言并不认可 int a[] 这种没有指定大小的数组
2018-09-26 22:32
小cai鸟
Rank: 2
等 级:论坛游民
帖 子:53
专家分:25
注 册:2018-7-13
得分:0 
回复 2楼 MeandC
不知道为什么变成这样
2018-09-27 09:19
小cai鸟
Rank: 2
等 级:论坛游民
帖 子:53
专家分:25
注 册:2018-7-13
得分:0 
回复 3楼 MeandC
一定需要指针吗?
2018-09-27 09:19
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:7 
保留你原本的算法步骤

程序代码:
#include <stdio.h>
#define M 100

void merge( int a[], size_t start, size_t mid, size_t end )
{
    int b[M];
    size_t k = 0;

    size_t  i=start, j=mid;
    while( i<mid && j<end )
    {
        if( a[i] <= a[j] )
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while( i < mid )
        b[k++] = a[i++];
    while( j < end )
        b[k++] = a[j++];

    for( size_t i=0; i<k; ++i )
        a[start+i] = b[i];
}

void merge_sort( int a[], size_t start, size_t end )
{
    if( start+1 < end )
    {
        size_t mid = (start + end)/2;
        merge_sort( a, start, mid );
        merge_sort( a, mid, end );
        merge( a, start, mid, end );
    }
}

int main( void )
{
    int a[M];
    size_t n;

    scanf( "%zu", &n );
    for( size_t i=0; i!=n; ++i )
        scanf( "%d", &a[i] );

    merge_sort( a, 0, n );
     for( size_t i=0; i!=n; ++i )
        printf( "%d ", a[i] );
}

顺便说一下,写代码要规范,
比如 下标要按C/C++标准使用size_t
比如 变量定义范围要按C/C++标准建议的来(上个世纪末,C标准就不建议将变量一股脑定义到块开头了。)
比如 变量命名要按标准库的习惯规则(不要使用Java的低头撅屁股的命名方式)
若不如此,别人看到你草莽气息浓郁的代码,就懒得浪费时间给你解答了。
2018-09-27 15:33
小cai鸟
Rank: 2
等 级:论坛游民
帖 子:53
专家分:25
注 册:2018-7-13
得分:0 
回复 7楼 rjsp
好的好的 受教了  
不过 我复制你的代码还是没有排序出来呀
而且你的用VC6.0不能编译  Dev-c++倒是可以编译
2018-10-04 20:07



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-490003-1-1.html




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

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