起一个记录性的作用。
 
设有两个有序数组 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}
 
例题：
 

合并有序数组
 
题：给定两个排序后的数组A和数组B，其中A的末端有足够的缓冲空间容纳B，编写一个方法，将B合并到A并排序
 思路：参照归并排序
 
对A数组进行从后往前进行填充
A和B数组两两比较，大的数填到A中
 
 
public static void main(String[] args) {
		int[] arr = new int[20];
		for(int i=0; i<10; i++) {
			arr[i]=i;
		}
		int[] arr01 = {10,12,13,18};
		sortAB(arr,arr01,10);
		for(int i=0; i<10+arr01.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
	
	public static void sortAB(int[] A, int[] B, int aLen){
		int p = 10+B.length-1; 
		int pA = A.length-1;
		int pB = B.length-1;
		while(pA>=0 && pB>=0) {
			if(A[pA]>=B[pB]) {
				A[p--]=A[pA--];
			}else {
				A[p--]=B[pB--];
			}
		}
		while(pB>=0) {
			A[p--]=B[pB--];
		}
		
	}

对于两个有序数组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;
}

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

 
 

 

今天写个简简单单的归并排序。顺带个合并两个有序数组。
 
先来合并两个有序数组
 
#include<iostream>
#include<vector>

vector<int> mergeTwoArray(vector<int> arr1, vector<int> arr2)
{
	if(arr1.size()==0 && arr2.size()==0) 	//判断入参是否为空
	{
		return;
	}
	if(arr1.size()==0)				//arr1为空的话，直接返回arr2
		return arr2;
	if(arr2.size()==0)
		return arr1;
		
	vector<int> arr;		//定义一个存放结果的容器
	int i=0,j=0;
	while(i<arr1.size() && j<<arr2.size())		//遍历两个vector的共同长度
	{
		if(arr1[i] <= arr2[j])					
		{
			arr.push_back(arr1[i]);
			i++;
		}
		else
		{
			arr.push_back(arr2[j]);
			j++;
		}
	}
	if(i==arr1.size())							//a==arr1.size()说明arr1已经走到了末尾。直接追加arr2容器到最终的结果容器中即可
	{
		while(j < arr2.size())
		{
			arr.push_back(arr2[j]);
			j++;
		}
	}
	else
	{
		while(i < arr1.size())
		{
			arr.push_back(arr1[i]);
			i++;
		}
	}
	
	return arr;
}


 
前面的博客中有其他排序，接下来。对某个数组进行归并排序,直接上代码说
 
#include<iostream>
#include<vector>

void mergeSort(vector<int> arr)
{
	//第一步肯定还是做入参判断啦
	if(arr.size() == 0)
	{
		return;
	}
	if(arr.size() == 1)
	{
		return arr;
	}
		
	const length = arr.size();
	int mid = length / 2;

	vector<int> arr1(arr.begin(), arr.begin()+mid);		//左半边构建一个vector
	vector<int> arr2(arr.begin()+mid, arr.end());		//右半边构建一个vector

	//注意：先执行括号里面的mergeSort函数，当然，这里是递归调用。
	//直至拿到返回值(都只含有一个元素)vector时再调用，最上面函数块的mergeTwoArray方法
	return mergeTwoArray(mergeSort(arr1), mergeSort(arr2));		
}