归并排序算法
归并排序算法： 归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并算法操作: 归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如 设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14
Java代码实现 ↓↓↓↓↓↓↓
/***
* 归并排序基础代码
*/
public class MergeSortBase {
/**
* 分 和 合并
*/
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
//确保两个数组中分别都存在至少一个数字
if (left < right) {
int mid = (left + right) / 2;
// 先分解左侧
mergeSort(arr, left, mid, temp);
// 再分解右侧
mergeSort(arr, mid + 1, right, temp);
// 最后合并
// 由于是递归，合并这里一定是栈顶的先执行(两边数组各只有一个数时)
// 第一次：left = 0,right=1
// 第二次：left = 2,right=3
// 第三次：left = 0，right=3
// System.out.println("left=" + left + "；right=" + right);
merge(arr, left, mid, right, temp);
}
}
/**
*
* 最难的是合并,所以可以先完成合并的方法，此方法请参考 基本思想 和 思路分析中的图解来完成
* 动脑筋
* @param arr 要排序的原始数组
* @param left 因为是合并，所以要得到左右两边的的数组信息，这个是左侧数组的第一个索引值
* @param mid 因为是一个数组，标识是第一个数组的最后一个索引，即 mid+1 是右侧数组的第一个索引，即中间索引
* @param right 右侧数组的结束索引，右边数组的最后一个数
* @param temp 临时空间，临时数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 定时临时变量，用来遍历数组比较
int l = left; // 左边有序数组的初始索引
int r = mid + 1; // 右边有序数组的初始索引
int t = 0; // temp 数组中当前最后一个有效数据的索引
// 1. 按思路先将两个数组（有序的）有序的合并到 temp 中
// 因为是合并两个数组，所以需要两边的数组都还有值的时候才能进行 比较合并
// 若其中一个数组的值遍历完了（取完了），那么就跳出该循环，把另一个数组所剩的值，直接copy进临时数组即可
while (l <= mid && r <= right) {
// 如果左边的比右边的小，则将左边的该元素填充到 temp 中
// 并移动 t++,l++,好继续下一个
if (arr[l] < arr[r]) {
temp[t] = arr[l];
t++;//移动 temp 临时数组中当前最后一个有效数据的索引
l++; //左边原始数组的索引移动
}
// 否则则将右边的移动到 temp 中
else {
temp[t] = arr[r];
t++;//移动 temp 临时数组中当前最后一个有效数据的索引
r++;//右边原始数组的索引移动
}
}
// 2. 如果有任意一边的数组还有值，则依序将剩余数据填充到 temp 中
// 如果左侧还有值
while (l <= mid) {
temp[t] = arr[l];
t++;
l++;
}
// 如果右侧还有值
while (r <= right) {
temp[t] = arr[r];
t++;
r++;
}
// 3. 将 temp 数组，拷贝到原始数组
// 注意：只拷贝当前temp有效数据到对应的原始数据中，通俗点说，就是原始数组中要排序的数据，通过temp排成了有序的，然后将temp中的有序数据将原始数组中原来要排序的那部分覆盖了就行了
int tempL = left; // 从左边开始拷贝，左边第一个值的索引
t = 0; // temp 中的有效值索引，有效值边界可以通过 right 判定，因为合并两个数组到 temp 中，边界就是 right ，这里自己好好想想
/*
* 对于 8,4,5,7,1,3,6,2 这个数组,
* 从栈顶开始合并：8,4 | 5,7 1,3 | 6,2
* 先左递归的话：
* 第一次：8,4 合并：tempL=0，right=1
* 第二次：5,7 合并：tempL=2，right=3
* 第三次：4,8 | 5，7 进行合并，tempL=0，right=3
* 直到左递归完成，得到左侧一个有序的序列：4,5,7,8 然后再开始递归右边那个无序的
* 最后回到栈底分解成两个数组的地方，将两个数组合并成一个有序数组
* 这里真的得自己想了，我只能这么说了。
*/
System.out.println("tempL=" + tempL + "; right=" + right);
while (tempL <= right) {
arr[tempL] = temp[t];
tempL++;
t++;
}
}
public static void main(String[] args) {
int[] arr = new int[]{97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("排序后：" + Arrays.toString(arr));
}
}
代码纯享版↓↓↓↓↓↓↓↓↓
/***
* 归并排序基础代码
*/
public class MergeSortBase {
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
// System.out.println("left=" + left + "；right=" + right);
merge(arr, left, mid, right, temp);
}
}
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int l = left;
int r = mid + 1;
int t = 0;
while (l <= mid && r <= right) {
if (arr[l] < arr[r]) {
temp[t] = arr[l];
t++;
l++;
}else {
temp[t] = arr[r];
t++;
r++;
}
}
while (l <= mid) {
temp[t] = arr[l];
t++;
l++;
}
while (r <= right) {
temp[t] = arr[r];
t++;
r++;
}
int tempL = left; // 从左边开始拷贝，左边第一个值的索引
t = 0;
System.out.println("tempL=" + tempL + "; right=" + right);
while (tempL <= right) {
arr[tempL] = temp[t];
tempL++;
t++;
}
}
public static void main(String[] args) {
int[] arr = new int[]{97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("排序后：" + Arrays.toString(arr));
}
}
运行结果 ↓↓↓↓↓↓↓
