[算法笔记]合并有序的两个数组

　　问题：数组a1[0, mid-1]和a1[mid,num-1]都分别有序。将其merge成有序数组a1[0,num-1]，要求空间复杂度为O(1),时间复杂度为O(n).

　　问题来自：http://blog.csdn.net/column/details/ms100.html

　　这个问题的关键点就是在于：如何降低空间复杂度。解决关键：考虑左边数组与右边数组交换元素的个数。若左边数组在交换过程中，还有剩余元素没有交换。也就是说，左边数组剩余数组元素还是大于已交换元素的。

　　例如， { 1, 2, 23, 24, 36, 74, 7, 10, 12, 38, 44, 84 }， mid = 6

　　交换代码如下：　

1 if ( order_array[lhs_index] > order_array[rhs_index] )
2 {
3     swap_int( order_array + lhs_index, order_array + rhs_index );
4     ++rhs_index;
5 }
6 
7     ++lhs_index;

　　在交换过程中，交换了3个元素，即{23, 24, 36}与{7,10,12}。

　　原数组就变成：{1, 2,7,10,12, 74,23, 24, 36，38, 44, 84}

　　如果继续使用上述代码进行交换，则导致最终结果不正确。即{1, 2,7,10,12,38,23,24,36,44,74,84}

　　因此，需要在交换过程中统计已经交换的个数，当左边的所有元素均交换到右边以后才算结束。

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 void swap_int( int *lhs, int *rhs )
  5 {
  6     int tmp = *lhs;
  7     *lhs = *rhs;
  8     *rhs = tmp;
  9 }
 10 
 11 /**<  usually used. time: O(n); space: O(n) */
 12 int merge_array_usual( int *order_array,
 13                        int array_size,
 14                        int split_point )
 15 {
 16     int lhs_index = 0,
 17         rhs_index = split_point,
 18         *merged_array = NULL,
 19          merged_index = 0;
 20 
 21     /**< check argument. */
 22     if ( NULL == order_array || array_size <= 0
 23             || split_point < 0 || split_point >= array_size )
 24     {
 25         fprintf( stderr, "merge_array_usual: error for argument.\n" );
 26         return -1;
 27     }
 28 
 29     /**< allocate memory */
 30     merged_array = (int *) calloc( array_size, sizeof(int) );
 31     if ( NULL == merged_array )
 32     {
 33         fprintf( stderr, "merge_array_usual: out of memory.\n" );
 34         return -1;
 35     }
 36 
 37     /**< inserted element */
 38     while ( lhs_index < split_point && rhs_index < array_size )
 39     {
 40         if ( order_array[lhs_index] <= order_array[rhs_index] )
 41         {
 42             merged_array[merged_index++] = order_array[lhs_index++];
 43         }
 44         else
 45         {
 46             merged_array[merged_index++] = order_array[rhs_index++];
 47         }
 48     }
 49     /**< remainint element */
 50     while ( lhs_index != split_point )
 51     {
 52         merged_array[merged_index++] = order_array[lhs_index++];
 53     }
 54     while ( rhs_index != array_size )
 55     {
 56         merged_array[merged_index++] = order_array[rhs_index++];
 57     }
 58 
 59     /**< copy back */
 60     for ( lhs_index = 0; lhs_index < array_size; ++lhs_index )
 61     {
 62         order_array[lhs_index] = merged_array[lhs_index];
 63     }
 64 
 65     /**< free memory and set pointer to null. */
 66     free( merged_array );
 67     merged_array = NULL;
 68 
 69     return 0;
 70 }
 71 
 72 /**<  optimize */
 73 int merge_array_opt( int *order_array,
 74                      int array_size,
 75                      int split_point )
 76 {
 77     int lhs_index       = 0,
 78         rhs_index       = split_point,
 79         swap_cnt        = 0,
 80         is_done         = 0,
 81         tmp_cnt         = 0;
 82 
 83     /**< check argument. */
 84     if ( NULL == order_array || array_size <= 0
 85             || split_point < 0 || split_point >= array_size )
 86     {
 87         fprintf( stderr, "merge_array: error for argument.\n" );
 88         return -1;
 89     }
 90 
 91     /**< if moved elements is less than remaining */
 92     while ( is_done == 0 )
 93     {
 94         /**< in left, which number is more than order_array[rhs_index] */
 95         for ( ; lhs_index < rhs_index
 96                 && order_array[lhs_index] <= order_array[rhs_index];
 97                 ++lhs_index );
 98 
 99         /**< in right, which number is more than order_array[lhs_index] */
100         for ( swap_cnt = 0; rhs_index < array_size
101                 && order_array[rhs_index] <= order_array[lhs_index];
102                 ++rhs_index, ++swap_cnt );
103 
104         /**< if lhs_index + swap_cnt > split_point, is over. */
105         if ( (lhs_index + swap_cnt) > split_point )
106             is_done = 1;
107 
108         /**< swap element */
109         tmp_cnt = swap_cnt;
110         rhs_index -= swap_cnt;
111         while ( tmp_cnt-- )
112         {
113             swap_int( order_array + rhs_index, order_array + lhs_index );
114             ++rhs_index;
115             ++lhs_index;
116         }
117 
118         /**< PS. reset rhs_index */
119         rhs_index -= swap_cnt;
120     }
121 
122     return 1;
123 }
124 int main()
125 {
126     int order_array[] = {  1, 2, 23, 24, 36, 74, 7, 10, 12, 38, 44, 84 };
127     int split_point = 6,
128         array_size  = 0;
129 
130     array_size = sizeof( order_array ) / sizeof( int );
131     merge_array_opt( order_array, array_size, split_point );
132 
133     printf( "\nElements is \n" );
134     for ( split_point = 0; split_point < array_size; ++split_point)
135     {
136         printf( " %d", order_array[split_point] );
137     }
138     printf( "\n" );
139 
140     return 0;
141 }

View Code

　　欢迎大家指导！！

[算法 笔记]合并有序的两个数组

推荐阅读

[算法笔记]合并有序的两个数组