MergeSort

大脑不够用了,补一个好玩的视频

基本思路首先是分,将数组平分两边,然后每边进行排序,排序后再将两边归并成一整个有序的数组;这阶段通过递归完成,所以归并=递归+合并

一个数组排序,分解为两个已经排序好的数组,不停地递归

来张书上的例子

最后一次的排序合并排序

对于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了

发表评论