数据�l�构�W�五章算法设计题[14]_跨考网

       1�Q�已知两个定长数�l�，它们分别存放两个非降序有序序列，��L(f��ng)��写程序把�W�二个数�l�序列中的数逐个插入到前一个数�l�序列中�Q�完成后两个数组中的数分别有序（非降序）�q�且�W�一数组中所有的数都不大于第二个数组中的��L��一个数。注意，不能另开辟数�l�，也不能对��L��一个数�l�进行排序操作。例如，

　　�W�一个数�l��ؓ(f��)�Q?/span>4,12,28

　　�W�二个数�l��ؓ(f��)�Q?/span>1,7,9,29,45

　　输出�l�果为：(x��)1,4,7--------------�W�一个数�l?/span>

　　9,12,28,29,45---------�W�二个数�l�　　　�?a target="_blank">上�v大学 1998 �?/span> �Q?/span>20分）�?/span>

　　【参考答案�?/span>

　　[题目分析] 题目要求调整后第一数组�Q?/span>A�Q�中所有数均不大于�W�二个数�l�（B�Q�中所有数。因两数�l�分别有序，�q�里实际是要求第一数组的最后一个数A[m-1]不大于第二个数组的第一个数B[0]。由于要求将�W�二个数�l�的数插入到�W�一个数�l�中。因此比�?/span>A[m-1]�?/span>B[0]�Q�如A[m-1]>B[0]�Q�则交换。交换后仍保�?/span>A�?/span>B有序。重复以上步骤，直到A[m-1]<=B[0]为止�?/span>

　　void ReArranger (int A[],B[],m,n)

　　//A�?/span>B是各�?/span>m个和n个整数的非降序数�l�，本算法将B数组元素逐个插入�?/span>A中，�?/span>A中各元素均不大于B中各元素�Q�且两数�l�仍保持非降序排列�?/span>

　　{ while (A[m-1]>B[0])

　　{x=A[m-1];A[m-1]=B[0]; //交换A[m-1]�?/span>B[0]

　　j=1;

　　wkile(j<n && B[j]<x) B[j-1]=B[j++]; //��L��A[m-1]的插入位�|?/span>

　　B[j-1]=x;

　　x=A[m-1];i=m-2;

　　wkile(i>=0 && A[i]>x) A[i+1]=A[i--]; //��L��B[0]的插入位�|?/span>

　　A[i+1]=x;

　　}

　　}���法�l�束