首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 服务器 > 云计算 >

碰到一个合并排序算法情帮忙大家解决上

2013-01-04 
碰到一个合并排序算法情帮忙大家解决下。都已经排序好的两个数组。把两个数组合并,那个算法对新数据做排序是

碰到一个合并排序算法情帮忙大家解决下。
都已经排序好的两个数组。
把两个数组合并,那个算法对新数据做排序是最快的。
[解决办法]
归并排序啊,这一步骤是O(n)的

原理其实很简单,你有两打排好的扑克,
你第一次次各抽一张,比较大小,把这两张放在桌子上.
然后再各抽一张,,比较大小,把这两张放在原先两张的两端.
重复上面步骤,直到有一打见底,把另一打直接放桌子上.

这就是Merge函数的原理.
需要开辟两个链表做这个事情.
[解决办法]
各抽一张,是从最上面拿,不是从里边拿.

算法导论上有这段,有图的


public static void merge(ArrayList<Integer> A, int p, int q, int r) {   
36.        //length of the child array   
37.        int n1 = q - p + 1;   
38.        int n2 = r - q;   
39.        //create arrays L[1...n1 + 1] and R[1...n2 + 1]   
40.        ArrayList<Integer> L = new ArrayList<Integer>(n1 + 1);   
41.        ArrayList<Integer> R = new ArrayList<Integer>(n2 + 1);   
42.        for(int i = 0; i < n1; i ++) {   
43.            L.add(A.get(p + i));   
44.        }   
45.        L.add(max);   
46.           
47.        for(int i = 0; i < n2; i ++) {   
48.            R.add(A.get(q + i + 1));   
49.        }   
50.        R.add(max);   
51.           
52.        for (int i = 0, j = 0, k = p; k <= r; k ++) {   
53.            if (L.get(i) <= R.get(j)) {   
54.                A.set(k, L.get(i));   
55.                i ++;   
56.            } else {   
57.                A.set(k, R.get(j));   
58.                j ++;   
59.            }   
60.        }   
61.    }   


[解决办法]
时间复杂度cnlog2n + cn 为 O(nlog2n)
------解决方案--------------------


归并排序~~数据多就多路归并

热点排行