美文网首页
合并两个内部有序的数组

合并两个内部有序的数组

作者: QinRenMin | 来源:发表于2018-07-07 13:45 被阅读0次

一个数组,内部是由两个有序的数组构成的,例如4 7 8 6 2 ,如果已经知道内部有序的位置3 ,通过设计算法,得到整体有序(从小到大)数组 2 4 6 7 8
题目要求:
最坏情况下时间复杂度为:O(n)
辅助空间为:O(1)

  • 问题思考
    将两个数组按照从小到大的顺序先排序(交换位置即可),然后前后比较;具体过程:
    4 7 8 6 2
    4 7 8 2 6
    2 7 8 4 6
    2 4 8 7 6 --> 6 7
    2 4 6 8 7 --> 7 8
    得到结果 2 4 6 7 8
    代码如下:
#include<stdio.h>
//合并两个排好顺序的子数组 
void sort_1(int a[],int low,int high)
{
    int temp,i;
    if(a[low] < a[high]) return; //如果是降序,就不交换位置 
    
    else
    
    {
        temp = a[low];
        a[low++] = a[high];
        a[high--] = temp;   
    }
    
}
void swap_1(int a[],int low,int mid,int high)
{
    int temp;
    //前后比较 
    while(low < high)
    {
        if(a[low] > a[mid +1])
        {
            temp = a[low];
            a[low] = a[mid+1];
            a[mid+1] = temp;
            sort_1(a,mid+1,high);
        }
        low++;
        
    }
}
void main(){
    int i;  int num;    int k;
    printf("请输入数组长度\n");
    scanf("%d",&num);
    int a[num];
    for(i = 0; i < num; i++)
    {
        scanf("%d",&a[i]);
    }
    printf("请输入有序断点\n");
    scanf("%d",&k);
    sort_1(a,0,k-1);
    sort_1(a,k,num-1);
    swap_1(a,0,k-1,num-1);
    for(i = 0; i < num; i++)
    {
        printf("%d ",a[i]);
    }
}
运行结果

相关文章

网友评论

      本文标题:合并两个内部有序的数组

      本文链接:https://www.haomeiwen.com/subject/myjwuftx.html