那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

[算法问题]合并两个已经排序的数组为另一个数组

问题描述:
设子数组a[0:k]和a[k+1:n-1]已排好序(0<=k<=n-1).试设计一个合并这两个子数组为排好序的数组a[0:n-1]的算法.要求算法在最坏的情况下所用的计算时间为O(n), 且只用到O(1)的辅助空间.

这一题比较简单,看代码就知道了.

#include <stdio.h>

void DisplayArray(int *pArray, int nLen)
{
    
for (int i = 0; i < nLen; ++i)
    
{
        printf(
"array[%d] = %d\n", i, pArray[i]);
    }

}


// pArray1和pArray2是已经排好序的数组,要求将它们按照顺序合并到pArray中
// 排序之后的数组不会有重复的元素
void MergeArray(int *pArray1, int nLen1, int *pArray2, int nLen2, int *pArray)
{
    
int i, j, n;

    i 
= j = n = 0;
    
while (i < nLen1 && j < nLen2)                  // 循环一直进行到拷贝完某一个数组的元素为止
    {
        
if (pArray1[i] < pArray2[j])                // 拷贝array1的元素
        {
            pArray[n
++= pArray1[i++];
        }

        
else if (pArray1[i] > pArray2[j])            // 拷贝array2的元素
        {
            pArray[n
++= pArray2[j++];                       
        }

        
else                                          // 相等的元素拷贝
        {
            pArray[n
++= pArray2[j++];                       
            
++i;
        }

    }


    
if (i == nLen1)                              // 如果array1已经被拷贝完毕就拷贝array2的元素
    {
        
while (j < nLen2)
            pArray[n
++= pArray2[j++];
    }

    
else                                         // 如果array2已经被拷贝完毕就拷贝array1的元素
    {
        
while (i < nLen1)
            pArray[n
++= pArray1[i++];
    }

}


int main()
{       
    
int array1[] = {1457};
    
int array2[] = {2368};
    
int array3[8];
    MergeArray(array1, 
4, array2, 4, array3);
    printf(
"Merge Array:\n");
    DisplayArray(array3, 
8);

    
return 1;
}


posted on 2006-09-26 23:27 那谁 阅读(5598) 评论(6)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: [算法问题]合并两个已经排序的数组为另一个数组  回复  更多评论   

该实现与题意不合吧, 题目是说"设子数组a[0:k]和a[k+1:n-1]已排好序(0<=k<=n-1).试设计一个合并这两个子数组为排好序的数组a[0:n-1]的算法.", 即只有一个a[]
2006-09-27 21:30 | elife

# re: [算法问题]合并两个已经排序的数组为另一个数组  回复  更多评论   

设计算法最好参考一下stl,如果不比stl好,就不要拿出来了

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2) {
if (*first2 < *first1) {
*result = *first2;
++first2;
}
else {
*result = *first1;
++first1;
}
++result;
}
return copy(first2, last2, copy(first1, last1, result));
}
2006-09-28 11:58 | 小明

# re: [算法问题]合并两个已经排序的数组为另一个数组  回复  更多评论   

是啊,看题意像是要求内排序的……
2006-09-30 09:50 | 废人

# re: [算法问题]合并两个已经排序的数组为另一个数组  回复  更多评论   

归并排序
2006-10-11 14:53 | 小胡

# re: [算法问题]合并两个已经排序的数组为另一个数组  回复  更多评论   

大傻逼。题目都没看懂
2008-07-03 10:47 | 网友

# re: [算法问题]合并两个已经排序的数组为另一个数组  回复  更多评论   

@小胡
归并排序的执行效率还不及上面高呢!所以应该不是归并排序,再说归并内存开销比上面的大!
2012-06-03 20:41 | 瞎看看

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理