C语言如何实现合并排序

来源:爱站网时间:2020-09-11编辑:网友分享
相信很多小伙伴都没有了解过合并排序吧,要知道合并排序是建立在归并操作上的一种有效的排序算法,那么在C语言里如何实现呢?下面就跟随爱站技术频道小编来看看吧!

相信很多小伙伴都没有了解过合并排序吧,要知道合并排序是建立在归并操作上的一种有效的排序算法,那么在C语言里如何实现呢?下面就跟随爱站技术频道小编来看看吧!

其基本模式如下:

分解:把一个问题分解成与原问题相似的子问题

解决:递归的解各个子问题

合并:合并子问题的结果得到了原问题的解。

现在就用递归算法,采用上面的分治思想来解合并排序。

                      合并排序(非降序)

分解:把合并排序分解成与两个子问题

伪代码:

 

 

MERGE_SORT(A, begin, end)

 

if begin

   then mid

           MERGE_SORT(A, begin, mid)

           MERGE_SORT(A, mid+1, end)

           MERGE(A, begin, mid, end)


解决:递归的解各个子问题,每个子问题又继续递归调用自己,直到"begin

 


合并:合并的子问题的结果有个隐含问题,即各个子问题已经是排好序的了(从两个氮元素序列开始合并)。做法是比较两个子序列的第一个元素小的写入最终结果,再往下比较,如下图所示:

        图中:待排序数组为2 4 6  1 3 5

        把2 4 6和 1 3 5 分别存到一个数组中,比较两个数组的第一个元素大小小者存于大数组中,直到两小数组中元素都为32767.

        这里32767 味无穷大,因为 c语言中  int类型是32位,表示范围是-32768-----32768。用无穷大作为靶子可以减少对两个小数组是否为空的判断,有了靶子,直接判断大数组元素个数次就排完了。 

     在整个过程中执行过程示如下图:

分解+执行时自上向下,合并时自下向上。

 代码奉上:

 

 

#include

 

void MERGE(int *A, int b, int m, int e)

{      

        int l = m-b+1, r = e-m, i;

        int L[l+1], R[r+1];

        for(i=0; i

        {

            L[i] = A[b+i];

        }

        for (i=0; i

        {

            R[i] = A[m+i+1];

        }

        L[l] = 32767;

        R[r] = 32767;

        l = 0;

        r = 0;

        for(i=0; i

        {

            if(L[l]

            {

                A[b+i] = L[l];

                l ++;

            }

            else            {

                A[b+i] = R[r];

                r ++;

            }

        }

}

 

void MERGE_SORT(int *A, int b, int e)

{

        if(b

        {

            int m = (b + e) / 2;

            MERGE_SORT(A, b, m);

            MERGE_SORT(A, m+1, e);

            MERGE(A, b, m, e);

        }

}

int main()

{

        int A[500];

        int lens, i;

        printf("Please Enter the lenghth of array:");

        scanf("%d", &lens);

 

        printf("Please Enter the elements of the array:");

        for(i=0; i

            scanf("%d", &A[i]);

 

        MERGE_SORT(A, 0, lens-1);

 

        printf("the result of the sort is:\n");

        for(i=0; i

        {

            printf("%d ", A[i]);

        }

        return 0;

}

本文内容就给大家介绍这么多,想必大家对C语言如何实现合并排序的内容有了一定的了解了吧,希望小编整理的文章能帮助到有需要的小伙伴!

上一篇:C 语言基础教程第三章

下一篇:atoi和itoa函数怎么区分

您可能感兴趣的文章

相关阅读

热门软件源码

最新软件源码下载