以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  大家看看这道题怎么解(ds)  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=38589)

--  作者：jianzhentianxia
--  发布时间：10/6/2006 5:40:00 PM

--  大家看看这道题怎么解(ds)
设a[0:k]和a[k+1:n-1]已排好序。设计一个合并算法使a[0:n-1]有序。要求时间复杂度O(n)，空间复杂度O(1).
--  作者：runningwulf
--  发布时间：10/6/2006 10:49:00 PM

--  
两路的归并？
呵呵，我刚看了一遍书，还都没复习呢，是不是这样？
--  作者：mxf3306
--  发布时间：10/9/2006 6:17:00 PM

--  
public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public void merge(int a[]) {
        int length = a.length;
        int start2 = 0;
        int start3 = length / 2;
        int start4 = length / 2;

        while (length > 1 && start4 < a.length) {
            int theSmallestOf3 = theSmallestOf3(a, start2, start3, start4);
            if (theSmallestOf3 == start2) {
                start2++;
            } else if (theSmallestOf3 == start4) {
                swap(a, start2, start4);
                start4++;
                start2++;
            } else {
                int temp = a[start2];
                a[start2] = a[start3];
                start2++;
                for (int i = start3; i < start4; i++) {
                    a[i] = a[i + 1];
                }
                a[start4 - 1] = temp;
            }
            if(start2 == start3){
                start3 = start4;
                length = a.length - start2;
            }
        }
    }

    public int theSmallestOf3(int a[], int start2, int start3, int start4) {
        int min = start2;
        if (a[min] > a[start3])
            min = start3;
        if (a[min] > a[start4])
            min = start4;
        return min;
    }

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 46.875ms