两集合求交集的算法比较(转)

看到一个比较优的解答是 

Arrays.sort(array_1);  
Arrays.sort(array_2);  
int len = array_1.length  
for (int i = 0; i < len; i++)  
{  
 if (Arrays.binarySearch(array_2, array_1[i]) != -1)  
      print array_1[i];  
 }  

　　排序后，这个算法的复杂度是: M*log2N 

数据结构中有个已排序的两集合求并集的例子。稍微改造: 

var a=[1,3,5,3,2,4,8];
var b=[6,5,3,7,9,2];
Array.sort(a);
Array.sort(b);
for(var indexA=0,lenA=a.length, indexB=0,lenB=b.length; indexA<lenA && indexB<lenB;  ) {
        if(a[indexA] == b[indexB]) {
              document.writeln(a[indexA] + "<br>");
               indexA++;
                indexB++;
          }
        else if (a[indexA] < b[indexB]) {
            indexA++;
        }
        else {
            indexB++;
        }    
}

　　这个算法的排序后的复杂度M+N. 

转自http://ihavegotyou.iteye.com/blog/524693