归并算法

1.在解释算法优缺点的时候，首先要提到2点，一是比较的次数，二是数据要改变或移动的次数。第一个比较好理解，那什么叫改变和移动的次数呢？比如说2这个数据在存储上存储的是10，如果现在2变成4，那么存储就变成了100，这个过程需要将2向左移动一位，那么就叫移动一次，如果是2变成8，那么就需要移动2次。在实际运算过程中不会考虑这么细致。

2.归并算法是排序算法中的第五种，前四种依次是：冒泡，选择，插入，快速。

3.归并的核心思想是分治。分治顾名思义就是分开治理，假设一个问题，有若干个小问题组成，那么分治就是先逐个击破每个小问题。(有点解高中物理，数学题的感觉)

4.归并算法的解释语言解释：如果你在网上去找一些归并算法的资料学习，那么你可能要茫然到最后不得不靠着阅读代码才能真正理解。所以有必要正真的用文字来描述下归并的全过程，毕竟直接阅读代码是晦涩难懂的。

假设一组数据有8个，一开始将这8个数据两两一组分成4组，然后对每组进行排序，这个地方叫做分治。然后第二次是将8个数据分成两组，每组4个数据，其中这4个数据分别是前两个和后两个已经有序，所以接下来的处理就是按照从左到右的顺序一个一个取出两组有序数据比较排列成一个有序数组，这个数组有4个数据。另外一边4个数据也是同样操作。这样就得到了一个左边和右边都有4个有序数据的数组，再按照以上操作，将这两组数据归并。

5.java代码
package algorithm.merge;

public class Merge {

	public static void main(String[] args) {
		int[] a = new int[]{4, 3, 6, 1, 2, 5, 8, 7};
        mergeSort(a, 0, 1);
        for (int i = 0; i < a.length; ++i) {
            System.out.print(a[i] + "　");
        }
	}
	/**
	 * 目的是将两个有序列表归并成一个有序表,这是一个分治点
	 * start 第一个有序表的起始索引
	 * mid  第二个有序表的起始索引
	 * end  第二个有序表的结束索引
	 */
	public static void merge(int[] target,int start,int mid,int end){
		int[] temp = new int[end-start+1];//一个临时数组，用来存储两个归并好的有序列表
		int indexS = start;//第一个有序表的索引
		int indexM = mid;//第二个有序表的索引
		int indexT = 0;//temp数组的索引
		//将两个有序表排列成一个有序表，直到其中的一个表数据取完，这时候将另一个表的剩余数据，一次添加到temp的尾部。
		while(indexS<mid && indexM<=end){
			if(target[indexS]<target[indexM]){
				temp[indexT++] = target[indexS++];
			}else{
				temp[indexT++] = target[indexM++];
			}
		}
		//如果第一个表还有数据
		while(indexS<mid){
			temp[indexT++] = target[indexS++];
		}
		//如果第二个表还有数据
		while(indexM<=end){
			temp[indexT++] = target[indexM++];
		}
		//将temp替换到原来target数组,从start的往后拷贝temp.length个数据
		//这个arraycopy方法是native修饰的，也就是说这个方法是从内存上直接copy的，效率特别高
		System.arraycopy(temp, 0, target, start, temp.length);	
	}
	/**
	 * length 每次归并的列表长度，开始为1
	 * 从0开始,
	 * 下面的例子按照8个长度数组举例子
	 */
	public static void mergeSort(int[] target,int start,int length){
		int size = target.length;//target数组总长度，用于计算分组数
		//例如第一次归并长度为1，那么就需要将数组分为4组，每组2个数据归并，所以将length向左移1位，也就是乘以2
		int group = size/(length<<1);//向下取整机制，假设是9个数，那么也是4组，就造成第9个数组未参与排序
		//当length==8的时候，那么group就等于0，此时结束算法(递归结束);
		if(group==0){
			return;
		}
		//循环将group组数据归并
		for(int i=0;i<group;++i){
			int s = i * 2 * length;
			//递归调用merge排序
			//当i=0时候merge(target,0,1,2);
			//当i=1时候merge(target,2,3,4);
			//当i=2时候merge(target,4,5,6);
			//当i=3时候merge(target,6,7,8);
			//也就是说当分4组的时候，0-2，2-4，4-6，6-8被分治排序。
			merge(target,s,s+length,(length<<1)+s-1);
		}
		//用总长度与每组长度取模运算，如果模为0代表数组的长度是2的整数次方，为最乐观情况下
		//如果模不为0意味着每次结束的时候余下的数都要与前面所有的数进行一次归并。
		//下面注释的代码为常规写法
//		 int mod = size%(length<<1);
//		 if(mod!=0){
//			 merge(target,0,(length<<1)*group,target.length-1);
//		 }
		
		//下面这段代码功能用途和上面的完全相同
		//这段代码运用的是&运算，效率上要高于注释的取模运算(神就在此处体现)
		//此处的运算，只有当length是2的指数幂时，结果是对的，其他一律错，正好这个地方必然是2的指数幂。
		int r = size & ((length << 1) - 1);
        if (r != 0){
            merge(target, size - r - 2 * length, size - r, size - 1);
        }
		mergeSort(target,0,length<<1);
	}

}

6.思考的问题
		a.当归并的数组长度不是2的指数次幂，是否可以通过补成2的指数次幂运算？
		b.当归并的数组长度不是2的指数次幂，是否可以去掉多余的数，当其余的归并成功后再插入？

算法和数据结构理解起来是非常痛苦的,而且不是第一次懂了以后还会懂,有可能会忘记!!!  所以先记录一下.防止忘记

归并算法 的时间复杂度是n乘以log n 在性能上还算比较优秀的

在理念上就是分封诸侯 ,每个人都给个官当当  然后把所有的官按大小排列
def merge_sort( li ):
    #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
    if len(li) == 1:
        return li

    #取拆分的中间位置
    mid = len(li) // 2
    #拆分过后左右两侧子串
    left = li[:mid]
    right = li[mid:]

    #对拆分过后的左右再拆分 一直到只有一个元素为止
    #最后一次递归时候ll和lr都会接到一个元素的列表
    # 最后一次递归之前的ll和rl会接收到排好序的子序列
    ll = merge_sort( left )
    rl =merge_sort( right )

    # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
    # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
    return merge(ll , rl)

#这里接收两个列表
def merge( left , right ):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
    result = []
    while len(left)>0 and len(right)>0 :
        #为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
        if left[0] <= right[0]:
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result

if __name__ == '__main__':
    li = [5,4 ,33 ,2 ,1]
    li2 = merge_sort(li)
    print(li2)

归并排序算法是用分支策略对n个元素进项排序的算法，其思想就是对待排序的序列分成最优两个子序列，对左右两个子序列进项排序，一次递归，最后将排好序的左右子序列合并成有序序列。

时间复杂度分析.
算法需要将2个排好序的数组段到新的数组段中，然后由算法copy将合并后的数组在复制到a数组中，显然都是在O（N）的时间内完成的。故时间复杂度为nlongn。

动画演示排序过程


代码实现

c++版
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

java版
public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

归并算法-MergeSort
      简单的说就是将要排序的序列分成等量的两份，从中间分开，然后接下来对第一次分出的两个子序列继续按前面的方法分，即对子序列继续用MergeSort的方法递归，然后将两个排序好的子序列通过简单的比较它们各自的最小值来合并成一个序列，这样就排序好了。
编程方面，利用两个函数，一个是用MergeSort方法来递归的mergeSort()函数，一个是讲左右两个子序列进行比较大小并合并成一个序列的Merge()函数。接下来贴上我的C++代码。
#include<iostream>
#define N 100
void mergeSort(int *a ,int l,int r);
void Merge(int *a,int l,int m,int r);
int main()
{
    int a[N];
    for(int i=0;i<N;i++)
    {
        a[i]=rand()%50+1;
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    mergeSort(a,0,N);
    for(int i=0;i<N;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    return 0;
    
}
void Merge(int *a, int l, int m, int r)
{
    int n1=m-l+1;
    int n2=r-m;
    int *L=new int[n1+1];//+1的含义：放置一个额外的数用来与R比较从而将R剩余比L中都大的数顺利放入a数组中（简称“哨兵”）。
    int *R=new int[n2+1];//+1的含义：放置一个额外的数用来与L比较从而将L剩余比R中都大的数顺利放入a数组中（简称“哨兵”）。
    int i,j,k;
    for(i=0;i<n1;i++)
    {
        L[i]=a[l+i];
    }
    for(j=0;j<n2;j++)
    {
        R[j]=a[m+1+j];
    }
    L[n1]=51;//设置比排序里最大的数还要大就行，这里设置的随机数最大为50，即设置哨兵。
    R[n2]=51;//设置比排序里最大的数还要大就行，这里设置的随机数最大为50，即设置哨兵。
    for(i=0,j=0,k=l;k<=r;k++){
        if(L[i]<R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
    }
    delete [] L;
    delete [] R;
}
void mergeSort(int *a,int l,int r)
{
    if(l<r)
    {
        int m=(l+r)/2;
        mergeSort(a, l, m);
        mergeSort(a, m+1, r);
        Merge(a,l,m,r);
    }
}
注意，如果序列长度不是很大，利用插入排序算法比归并排序算法更快，大约30个数以下用插入排序还是很好的。