大脑不够用了，补一个好玩的视频
基本思路首先是分，将数组平分两边，然后每边进行排序，排序后再将两边归并成一整个有序的数组；这阶段通过递归完成，所以归并=递归+合并
一个数组排序，分解为两个已经排序好的数组，不停地递归
来张书上的例子
最后一次的排序合并排序
对于merge函数的实现，while (left <= middle && right <= end) 这一层每次比较首位数字的大小，然后写入临时数组temp里；但是后面还有两轮while循环，原因如下
比如下面这个例子：middle=4，end=9
left=0，right=5，arr[left]=0，arr[right]=1，arr[left]<arr[right]，temp[i]=temp[0]=arr[left]=0，i=1，left=1
left=1，right=5，arr[left]=2，arr[right]=1，arr[left]<arr[right]，temp[i]=temp[1]=arr[right]=1，i=2，right=6
left=1，right=6，arr[left]=2，arr[right]=3，arr[left]<arr[right]，temp[i]=temp[2]=arr[left]=2，i=3，left=2
left=2，right=6，arr[left]=4，arr[right]=3，arr[left]<arr[right]，temp[i]=temp[3]=arr[right]=3，i=4，right=7
left=2，right=7，arr[left]=4，arr[right]=5，arr[left]<arr[right]，temp[i]=temp[4]=arr[left]=4，i=5，left=3
left=3，right=7，arr[left]=6，arr[right]=5，arr[left]<arr[right]，temp[i]=temp[5]=arr[right]=5，i=6，right=8
left=3，right=8，arr[left]=6，arr[right]=7，arr[left]<arr[right]，temp[i]=temp[6]=arr[left]=6，i=7，left=4
left=4，right=8，arr[left]=8，arr[right]=7，arr[left]<arr[right]，temp[i]=temp[7]=arr[right]=7，i=8，right=9
left=4，right=9，arr[left]=8，arr[right]=9，arr[left]<arr[right]，temp[i]=temp[8]=arr[left]=8，i=9，left=5
此时left=5，right=9，这样就跳出了while循环，可是arr[right]=9却还没有copy到temp里
但是无法确认left和right哪边还有剩余，因此还需要继续copy
/** * start = 0; middle = 4; end = 9; * temp: 02468 13579 0 * temp: 02468 13579 01 * temp: 02468 13579 012 * temp: 02468 13579 0123 * temp: 02468 13579 01234 * temp: 02468 13579 012345 * temp: 02468 13579 0123456 * temp: 02468 13579 01234567 * temp: 02468 13579 012345678 * temp: 02468 13579 0123456789 */
Java源码
package com.maoxiaomeng;
/**
* Copyright (C), 2014-2018, maoxiaomeng.com
* FileName: Solution
* Author: lihui
* Date: 2018/4/14 00:37
*/
public class Solution {
public void mergeSort(int[] arr) {
int len = arr.length;
int[] temp = new int[len];
sort(arr, 0, len - 1, temp);
}
public void sort(int[] arr, int start, int end, int[] temp) {
/**
* 4268093175
* 42680 93175
* 426 80 931 75
* 42 6 8 0 93 1 7 5
* 4 2 6 8 0 9 3 1 7 5
* 24 6 08 39 1 57
* 246 08 139 57
* 02468 13579
* 0246813579
* 0123456789
*/
if (start < end) {
int middle = (start + end) / 2;
sort(arr, start, middle, temp);
sort(arr, middle + 1, end, temp);
merge(arr, start, middle, end, temp);
}
}
public void merge(int[] arr, int start, int middle, int end, int[] temp) {
/**
* start = 0; middle = 4; end = 9;
* temp: 02468 13579 0
* temp: 02468 13579 01
* temp: 02468 13579 012
* temp: 02468 13579 0123
* temp: 02468 13579 01234
* temp: 02468 13579 012345
* temp: 02468 13579 0123456
* temp: 02468 13579 01234567
* temp: 02468 13579 012345678
* temp: 02468 13579 0123456789
*/
int left = start;
int right = middle + 1;
int i = 0;
while (left <= middle && right <= end) {
if (arr[left] <= arr[right]) {
temp[i++] = arr[left++];
} else {
temp[i++] = arr[right++];
}
}
while (left <= middle) {
temp[i++] = arr[left++];
}
while (right <= end) {
temp[i++] = arr[right++];
}
i = 0;
while (start <= end) {
arr[start++] = temp[i++];
}
}
}
merge里的条件，以及变量的++挺难想
比如传入的数组int[] arr = {0, 2, 3, 5, 6, 1, 7, 4, 8, 9};在while (left <= middle && right <= end)后面，打印一下temp的变化情况
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
[5, 2, 3, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 3, 0, 0, 0, 0, 0, 0, 0]
[1, 2, 3, 5, 6, 0, 0, 0, 0, 0]
[1, 4, 3, 5, 6, 0, 0, 0, 0, 0]
[8, 4, 7, 5, 6, 0, 0, 0, 0, 0]
[1, 4, 7, 5, 6, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 6, 0, 0, 0]
可以看到左半边left=5，这时候left <= middle不满足，跳出了while循环，而右半边7 8 9还没copy到temp里，经过下面
while (right <= end) {
temp[i++] = arr[right++];
}
就Ok了
