C#核心知识回顾——21.归并排序

理解递归逻辑
        一开始不会执行sort函数的
        要先找到最小容量数组时
        才会回头递归调用Sort进行排序

基本原理
        归并 = 递归 + 合并
        数组分左右
        左右元素相比较
        一侧用完放对面
        不停放入新数组

        递归不停分
        分完再排序
        排序结束往上走
        边走边合并
        走到头顶出结果

套路写法
        两个函数
        一个基本排序规则
        一个递归平分数组

注意事项
        排序规则函数在平分数组函数
        内部return调用

 private void Start(){int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };arr = Merge(arr);for (int i = 0; i < arr.Length; i++){print(arr[i]);}}//第一步//基本排序规则//左右元素相比较//满足条件放进去//一侧用完直接放public int[] Sort(int[] left, int[] right){//新数组存放排序后的元素int[] arry = new int[left.Length + right.Length];//分隔后左右数组的索引标识int leftindex = 0;int rightindex = 0;for (int i = 0; i < arry.Length; i++){//左侧已经放完了，直接放右边的if (leftindex >= left.Length){arry[i] = right[rightindex];//已经放入一个右侧元素进入新数组//标识指向下一个rightindex++;}//右侧已经放完，直接放左边的else if(rightindex >= right.Length){arry[i] = left[leftindex];//已经放入一个左侧元素进入新数组//标识指向下一个leftindex++;}else if (left[leftindex] < right[rightindex]){arry[i] = left[leftindex];//已经放入一个左侧元素进入新数组//标识指向下一个leftindex++;}else{arry[i] = right[rightindex];//已经放入一个右侧元素进入新数组//标识指向下一个rightindex++;}}return arry;}//第二步：//递归评分数组//结束条件为长度小于2public int[] Merge(int[] arry){//递归结束条件if (arry.Length < 2)return arry;//1.数组分两段int mid = arry.Length / 2;//2.初始化左右数组int[] left =new int[mid];int[] right =new int[arry.Length - mid];for (int i = 0; i < arry.Length; i++){if (i < mid){left[i] = arry[i];}else{right[i-mid] = arry[i];}}//3.递归分组再排序return Sort(Merge(left),Merge(right));}