排序算法问题 已知两个已经排好序的数组， 怎样快速找到这两组数的中位数？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package test;
import java.util.Arrays;
import java.util.Comparator;
public class JButtonTest
{
public static void main ( String[] args )
{
int[] arr1 = { 3, 1, 23 };
int[] arr2 = { 27, 7, 2 };
String temp = Arrays.toString (arr1) + Arrays.toString (arr2);
temp = temp.replaceAll ("\\]\\[", ",").replaceAll ("\\s", "").replaceAll ("[\\[\\]]", "");
String[] result = temp.split ("\\,");
System.out.println (Arrays.toString (result));
Arrays.sort (result, new Comparator ()
{
@Override
public int compare ( String o1, String o2 )
{
int a = Integer.parseInt (o1), b = Integer.parseInt (o2);
if (a > b)
{
return 1;
}
else if (a < b)
{
return -1;
}
else
{
return 0;
}
}
});
System.out.println (Arrays.toString (result));
}
}
这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下：
bool findcommon(int a[],int size1,int b[],int size2)
{
int i;
for(i=0;i<size1;i++)
{
int start=0,end=size2-1,mid;
while(start<=end)
{
mid=(start+end)/2;
if(a[i]==b[mid])
return true;
else if (a[i]<b[mid])
end=mid-1;
else
start=mid+1;
}
}
return false;
}
后来发现有一个 O(n)算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进 。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。
bool findcommon2(int a[], int size1, int b[], int size2)
{
int i=0,j=0;
while(i<size1 && j<size2)
{
if(a[i]==b[j])
return true;
if(a[i]>b[j])
j++;
if(a[i]<b[j])
i++;
}
return false;
}
这个问题的关键在于给定 k，怎样找到 A 和 B 合并后的第 k 大元素。我们可以这样做：
1. 把 A 平均分为前后两个部分，前部分有 x 个元素，后部分有 n1-x 个元素（由于 A 是有序的，所以后一部分的所有元素大于前一部分）。A[x] = A的后一部分的第一个元素。
2. 同理把 B 也平均分成前后两个部分，前部分有 y 个元素，后部分有 n2-y 个元素。B[y] = B的后一部分的第一个元素。
3. 由于两个数组都是被平均分割的，所以可以近似地认为 x = n1/2, y = n2/2。
这里不妨设 A[x] <= B[y]（如果 A[x] > B[y] 处理过程和下面类似）：
=============================== 情况1 ============================
由于在 A 中，A[x] 前面有 x 个元素，在 B 中，B[y] 前面有 y 个元素，并且又有 A[x] <= B[y]，那么，合并以后，A[x]前面原来那些元素必然也在B[y]前面，也就是说，B[y]前面至少会有 x + y 个元素，我们再规定如果 A, B 中有相同元素，则合并后 A 中的元素排在 B 前面，那么归并以后 A[x] 也会排在 B[y] 前面，于是乎合并之后 B[y] 至少有 x+y+1 个元素。
如果 k <= x+y+1，也就是说，合并后第 k 大的元素必然落在 B[y] 前面。所以，原来在 B 数组中，第二部分（B[y]以及 B[y] 之后）那些元素都不可能包含我们要找到内容（第 k 大元素），所以我们可以把他们排除掉。这样就排除了 B 中一半的内容。
=============================== 情况2 ============================
在 A 中，A[x] 及其后面有 n1-x 个元素，除去 A[x] 之后有 n1-x-1 个元素，B[y] 及其后面有 n2-y 个元素。那么，由于 A[x] <= B[y]，所以合并起来之后，B[y] 后面那些元素必然也在 A[x] 后面，则合并后 A[x] 后面至少有 (n1-x-1) + (n2-y) = (n1+n2)-(x+y+1) 个元素。
如果 k > x+y+1，也就说，合并后第 k 大的元素必然落在 A[x] 后面。所以，原来在 A 数组中，第一部分（A[x]之前）以及 A[x] 都不可能包含我们要找的元素，所以我们可以把他们排除掉。这样就排除了 A 中一半的内容。
============================ 下面是总结 ===========================
综上所诉，对于 k <= x+y+1 还是 k > x+y+1 我们都提出了解决的方案，并且每种方案都能把 A 或者 B 的规模减小一半。减小了一半之后，我们将其作为一个新的问题继续使用上面的算法处理，直到 A 或者 B 减小到足够小：
1. A没有了，这样只需要找出 B 中第 k 大的元素，也就是 B[k].
2. B没有了，同上结果就是 A[k].
达到以上两个条件的任意一个分别只需要 O(logn1) 和 O(logn2) 的时间，所以最坏情况下这个算法只需要 O(logn1 + logn2) 就能得出结果。
============================ 下面是程序 ===========================
以下是基于这个算法的程序，具体实现是在 element_at 这个函数中，通过调用 element_at(0, n1-1, 0, n2-1, k) 可返回 A, B 数组合并后第 k 大的元素。
#include <stdio.h>
int n1, n2;
int A[1000];
int B[1000];
int element_at(int l1, int r1, int l2, int r2, int k) {
int x = (l1 + r1) / 2, y = (l2 + r2) / 2;
if (l1 > r1) return B[l2+k-1];
if (l2 > r2) return A[l1+k-1];
if (A[x] <= B[y]) {
if (k <= (x - l1) + (y - l2) + 1) {
return element_at(l1, r1, l2, y-1, k);
} else {
return element_at(x+1, r1, l2, r2, k-(x-l1)-1);
}
} else {
if (k <= (x - l1) + (y - l2) + 1) {
return element_at(l1, x-1, l2, r2, k);
} else {
return element_at(l1, r1, y+1, r2, k-(y-l2)-1);
}
}
return 0;
}
int main() {
int i;
printf("请输入A的大小：");
scanf("%d", &n1);
printf("请输入%d个数，以空格隔开：",n1);
for (i = 0; i < n1; i++) scanf("%d", &A[i]);
printf("请输入B的大小：");
scanf("%d", &n2);
printf("请输入%d个数，以空格隔开：",n2);
for (i = 0; i < n2; i++) scanf("%d", &B[i]);
if ((n1 + n2) & 1) {
printf("中位数是：%d\n", element_at(0, n1-1, 0, n2-1, (n1+n2)/2+1));
} else {
printf("中位数是：%lf\n", (element_at(0, n1-1, 0, n2-1, (n1+n2)/2) + element_at(0, n1-1, 0, n2-1, (n1+n2)/2+1)) / 2.0);
}
return 0;
}
假设两个数组叫A 和B，合并后数组叫C
1）merge sort A, B -->C
2) K_lement(C)
搞定
妫亲新天： 这个比较不好讲清楚,先假设 A 和 B 都是升序的.这个问题的关键在于给定 k,怎样找到 A 和 B 合并后的第 k 大元素.我们可以这样做:1. 把 A 平均分为前后两个部分,前部分有 x 个元素,后部分有 n1-x 个元素(由于 A 是有序的,所以后一...
武义县18411806138： 已知两个包含n及m个记录的排好序的文件能在O(n+m)时间内合并为一个包含n+m个记录的排好序的文件.当有多只求算法(详细)已知两个包含n及m个记录... - ？
妫亲新天：[答案] 当a为(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)恰好为九十m>n && m != -n; 因为ROLL出来的m,n必须大于0,那么只要m>n即可;
武义县18411806138： 设计一个函数将两个已排好序的数组(都已是升序)重组成一个有序的数组.？
妫亲新天： //下面就是排序函数,其中a,b代表两个数组,len1和len2分别是它们的长度 //c是用来存放重组后的数的数组,返回值为重组后的数组长度 int sort(int *a,int len1,int *b,int len2,int *c) { int i=0,j=0,k=0; while(i!=len1&&j!=len2) if(a[i]<b[j]) c[k+...
武义县18411806138： 如何用C++合并两个已经排好序的数组为一个数组 - ？
妫亲新天： 首先用两个指针a,b分别指向第一个和第二个有序的数组,用另一指针pt指向存放答案的数组;若(*a)>(*b)则b++,(*pt++)=(*b),否则a++,(*pt++)=(*a);若a与b都指向已知有序数组末尾的下一位,算法结束.
武义县18411806138： 两个已经排好顺序的数组a和数组b,并将比较后的数组从大到小排序,在进行大小比较时候,有两种比较思路 - ？
妫亲新天： 其实最优思路只有一种:1、现将a、b排好序的两数组变为从大到小顺序;(已经是这个顺序的可省去此步骤)2、合并a、b得到c,使c元素仍然从大到小(不允许合并后再排序).
武义县18411806138： 不要调用api ,两个已经排序的数组如何合并成一个新的有序数组 - ？
妫亲新天： #include <stdio.h>void DisplayArray(int *pArray, int nLen) { for (int i = 0; i < nLen; ++i) { printf(＂array[%d] = %dn＂, i, pArray[i]); } }// pArray1和pArray2是已经排好序的数组,要求将它们按照顺序合并到pArray中 // 排序之后的数组不会...
武义县18411806138： C语言关于归并排序的问题,高分等待？
妫亲新天： 关于这个问题,1.这个方法是把两组已经排好序的元素合并成一组新的排好序的元素.首先要把原本的元素不断分成两堆,直到每一堆只有0到1个元素.然后将这些小堆的元素两两按照顺序合并,然后再把这些新的堆继续两两合并,直至合并完.2.这个算法的比较次数不是最少的,但是最稳定的,并不比快速排序要少.3.冒泡算是最慢的方法之一.
武义县18411806138： 归并排序merge sort是高效的排序算法,写出对两个已经排好序的数组20,14,10,2和12,11,9,1的合并过程 - ？
妫亲新天： //A保存合并后的结果,A.length=B.length+C.length//B,C待合并的数组//为了过程简单,可以在B,C最后各加一个哨兵merge(B,C){ //定义一个新数组A,其长度为B,C长度之和 A.length=B.length+C.length; B[B.length+1]=x;//x为一个小于所有元素的数 C[C.length+1]=x; j=1; k=1; for(i=1;i<=A.length;i++){ if(j<=B.length && B[j]>C[k]) A[i]=B[j++]; else A[i]=C[k++]; }}
武义县18411806138： 在一组已经排序好的数据中确定某一个数据个位置,最佳算法是 - ？
妫亲新天： 既然已经排好序了 那么直接可以进行二分查找. 比如你的序列是从小到大排的,你要找的数据是k (1)另left=开头的位置,right=结束的位置 (2)取一个中间的位置mid (3)如果当前位置的数等于k,则k的位置找到了 (4)如果中间的位置数大,表示k在前半部分,另right=mid-1,继续重复(2)查找. (5)如果中间的位置数小,表示k在后半部分,另left=mid+1,继续重复(2)查找. 当然,这中间要是left>right了,就表示不存在这个数了 时间复杂度O(logn),没有多次查找等特殊要求的话,应该是最快的了.
