寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

提交1：
先把两个数组合并成一个，然后通过冒泡排序给数组排序，最后找到中位数。
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] array;
        
        if(nums1.length == 0){
            array = nums2;
        }else if(nums2.length == 0){
            array = nums1;
        }else{
            array = new int[nums1.length + nums2.length];
            
            for(int i = 0;i < nums1.length;i++){
                array[i] = nums1[i];
            }
            for(int i = 0;i < nums2.length;i++){
                array[nums1.length + i] = nums2[i];
            }
            array = sort(array);
        }
        
        if(array.length % 2 == 0){
                return (array[array.length / 2 - 1] + array[array.length / 2]) / 2.0;
            }else{
                return (array[array.length / 2 ]);
            }
    }
    
    private int[] sort(int[] nums){
        int temp;
        for(int i = 0;i < nums.length;i++){
            for(int j = i + 1;j < nums.length;j++){
                if(nums[i] > nums[j]){
                    temp =nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        return nums;
    }
}

提交2:
先对数组1和数组2排序，然后依次遍历两个数组，按从小到大的顺序放到新数组里，取出中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] array = new int[nums1.length + nums2.length];
        nums1 = sort(nums1);
        nums2 = sort(nums2);
        
        int i = 0;
        int j = 0;
        int index = 0;
        while(i < nums1.length && j< nums2.length){
            if(nums1[i] < nums2[j]){
                array[index] = nums1[i];
                i++;
            }else{
                array[index] = nums2[j];
                j++;
            }
            index++;
        }
        
        if(i == nums1.length && j == nums2.length){
            
        }else if(i == nums1.length){
            for(int k = j;k < nums2.length;k++,index++){
                 array[index] = nums2[k];
            }
        }else if(j == nums2.length){
            for(int k = i;k < nums1.length;k++,index++){
                 array[index] = nums1[k];
            }
        }
        
        
        if(array.length % 2 == 0){
            return (array[array.length / 2 - 1] + array[array.length / 2]) / 2.0;
        }else{
            return (array[array.length / 2 ]);
        }
    }
    
    private int[] sort(int[] nums){
        int temp;
        for(int i = 0;i < nums.length;i++){
            for(int j = i + 1;j < nums.length;j++){
                if(nums[i] > nums[j]){
                    temp =nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        return nums;
    }
}

提交3：
将提交1的排序改为快速排序
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] array;
        
        if(nums1.length == 0){
            array = nums2;
        }else if(nums2.length == 0){
            array = nums1;
        }else{
            array = new int[nums1.length + nums2.length];
            
            for(int i = 0;i < nums1.length;i++){
                array[i] = nums1[i];
            }
            for(int i = 0;i < nums2.length;i++){
                array[nums1.length + i] = nums2[i];
            }
            sort(array,0,array.length-1);
        }
        
        if(array.length % 2 == 0){
                return (array[array.length / 2 - 1] + array[array.length / 2]) / 2.0;
            }else{
                return (array[array.length / 2 ]);
            }
    }
    
    private void sort(int[] arr,int _left,int _right){
        int left = _left;
        int right = _right;
        int temp = 0;
        if(left <= right){   //待排序的元素至少有两个的情况
            temp = arr[left];  //待排序的第一个元素作为基准元素
            while(left != right){   //从左右两边交替扫描，直到left = right

                while(right > left && arr[right] >= temp)  
                     right --;        //从右往左扫描，找到第一个比基准元素小的元素
                  arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换

                while(left < right && arr[left] <= temp)
                     left ++;         //从左往右扫描，找到第一个比基准元素大的元素
                  arr[right] = arr[left];  //找到这种元素arr[left]后，与arr[right]交换

            }
            arr[right] = temp;    //基准元素归位
            sort(arr,_left,left-1);  //对基准元素左边的元素进行递归排序
            sort(arr, right+1,_right);  //对基准元素右边的进行递归排序
        } 
    }
    
}