归并排序 - 《排序算法小结》

基本思路
debug理解一下

该算法采用经典的D&C策略，也就是法治策略。
对比python的分治，Java不能实现对数组的切割，所以本质上是对指针的分割，是对操作区间的分割，要理解索引的变化

基本思路

首先要理解，上面图示中的分并不是真的将数组切割了，只是将操作区间切割了，本质上就是指针的变化范围。
来看怎么治，看治的最后一步，数据多，比较容易理解。原理其实就是运用了中间数组，运用两个索引分别遍历两个部分的元素，值较小的就进入中间数组，大的那个则留下了继续和接下来的数比较，最后如果一边的数全部遍历完了，那另一边的数则自动归入中间数组，图解如下：

代码如下，注意事项已在代码中标明
`//合并的方法
/*

* @param __arr 排序的原始数组
* @param __left 左边有序序列的初始索引
* @param __mid 中间索引（右边有序序列的前面一个位置）
* @param __right 右边索引
* @param __temp 中转数组
*/
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//初始化i，左边有序序列的初始索引
int j = mid + 1;//初始化j，右边有序序列的初始索引
int t = 0;_//指向temp数组的当前索引

    //（一）<br />        //先把左右两边（有序）的数据按照规则填充到temp数组<br />        //直到左右两边的有序序列，有一边处理完毕为止<br />        _**while **(i <= mid && j<= right){_//继续<br />            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素<br />            //就将左边的当前元素，填充到temp，然后t++,i--<br />            _**if **(arr[i] <= arr[j]){<br />                temp[t] = arr[i];<br />                t += 1;<br />                i += 1;<br />            }**else **{<br />                temp[t] = arr[j];<br />                t += 1;<br />                j += 1;<br />            }<br />        }
    _//（二）<br />        //吧有剩余数据的一边的数据依次全部填充到temp<br />        _**while **(i <= mid){<br />            temp[t] = arr[i];<br />            t += 1;<br />            i +=1;<br />        }<br />        **while **(j <= right){<br />            temp[t] = arr[j];<br />            t += 1;<br />            j += 1;<br />        }
    _//（三）<br />        //将temp数组的元素拷贝到arr<br />        _t = 0;<br />        **int **tempLeft = left;<br />        **while **(tempLeft <= right){<br />            arr[tempLeft] = temp[t];<br />            t += 1;<br />            tempLeft += 1;<br />        }<br />    }<br />}`<br />这一部分还算好理解，接下来就是递归的部分，先看代码<br />`_//分+合的方法<br />_**public static void **mergeSort(**int**[] arr,**int **left,**int **right,**int**[] temp){<br />    **if **(left < right){<br />        **int **mid = (left+right)/2;<br />        _//向左递归进行分解<br />        mergeSort_(arr, left, mid, temp);<br />        _//向有右递归进行分解<br />        mergeSort_(arr,mid+1, right, temp);<br />        _//合并<br />        merge_(arr,left,mid,right,temp);
}<br />}`

debug理解一下

**public void **test5(){ **int**[] arr = {4,8,6,2,9,7,7,21,6,3,5,8}; _//Sort.quickSort(arr,0,arr.length-1); _**int**[] temp = **new int**[arr.**length**]; Sort._mergeSort_(arr,0,arr.**length**-1,temp); System.**_out_**.println(Arrays._toString_(arr)); }

首先程序会不断运行向左递归，栈里进入了5个mergeSort，注意到在栈顶的方法里，左右指针已经相等，向左递归和向右递归都不会再运行，这时候merge方法得到的就是arr[0]本身，然后整个方法运行完毕，出栈，到第四个方法

则会运行到向右递归，然后向右递归又会进入第五个方法，然后跟上面一样退出，然后进入到第四个方法的merge方法，对4，8运用合并方法进行排序，以此类推，最后当栈内存为空时，则可得到一个排序完成的数组。

最后，本质上这个算法也是一个以空间换时间的极好例子