编程中的基本数据结构与算法思想( 三 ) _算法

归并排序在1945年由冯·诺伊曼首次提出。
2-路归并的基本思路就是将数组分成二组A ， B ，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序？
可以将A ， B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
归并排序的效率是比较高的，设数列长为N ，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N) ，故一共为O(N*logN) 。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。
7.1 归并排序分解

文章插图

可以看到这种结构很像一棵完全二叉树，分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n 。
7.2 归并排序合并相邻有序子序列
再来看看并阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8] ，来看下实现步骤。

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];
重复步骤3直到某一指针到达序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾；

文章插图

文章插图

7.3 归并排序动图演示

文章插图

文章插图

7.4 归并排序代码

文章插图

8 回溯法和分书问题回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯“返回，尝试别的路径。可以参考一下走迷宫的过程，一开始会随机选择一条道路前进，一直到走不通之后就会回头直到找到另外一条没有试过的道路前进。实际上，走迷宫的算法就是回溯法的经典问题。
回溯法实际上也是一种试错的思路，通过不断尝试解的组合来达到求解可行解和最优解的目的。虽然都有穷搜的概念蕴含其中，但是回溯法和穷举查找法是不同的。对于一个问题的所有实例，穷举法注定都是非常缓慢的，但应用回溯法至少可以期望对于一些规模不是很小的实例，计算机在可接受的时间内对问题求解。
许多复杂的规模的问题都可以使用回溯法，有”通用解题方法”的美称。分书问题和八皇后都是典型的回溯法问题。
分书问题能够较有代表性地表现数据描述、递归、回溯的算法思路。
有编号为0 ， 1 ， 2 ， 3 ， 4的5本书，准备分给5个人A ， B ， C ， D ， E ，写一个程序，输出所有皆大欢喜的分书方案。