对两个有序数组进行合并

mukekeheart

发布于 2018-02-27 15:32:18

1.2K0

发布于 2018-02-27 15:32:18

文章被收录于专栏：mukekeheart的iOS之旅

问题描述：

　　数组arr[0...mid-1]和arr[mid..n-1]是各自有序的，对数组arr[0..n-1]的两个有序段进行合并，得到arr[0..n-1]整体。要求空间复杂度为O(1)

　　eg：{1，3，5，7，2，4，6}合并成{1,2,3,4,5,6,7}

思路：

方法一

　　很显然，看到这个题目就想到了归并中的合并算法，时间复杂度为O(n)，但是很可惜空间复杂度也是O(n)不满足要求。但是还是作为一种解决方案提出来吧，具体实现代码就不列了。

方法二

　　此外，对于部分有序的我们能想到的是插入排序，但是本题是两段部分有序合并在一起，进行插入排序的话时间复杂度也是O(n2)，空间复杂度满足条件。

方法三

　　本方法的思路有点类似简单排序的，具体思路如下：

遍历数组中下标为0~mid-1的元素，将遍历到的元素的值与arr[mid]比较，若arr[i]大于arr[mid]，则交换，即第i次排序，将其最右边的最小的值放到arr[i]的位子上，
然后在后半段中将arr[mid]排序到正常的位置上去。

 1 　　public static void merge(int [] arr,int mid){
 2         int len = arr.length ;
 3         int temp ;
 4         for(int i = 0 ; i < mid ; i++){
 5                 if(arr[i] > arr[mid]){
 6                 temp = arr[i] ;
 7                 arr[i] = arr[mid] ;
 8                 arr[mid] = arr[i] ;
 9             }
10             
11             for(int j = mid + 1 ; j < len ; j++){
12                 if(arr[j] < arr[j-1]){
13                     temp = arr[j] ;
14                     arr[j] = arr[j-1] ;
15                     arr[j-1] = arr[j] ;
16                 }else{                    
17                     break ;
18                 }
19             }
20         }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-08-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法