[index]
[#1]原理部分
[#2]代码部分
[/index]
归并排序是重要的一个排序，归并排序的原理很有意思，请大家往下看。
有句话叫做大事化小，小事化了。归并排序也就是用的这一种非常简单的方法来排序的。
用一句话的概括叫做：将数据一分为二，分到不能分，然后根据比较大小的方法排序。
说起来很简单，但实际上做起来不简单，我们用一串数据来模拟一遍：
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[] | 3 | 6 | 1 | 8 | 7 | 2 | 4 | 9 | 10 | 5 |
这一串数据就是模拟数据了。接下来我们把刚刚讲的那句话拆解一下：
数据一分为二，分到不能分/然后用比较大小的方法排序
拆解后，会发现只有两个步骤：分+排序。
首先是一分为二：我们用这一串数据举个例子（小到大排）：先将这一串数据对半分（下表中属于左半部分的标了1，右半部分标了2）：
| 数组 | 0(1) | 1(1) | 2(1) | 3(1) | 4(1) | 5(2) | 6(2) | 7(2) | 8(2) | 9(2) |
| a[] | 3 | 6 | 1 | 8 | 7 | 2 | 4 | 9 | 10 | 5 |
然后按照那句话说的，分到不能分，那么我们就继续分：（数据对半除不尽用去尾法操作）
| 数组 | 0(11) | 1(11) | 2(12) | 3(12) | 4(12) | 5(21) | 6(21) | 7(22) | 8(22) | 9(22) |
| a[] | 3 | 6 | 1 | 8 | 7 | 2 | 4 | 9 | 10 | 5 |
继续分……
| 数组 | 0(11) | 1(11) | 2(121) | 3(122) | 4(122) | 5(21) | 6(21) | 7(221) | 8(222) | 9(222) |
| a[] | 3 | 6 | 1 | 8 | 7 | 2 | 4 | 9 | 10 | 5 |
此时你会看到，数据有一些在第二步就分成了两个一组，那么当分到两两一组或单独一组，就可以停止分组了。（如上表）这就叫做分到不能分，大家明白了吗？
接下来就是比较做排序。
首先我们进行第一层比较（两个数据比较），交换，完成后如下：
| 数组 | 0(11) | 1(11) | 2(12) | 3(12) | 4(12) | 5(21) | 6(21) | 7(22) | 8(22) | 9(22) |
| a[] | 3 | 6 | 1 | 7 | 8 | 2 | 4 | 9 | 5 | 10 |
第一次比较后是这样的。大家可以发现上方的角标有的从三位变成了两位。
接下来进行第二次比较，但此时是四个数据（或者两个和三个数据），那我们怎么比较呢？
我们用一组例子：大家看到带(22)中的例子，带(22)的有三个数，分别是9,5,10，它们在上一步分成了左右两边，分别是9在一边，5和10在另一边
然后我们命名两个变量p和q，作为指针（因为我不会写指针），将指针分别指向每一边的第一个数
然后我们在命名一个result数组，等会大家就知道它的作用了。
以上的过程均用表格呈现：
| 数组 | 0(11) | 1(11) | 2(12) | 3(12) | 4(12) | 5(21) | 6(21) | 7(22) | 8(22) | 9(22) |
| a[] | 3 | 6 | 1 | 7 | 8 | 2 | 4 | 9 | 5 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | ||||||||||
| 比较过程 |
第一步，我们先对p和q指针指向的数字对比，发现9>5，然后我们先将5加入result数组里，然后将q向后进一位，如下表：
| 数组 | 0(11) | 1(11) | 2(12) | 3(12) | 4(12) | 5(21) | 6(21) | 7(22) | 8(22) | 9(22) |
| a[] | 3 | 6 | 1 | 7 | 8 | 2 | 4 | 9 | 5 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 5 | |||||||||
| 比较过程 |
第二步，我们继续将和q指针指向的数字对比，发现10>9，那么我们将9加入result数组里，然后将p向后进一位。但你发现p向后没有办法进位了，那么排序就结束了。
| 数组 | 0(11) | 1(11) | 2(12) | 3(12) | 4(12) | 5(21) | 6(21) | 7(22) | 8(22) | 9(22) |
| a[] | 3 | 6 | 1 | 7 | 8 | 2 | 4 | 9 | 5 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 5 | 9 | ||||||||
| 比较过程 |
第三步，右边还有10没有加入result数组中，所以我们要将剩下没排序的数字依次按顺序加入result数组中：
| 数组 | 0(11) | 1(11) | 2(12) | 3(12) | 4(12) | 5(21) | 6(21) | 7(22) | 8(22) | 9(22) |
| a[] | 3 | 6 | 1 | 7 | 8 | 2 | 4 | 9 | 5 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 5 | 9 | 10 | |||||||
| 比较过程 |
最后一步，result数组重新填入a[]中：
| 数组 | 0(11) | 1(11) | 2(12) | 3(12) | 4(12) | 5(21) | 6(21) | 7(22) | 8(22) | 9(22) |
| a[] | 3 | 6 | 1 | 7 | 8 | 2 | 4 | 5 | 9 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 5 | 9 | 10 | |||||||
| 比较过程 |
这就是如何多个数比较排序的方法，我们再看一个例子。此时已经是最后一次合并了（如下表，此时剩余最后一步，将左边的0~4号与右边的5~9号进行合并，从而排好序）：
我们将p和q都指向两边的第一号，0号和5号，并且result清空。
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[] | 1 | 3 | 6 | 7 | 8 | 2 | 4 | 5 | 9 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | ||||||||||
| 比较过程 |
第一次比较，发现1<2，将1加入result数组，p往后进一位。
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[] | 1 | 3 | 6 | 7 | 8 | 2 | 4 | 5 | 9 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 1 | |||||||||
| 比较过程 |
第二次比较，发现3>2，将2加入result数组，q往后进一位。
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[] | 1 | 3 | 6 | 7 | 8 | 2 | 4 | 5 | 9 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 1 | 2 | ||||||||
| 比较过程 |
其余的比较同理，我们跳过……
最后一次比较，8<9，将8加入result数组，p往后进一位，但此时p已经是指向左边的最后一位了，那么停止循环。
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[] | 1 | 3 | 6 | 7 | 8 | 2 | 4 | 5 | 9 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||
| 比较过程 |
然后我们将没有排序的9和10也依次加入result数组：
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[] | 1 | 3 | 6 | 7 | 8 | 2 | 4 | 5 | 9 | 10 |
| 指针位置 | p | q | ||||||||
| result[] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 比较过程 |
最后将result数组的值重新加入a[]中，
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| a[] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 指针位置 | ||||||||||
| result[] | ||||||||||
| 比较过程 |
那么这就是归并排序的步骤，不难理解，而且掌握方法后写程序就很有思路了。
页:
[1]