java 两个有序数组合并到一个有序数组(时间复杂度低)

青旅半醒 2022-04-08 08:44 183阅读 0赞

默认一般会采用数组先合并，在排序

时间复杂度会在o(n) -o(n\*n) 之间

我想了个其他的思路 对数组1 和数组2 元素从头开始进行一次对比，小的放入结果集合，

直到两个数组的元素都加入结果集合

这样的时间复杂度 在o(n) 只要比较两个数组较短的长度的次数

代码

import java.util.ArrayList;
    
    /**
     * 两个有序数组合并到 一个新排序数组
     * @version   
     * @author flyer 2018年12月6日下午1:20:28
     * @since 1.8
     */
    class QuickSort {
    
        public static void main(String[] agrs) {
    
            int a[] = { 1, 3, 8 };
            int b[] = { 2, 6, 6, 10, 15 };
            //生产的处理结果的数组
            ArrayList<Integer> t = new ArrayList<>();
            //查看a数组里面处理到的位置
            int ak = 0;
            //查看b数组里面处理到的位置
            int bk = 0;
            //a数组里面元素是否都已经被处理
            boolean isAOk = false;
            boolean isBOk = false;
            //a ,b数组都已经处理结束
            boolean isOk = false;
            while (!isOk) {
                if (!isAOk && a[ak] <= b[bk]) {
                    t.add(a[ak]);
                    System.out.print(a[ak]);
                    if (ak < a.length - 1)
                        ak++;
                    else {
                        isAOk = true;
                        //a处理完，直接把b数组剩下的加进去即可
                        for (int tmp = bk; tmp < b.length; tmp++) {
                            t.add(b[tmp]);
                            System.out.print(b[tmp]);
                        }
                        //a,b都处理完 程序结束
                        isOk = true;
                    }
                }
                else if (!isBOk && a[ak] > b[bk]) {
                    t.add(b[bk]);
                    System.out.print(b[bk]);
                    if (bk < b.length - 1)
                        bk++;
                    else {
                        isBOk = true;
                        for (int tmp = ak; tmp < a.length; tmp++) {
                            t.add(a[tmp]);
                            System.out.print(a[tmp]);
                        }
                        isOk = true;
                    }
                }
            }
            System.out.println(" result:");
            for (int i = 0; i < t.size(); i++) {
                System.out.print(t.get(i) + " ");
            }
        }
    
    }