将另一序列剩下的所有元素直接复制到原始数组末尾

________________

（1)在数据集之中，选择一个元素作为”基准”（pivot）。

(2)所有小于”基准”的元素，都移到"基准”的左边;所有大于"基准”的元素，都移到"基准”的右边。

(3)对”基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

（1)快速排序问题

设a［0：n-1]是一个未排序的数组，如｛0，12，45，3，6，29，4,16，77｝.实现快速排序算法对该数组进行排序.

（2）步骤

对于输入的子序列L［p..r］分三步处理：

第一步:分解(Divide）

先从数据序列中选一个元素,称为基准元素。将序列中所有比基准元素小的元素都放到它的左边，比基准元素大的元素都放到它的右边。

在序列L［p..r]中选择基准元素L［q]，经比较和移动后，L［q]将处于L[p.。r]中间的适当位置,使得基准元素L[q］的值大于L［p.。q—1］中任一元素的值,基准元素L［q]的值小于L［q+1。。r]中任一元素的值。

第二步：递归求解（Conquer）

再对左右两边分别用同样的方法处理，直到每一个待处理的序列的长度为1。

通过递归调用快速排序算法，分别对L［p。。q—1]和L［q+1.。r］进行排序.

第三步：合并(Merge）

由于对分解出的两个子序列的排序是就地进行的,所以在L[p。。q-1]和L［q+1。。r]都排好序后不需要执行任何计算L[p..r］就已排好序,即自然合并.

这个解决流程是符合分治法的基本步骤的。

贪心算法

贪心算法（又称贪婪算法）是指，在对______时，总是做出在当前看来是最好的选择。也就是

说，不从整体最优上加以考虑,他所做出的是在某种意义上的局部______。

（2)特性:贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质

(3)贪心算法与动态规划算法的差异：

动态规划和贪心算法都是一种递推算法，均有最优子结构性质,通过局部最优解来推导全局最优解.两者之间的区别在于:贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解,因此需要记录之前的所有最优解。

活动安排问题

由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中.直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。

最小生成树

Prim算法

设G = (V，E)是连通带权图，V =｛1，2,…，n}.构造G的最小生成树Prim算法的基本思想是：首先置S =｛1｝，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i ∈S，j ∈V – S，且c[i］[j］最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止.在这个过程中选取到的所有边恰好构成G的一棵最小生成树.

Kruskal算法

给定无向连同带权图G =（V,E），V =｛1,2,。.。,n｝。Kruskal算法构造G的最小生成树的基本思想是：

（1）首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小大排序。

（2)从第一条边开始，依边权递增的顺序检查每一条边.并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w）时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点是，就用边（v,w）将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看k+1条边。这个过程一个进行到只剩下一个连通分支时为止。

动态规划

基本思想：基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解.每一个解都对应于一个值，我们希望找到具有______的解。动态规划算法与______类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题,然后从______问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间.我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过,就将其结果填入表中.这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

基本步骤

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性)，否则问题就无法用动态规划求解.

（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态.所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。

动态规划算法分以下4个步骤：

1.描述最优解的结构

2.递归定义最优解的值

3.按自底向上的方式计算最优解的值//此3步构成动态规划解的基础。

4.由计算出的结果构造一个最优解。//此步如果只要求计算最优解的值时，可省略.

好,接下来,咱们讨论适合采用动态规划方法的最优化问题的俩个要素：最优子结构性质,和子问题重叠性质.

1·最优子结构性

简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

2·重叠子问题

在递归算法自顶向下解决问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算了多次。动态规划正是利用这种重叠子问题性质，对每一子问题直解一次,而后将其解保存在一个表格中，当每次需要时，只简单用常数时间查看一下结果。

3·备忘录方法

备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案,在下次需要解此子问题时，只要简单查看该问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下,而动态规划算法是自底向上递归。

矩阵连乘

.