c语言合并两个已排序数组的示例(c语言数组排序)

问题：将两个已排序数组合并成一个排序数组

这里先不考虑大数据量的情况(在数据量很大时不知大家有什么好的思路或方法？)，只做简单数组的处理。

简单代码如下：

说明：之所以把merge函数定义成返回数组长度，是因为后续会有重复数据合并功能的merge版本，考虑到接口一致性。

代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int merge(int* ar1, int len1, int* ar2, int len2, int** rtn)
/*++
 DeScription:
    This routine merge two sorted arrays into one sorted array,
    the same values in different arrays will be keeped.

Arguments:
    ar1 - The first sorted array to be merged
    len1 - The num of items in ar1
    ar2 - The second sorted array to be merged
    len2 - The num of items in ar2
    rtn - The caller proviced pointer to get the result array,
        memory allocated for rtn should be free by the caller.

Return Value:
    The num of items in the merge array
--*/
{
    int i=0,j=0,k=0;
    int m=0;
    int* res = NULL;

if (ar1 == NULL || ar2 == NULL || rtn == NULL) {
        return 0;
    }

*rtn = (int *)malloc((len1+len2)*sizeof(int));
    if(*rtn == NULL) {
        return 0;
    }
    memset(*rtn, 0, (len1+len2)*sizeof(int));
    res = (int*)*rtn;

while(i<len1 && j<len2) {
        if (ar1[i]<=ar2[j]) {
            res[k++] = ar1[i++];
        } else {
            res[k++] = ar2[j++];
        }
    }

while(i<len1) {
        res[k++] = ar1[i++];
    }
    while(j<len2) {
        res[k++] = ar2[j++];
    }

return  len1+len2;
}

int merge_test()
{
    int a1[] = {0,1,2,5,8,19,34,43,52};
    int a2[] = {1,4,5,12,17,33,42,51,53,65,76};
    int len1 = sizeof(a1)/sizeof(int);
    int len2 = sizeof(a2)/sizeof(int);
    int i = 0, len = 0;
    int* a3 = NULL;
    int* ptr = NULL;

len = merge(a1, len1, a2, len2, &a3);
    if (a3 == NULL) {
        printf("a3==NULL\n");
        return 1;
    }

ptr = a3;
    while(i<len) {
        printf("a3[%3d]---->%8d\n", i++, *ptr++);   
    }

if (a3 != NULL) {
        free(a3);
    }

return 0;
}

int main(int argc, char* argv[])
{
    merge_test();

return 0;
}

赞 (0)

相关推荐

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • c语言实现输入一组数自动从大到小排列的实例代码

    如下所示: #include <stdio.h> main() { int x; printf("请输入要排序数字个数:"); scanf("%d",&x); int i,j,k,a,b,num[x]; printf("输入数据:"); for(i=0;i<x;i++) scanf("%d",&num[i]); for(j=0;j<x;j++) { for(k=j+1;k<x;k+

  • C语言将数组中元素的数排序输出的相关问题解决

    问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个.例如输入数组{32,  321},则输出这两个能排成的最小数字32132.请给出解决问题的算法,并证明该算法.       思路:先将整数数组转为字符串数组,然后字符串数组进行排序,最后依次输出字符串数组即可.这里注意的是字符串的比较函数需要重新定义,不是比较a和b,而是比较ab与 ba.如果ab < ba,则a < b:如果ab > ba,则a > b:如果ab = ba,则a = b.比较

  • c语言合并两个已排序数组的示例(c语言数组排序)

    问题:将两个已排序数组合并成一个排序数组 这里先不考虑大数据量的情况(在数据量很大时不知大家有什么好的思路或方法?),只做简单数组的处理. 简单代码如下: 说明:之所以把merge函数定义成返回数组长度,是因为后续会有重复数据合并功能的merge版本,考虑到接口一致性. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <string.h> int merge(int* ar1, int len1, int

  • java去除已排序数组中的重复元素

    java去除已排序数组中的重复元素

    题目描述 给定一个已排序的数组,去除数组中的重复元素,只保留一个重复的元素,并且返回新的数组长度. 要求: 不要给数组分配额外的空间,你必须使用常量的内存大小进行原地操作. 例如: 给出数组A=[1,1,2],你的函数调用之后必须返回长度length=2,并且A现在变成[1,2]. 输入 一个已排序的数组,例如[1,1,2]. 输出 返回数组新的长度,例如length=2. 快慢指针法 设置fast指针遍历数组,slow指针指向不重复元素的下一位. public static int remov

  • java实现合并两个已经排序的列表实例代码

    相对于C++来说,Java的最大特点之一就是没有令人困惑的指针,但是我们不可否认,在某些特定的情境下,指针确实算的上一把利刃.虽然Java中没有明确定义出指针,但是由于类的思想,我们可以使用class来实现指针的操作.小二,上栗子-----合并两个已经排序的列表,输出合并后列表的头结点,且合并后的列表中的元素是有序的. 需要时刻铭记于心的:在Java中,列表的一个节点其实就是某个类实例化的一个对象. 示例代码如下: 复制代码 代码如下: package DecemberOf2013; class

  • JavaScript简单实现合并两个Json对象的方法示例

    JavaScript简单实现合并两个Json对象的方法示例

    本文实例讲述了JavaScript简单实现合并两个Json对象的方法.分享给大家供大家参考,具体如下: $.mergeJsonObject = function(jsonbject1, jsonbject2) { var resultJsonObject = {}; for (var attr in jsonbject1) { resultJsonObject[attr] = jsonbject1[attr]; } for (var attr in jsonbject2) { resultJso

  • Python实现合并两个有序链表的方法示例

    Python实现合并两个有序链表的方法示例

    本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

  • C语言求两个正整数的最大公约数示例代码

    目录 前言 1.穷举法 2.欧几里得算法(辗转相除法) 3.递归方法 附:相减法 总结 前言 两个正整数的最大公约数(Greatest Common Divisor, GCD)是能够整除这两个整数的最大整数.两个正整数的最大公约数的求法有多种解答,本文就三种方法做详细介绍:穷举法.欧几里得算法(辗转相除法).递归方法. 我们从一道问题来引入:编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的最大公约数. 1.穷举法 根据最大公约数的定义,我们可以采用一种最简单的方

  • C语言合并两个带头节点升序排列链表

    合并链表,顾名思义,就是将两个按顺序存放数据的链表中的数据合并为用一个链表存储,比如在处理多项式的加减法时就需要将两个多项式的数据进行合并.合并方式有很多种:如果按照存储方式的不同,可以将两个链表的数据分别提取出来生成一个新的链表来存储原先两个链表的数据,还可以将其中一个链表的数据依次插入到另外一个链表的相应位置当中去.在遇到相同数据时可以采取只留下一个数据的方式和两个数据均保留的方式.这些不同点需要到具体的问题中具体分析,但是只是在细节上有一些差别,大体的思路都是一样的,本文主要介绍将一个链表

  • C语言数据结构经典10大排序算法刨析

    C语言数据结构经典10大排序算法刨析

    1.冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层循环实现的方法. // 参数arr是待排序数组的首地址,len是数组元素的个数. void bubblesort1(int *arr,unsigned int len) { if (len<2) return; // 数组小于2个元素不需要排序. int ii; // 排序的趟数的计数器. int jj; // 每趟排序的元素位置计数器. int itmp

  • JavaScript实现基础排序算法的示例详解

    目录 前言 正文 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 前言 文本来总结常见的排序算法,通过 JvavScript  来实现 正文 1.冒泡排序 算法思想:比较相邻两个元素的大小,如果第一个比第二个大,就交换它们.从头遍历到尾部,当一轮遍历完后,数组最后一个元素是最大的.除去最后一个元素,对剩下的元素重复执行上面的流程,每次找出剩余元素中最大的,遍历完后,数组是升序的 算法分析:总共需要进行length * (length - 1) / 2 次比较,所以时间复杂度为O(n^2)

  • go语言题解LeetCode88合并两个有序数组示例

    目录 题目描述 思路分析 AC 代码 题目描述 原题链接 : 88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目. 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列. 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素

随机推荐