今天偶尔看到了归并排序的算法复杂度证明，对于将几个有序数组合并成一个有序数组的比较次数产生了兴趣。


设有两个有序数组 arr1 与 arr2，数组长度分别为 m 与 n， 要合并成一个长度位 m+n 的有序数组 arr3.


最差情况下：比较次数为 m+n-1
此时，将数组 arr1 与数组 arr2 中的元素两两比较，将值小的放进数组 arr3， 直到数组 arr3 填满为止。
因为 arr3 有 m+n 个空位，每次两两比较就放进去一个数，而最后一个剩下的元素可以不用比较直接放进去，所以一共两两比较了 m+n-1 次。


最好情况下：比较次数为 min{m, n}
有个疑问： 若一个数组为 1， 2，3 ； 另一个数组为 4, 5, 6, 7； 则直接将后一个数组最小的与前一个数组最大的比较，仅需一次比较就行了
一定要注意，这是简单归并排序，必须从第一个元素比。
因此，最好情况下，至少需要两两比较一个数组的长度，比较次数为 min{m,n}


java 代码：

import java.util.Arrays;

public class HelloWorld {
	  static int[] mergeArray(int[] a, int[] b) {
		int k = a.length + b.length;
		int[] c = new int[k];
		int m = 0; int n = 0;
		for (int i = 0; i < k; i++) {
			c[i] = a[m] > b[n] ? b[n++] : a[m++]; // 一共比较了 k-1 次
			
			// 最后一个数单独处理
			if (m == a.length) {
				c[k-1] = b[n];
				break;
			}
			if (n == b.length) {
				c[k-1] = a[m];
				break;
			}
		}
		return c;
	}
	
	
	public static void main(String[] args) {
			int[] a = {3, 6, 8, 10};		
			int[] b = {1, 2, 6, 9};
			
			int[] c = mergeArray(a, b);
			System.out.println(Arrays.toString(c));		
	}
}

学归并排序算法的时候，先要了解归并有序数组。
顺便写个有序单链表的归并

/*有序数组的归并*/
function mergeArr(arr1, arr2) {
	var result = [], 
		arr1_index = 0, 
		arr2_index = 0;
	while(arr1_index < arr1.length &&
		  arr2_index < arr2.length) {
		if(arr1[arr1_index] < arr2[arr2_index]) {
			result.push(arr1[arr1_index]);
			arr1_index++;
		} else {
			result.push(arr2[arr2_index]);
			arr2_index++;
		}
	}

	while(arr1_index < arr1.length) {
		result.push(arr1[arr1_index]);
		arr1_index++;
	}

	while(arr2_index < arr2.length) {
		result.push(arr2[arr2_index]);
		arr2_index++;
	}

	return result;
}


var arr1 = [1, 2, 4, 20, 30];
var arr2 = [0, 9];

//console.log(mergeArr(arr1, arr2));


/*有序单链表的归并*/
function LinkedList() {
	var Node = function (value) {
		this.value = value;
		this.next = null;
	}

	var head = null;
	var length =0;

	this.append = function (value) {
		var node = new Node(value);
		if(head == null) {
			head = node;
			length++;
			return;
		} else {
			appendNode(head, node);
		}
	}

	function appendNode(root, node) {
		if(root.next == null) {
			root.next = node;
		} else {
			appendNode(root.next, node);
		}
		length++;
	}

	this.toString = function () {
		var result = [];
		var temp = head;
		while(temp != null) {
			result.push(temp.value);
			temp = temp.next;
		}

		return result.join(" ");
	}

	this.getHead = function () {
		return head;
	}

	this.getLength = function () {
		return length;
	}
}


function linkedTest() {
	var arr1 = [2, 6, 9, 18, 25];
	var arr2 = [0, 10, 30];
	var linked_list1 = new LinkedList();
	var linked_list2 = new LinkedList();
	for(var i=0; i<arr1.length; ++i) {
		linked_list1.append(arr1[i]);
	}

	for(var i=0; i<arr2.length; ++i) {
		linked_list2.append(arr2[i]);
	}

	console.log("linked list1 ", linked_list1.toString());
	console.log("linked list2 ", linked_list2.toString());

	var merge_list = mergeLinkedList(linked_list1, linked_list2);
	console.log(merge_list.toString());
}


/*单链表合并*/
function mergeLinkedList(list1, list2) {
	var result_list = new LinkedList(),
		list1_node = list1.getHead();
		list2_node = list2.getHead();

	while(list1_node && list2_node) {
		if(list1_node.value < list2_node.value) {
			result_list.append(list1_node.value);
			list1_node = list1_node.next;
		} else {
			result_list.append(list2_node.value);
			list2_node = list2_node.next;
		}
	}

	while(list1_node) {
		result_list.append(list1_node.value);
		list1_node = list1_node.next;
	}

	while(list2_node) {
		result_list.append(list2_node.value);
		list2_node = list2_node.next;
	}

	return result_list;
}

linkedTest();

解题思路 

现省略，具体后边再写，只要熟悉归并算法就不太难。
代码
package FileTest;


public class Test {

    public static int[] arrayMerge(int[] a, int[] b) {
        int[] am = new int[a.length + b.length];
        int ai = 0;
        int bj = 0;

        while ((ai<a.length) && (bj<b.length)) {
            if(a[ai] < b[bj]) {
                am[ai + bj] = a[ai];
                ai++;
            } else {
                am[ai + bj] = b[bj];
                bj++;
            }
        }

        while (ai < a.length) {
            am[ai + bj] = a[ai];
            ai++;
        }

        while (bj < b.length) {
            am[ai + bj] = b[bj];
            bj++;
        }

        return am;

    }

    public static void main(String[] args) {
        int[] a = {0,1,2,3,4,5,6,6};
        int[] b = {1,2,3,4,5,6,7,8,9};
        int[] am = new int[a.length + b.length];
        am = arrayMerge(a, b);
        for (int i=0;i < am.length;i++) {
            System.out.print(am[i] + " ");
        }
    }

}

对于两个有序数组arr1和arr2，arr1的末尾有足够的空间可以容纳arr2。
把arr2的所有数组插入arr1中，使得插入后的数组仍然是个有序数组。
解决思路是从尾到头比较arr1和arr2中的数字的大小，然后将较大的数字插入到相应的位置。
具体代码参考如下：



#include <iostream>
using namespace std;
/*template<class T>     测试模板函数，可以忽略
int getArrayLen(T& arr)
{
    return (sizeof(arr)/sizeof(arr[0]));
}*/

void insertArray(int arr1[],int arr2[],int lastIndexOfArr1, int lastIndexOfArr2)   //传输两个数组以及数组的末尾元素的下标
{
    if(lastIndexOfArr1<0 || lastIndexOfArr2<0)
    {
        return;
    }
    int newIndex=lastIndexOfArr1+lastIndexOfArr2+1;     //两个数组合并到同一个数组之后的尾元素的下标
    int len=newIndex+1;
    while(newIndex>0)                     //循环比较，较大的数字向后插入
    {
        if(arr1[lastIndexOfArr1]>=arr2[lastIndexOfArr2])
        {
            arr1[newIndex--]=arr1[lastIndexOfArr1];
            if(lastIndexOfArr1!=0)
                lastIndexOfArr1--;
        }
        else
        {
            arr1[newIndex--]=arr2[lastIndexOfArr2];
            if(lastIndexOfArr2!=0)
                lastIndexOfArr2--;
        }
        if(newIndex==0)    //比较到最后，最小的数字，插入到数组的0下标位置
        {
            arr1[0]=arr1[0]<arr2[0]?arr1[0]:arr2[0];
        }
    }

    for(int i=0;i<len;i++)
        cout << arr1[i] << " ";
    cout << endl;
}

int main()
{
    int arr1[30]={2,7,9,10,13,18,23,26,30,33};
    int arr2[]={1,3,5,7,9,11,13,15,23,29,31};
    insertArray(arr1,arr2,9,10);
    //cout << getArrayLen(arr1) << endl;  测试template函数模板，可以忽略
    //cout << getArrayLen(arr2) << endl;
    return 0;
}


上述代码主要的思路是从尾向头进行比较，降低复杂度的同时，避免了多次复制同一个数字的情况。