分治法之合并排序（C实现）

迷南。 2022-08-09 18:51 177阅读 0赞

#include <stdio.h>
     
    void merge(int a[],int p,int q,int r)
    {
        int n1=q-p+1,n2=r-q;
        int b1[n1];
        int b2[n2];
        int i=0,j=0,temp1=p,temp2=q;
        while(p<=q)
        {
            b1[i]=a[p];
            ++i;
            ++p;
        }
        while(q+1<=r)
        {
            b2[j]=a[q+1];
            ++j;
            ++q;
        }
     
        p=temp1;q=temp2;
        i=0,j=0;
        while(p<=r)
        {
            if(i==n1)         
            {
                a[p]=b2[j];
                ++j;
            }
            else if(j==n2)
            {
                a[p]=b1[i];
                ++i;
            }
         
            else if(b1[i]<b2[j])
            {
                a[p]=b1[i];
                ++i;
            }
            else
            {
                a[p]=b2[j];
                ++j;
            }
            ++p;
        }
    }
     
    void merge_sort(int a[],int p,int r)
    {
        int q=0;
        if(p<r)
        {
            q=(p+r)/2;
            merge_sort(a,p,q); 
            merge_sort(a,q+1,r);
            merge(a,p,q,r);
        }
    }
     
    int main()
    {
        int i, a[100];
        srand(time(0));
        for ( i = 1; i < 101; ++i ){
            a[i-1] = rand() % 1001;
            printf( "%3d ", a[i-1] );
            if(i%15==0) printf("\n"); 
        }
        printf("\n\n");
        SelectionSort(a, 100);
        for ( i = 1; i < 101; ++i ){
            printf( "%3d ", a[i-1] );
            if(i%15==0) printf("\n"); 
        }
        getch();
        return 0;
    }

运行效果图

![20151104134325027][]

[20151104134325027]: /images/20220731/d1ad26fa11f7409188996565b8ceb72f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关分治法-归并排序

一、前言归并排序归并排序是建立在归并操作上的一种有效的排序算法，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。该算法是采用分

落日映苍穹つ/ 2022年11月16日 05:47/ 0 赞/ 205 阅读

相关分治——合并排序

分治思路： 1. 大问题分解为子问题 2. 子问题相互独立，可以直接解决 3. 将子问题合解，得到原问题的解使用分治法进行数组排序。 \ 将一个数列等分为两半，

- 日理万妓/ 2022年08月21日 04:54/ 0 赞/ 172 阅读

相关分治法之合并排序（C实现）

include <stdio.h> void merge(int a[],int p,int q,int r) { int

迷南。/ 2022年08月09日 18:51/ 0 赞/ 178 阅读

相关归并排序 java（分治法）

归并排序：归并排序是将给定的数列，尽可能地数量相同的两个数列。然后通过递归调用进行排序，排序完毕后的，将两个已经排好序的数列

以你之姓@/ 2022年05月31日 07:36/ 0 赞/ 259 阅读

相关快速排序法和合并排序法——Python实现

快速排序法 class Solution: def sort(self,a): first = 0

向右看齐/ 2022年05月19日 06:51/ 0 赞/ 178 阅读

相关【数据结构】合并K个有序链表(采用分治法、vector排序法分别实现)

一、合并K个链表将n个已经有序的链表，合并成一个链表，使之有序【1】排序法实现，时间复杂度为O(KNlogKN) 【2】分治法实现，时间复杂度为O(KNlog

爱被打了一巴掌/ 2022年05月15日 06:08/ 0 赞/ 133 阅读

相关 java归并排序及分治法

归并排序采用分治法的思想：将原问题分解为若干规模较小但类似于原问题的子问题，递归地求解这些子问题，再合并这些子问题的解来建立原问题的解。分治模式在每层递归时都有三个步骤：

川长思鸟来/ 2022年05月15日 03:12/ 0 赞/ 225 阅读

相关排序问题（蛮力法，分治法）

蛮力法：选择排序法：算法思想：在剩余序列中选出最小（或最大）的关键字，和剩余序列的第一个关键字交换位置，依次选择下去（每次扫描结束找出最小的一个元素依次放在前面的位

布满荆棘的人生/ 2022年04月16日 04:59/ 0 赞/ 236 阅读

相关排序算法--------快速排序(分治法 )

快速排序 1.简介 2.实现的基本思想 3.举个例子 4.java代码实现 4.1实现代码 4.2 主方法代码 5

我不是女神ヾ/ 2022年03月20日 11:56/ 0 赞/ 278 阅读

相关分治法——归并排序

归并排序归并排序是成功应用分治法的完美例子，归并排序是按照记录在序列中的位置对序列进行划分。【问题】应用归并排序方法对一个记录序列进行升序排序。归并排序（m

￡神魔★判官ぃ/ 2021年06月22日 15:36/ 0 赞/ 495 阅读