死磕数据结构与算法（排序）--归并排序。才疏学浅，如有错误，及时指正

八大排序算法

1. 冒泡排序算法

2. 选择排序算法

3. 插入排序冒泡算法

4. 希尔排序冒泡算法

5. 快速插入冒泡算法

6. 归并排序冒泡算法

7. 基数排序冒泡算法

8. 堆排序算法

1. 概念以及思路

归并排序是分治算法的典型应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

2. 图解过程

3. 代码实现

package 算法学习.Sort;import java.util.Arrays;public class MergeSort {public static void main(String[] args) {int arr[] = {2,5,4,8,9,1,3,0};int temp[] = new int[arr.length];sortMerge(arr, 0, arr.length-1, temp);System.out.println(Arrays.toString(arr));}public static void sortMerge(int[] arr, int left, int right, int[] temp){if(left < right){int mid = (left + right) / 2;//向左递归sortMerge(arr, left, mid, temp);//向右递归sortMerge(arr, mid+1, right, temp);merge(arr, left, mid, right, temp);}}public static void merge(int[]arr, int left, int mid, int right, int[] temp){System.out.println("aaaaaaaaaaaaa");int i = left;   //定义左边起始位置int j = mid + 1;    //定义右边起始位置int t = 0; //t位temp中的索引//1. 先对arr左边数组和右边数组进行循环，直到有一边的数组的走完位止while(i <= mid && j <= right){if(arr[i] < arr[j]){temp[t++] = arr[i++];}else{temp[t++] = arr[j++];}}//2. 如果有哪一边数组没走完，则对这边的数组进行继续操作。while(i <= mid){temp[t++] = arr[i++];}while(j <= right){temp[t++] = arr[j++];}// 3. 将temp数组的元素拷贝到arrt = 0;int tempLeft = left;while(tempLeft <= right){arr[tempLeft++] = temp[t++];}}
}