五大经典算法介绍
1分治法
1.1基本概念
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
1.2基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1 1.3分治法适用的情况 分治法所能解决的问题一般具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解； 4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加； 第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用； 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。 第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。 1.4分治法的基本步骤 分治法在每一层递归上都有三个步骤： step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 step3 合并：将各个子问题的解合并为原问题的解。 它的一般的算法设计模式如下： Divide-and-Conquer(P) 1. if |P|≤n0 2. then return(ADHOC(P)) 3. 将P分解为较小的子问题P1 ,P2 ,...,Pk 4. for i←1 to k 5. do yi ←Divide-and-Conquer(Pi) △递归解决Pi 6. T ←MERGE(y1,y2,...,yk) △合并子问题 7. return(T) 其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。 1.5分治法的复杂性分析 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有： T（n）= k T(n/m)+f(n) 通过迭代法求得方程的解： 递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n 1.6可使用分治法求解的一些经典问题 （1）二分搜索 （2）大整数乘法 （3）Strassen矩阵乘法 （4）棋盘覆盖 （5）合并排序 （6）快速排序 （7）线性时间选择 （8）最接近点对问题 （9）循环赛日程表 （10）汉诺塔 1.7依据分治法设计程序时的思维过程 实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。 1、一定是先找到最小问题规模时的求解方法 2、然后考虑随着问题规模增大时的求解方法 3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。 2动态规划 2.1基本概念 动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。 2.2基本思想与策略 基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。 与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。 2.3适用的情况 能采用动态规划求解的问题的一般要具有3个性质： (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。 (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。 (3)有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势） 2.4求解的基本步骤 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。 初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态 图1 动态规划决策过程示意图 (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。 (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。 实际应用中可以按以下几个简化的步骤进行设计： （1）分析最优解的性质，并刻画其结构特征。 （2）递归的定义最优解。 （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值 （4）根据计算最优值时得到的信息，构造问题的最优解 2.5算法实现的说明 动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。 使用动态规划求解问题，最重要的就是确定动态规划三要素： （1）问题的阶段（2）每个阶段的状态 （3）从前一个阶段转化到后一个阶段之间的递推关系。 递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。 确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)} 2.6动态规划算法基本框架 代码 1for(j=1; j<=m; j=j+1) // 第一个阶段 2 xn[j] = 初始值; 3 4for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段 5for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式 6 xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])}; 8 9t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案 10 11print(x1[j1]); 12 13for(i=2; i<=n-1; i=i+1） 15{ 17 t = t-xi-1[ji]; 18 19for(j=1; j>=f(i); j=j+1) 21if(t=xi[ji]) 23break; 25} 3贪心算法 3.1基本概念： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。 3.2贪心算法的基本思路： 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 3.3贪心算法适用的问题 贪心策略适用的前提是：局部最优策略能导致产生全局最优解。 实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。 3.4贪心算法的实现框架 从问题的某一初始解出发； while （能朝给定总目标前进一步） { 利用可行的决策，求出可行解的一个解元素； } 由所有解元素组合成问题的一个可行解； 3.5贪心策略的选择 因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。 3.6例题分析 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。 [背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品A B C D E F G 重量35 30 60 50 40 10 25 价值10 40 30 50 35 40 30 分析： 目标函数：∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150) （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占重量最小的物品装入是否能得到最优解？ （3）每次选取单位重量价值最大的物品，成为解本题的策略。 值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。 贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。 可惜的是，它需要证明后才能真正运用到题目的算法中。 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下： （1）贪心策略：选取价值最大者。反例： W=30 物品：A B C 重量：28 12 12 价值：30 20 20 根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。 （2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。 （3）贪心策略：选取单位重量价值最大的物品。反例： W=30 物品：A B C 重量：28 20 10 价值：28 20 10 根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。 4回溯法 4.1概念 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 4.2基本思想 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。 4.3用回溯法解题的一般步骤： （1）针对所给问题，确定问题的解空间： 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。 （2）确定结点的扩展搜索规则 （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 4.4算法框架 （1）问题框架 设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。 （2）非递归回溯框架 1:int a[n],i; 2:初始化数组a[]; 3: i = 1; 4:while (i>0(有路可走) and (未达到目标)) // 还未回溯到头 5: { 6:if(i > n) // 搜索到叶结点 7: { 8:搜索到一个解，输出； 9: } 10:else// 处理第i个元素 11: { 12: a[i]第一个可能的值； 13:while(a[i]在不满足约束条件且在搜索空间内) 14: { 15: a[i]下一个可能的值； 16: } 17:if(a[i]在搜索空间内) 18: { 19:标识占用的资源； 20: i = i+1; // 扩展下一个结点 21: } 22:else 23: { 24:清理所占的状态空间；// 回溯 25: i = i –1; 26: } 27: } （3）递归的算法框架 回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下： 1:int a[n]; 2:try(int i) 3: { 4:if(i>n) 5:输出结果; 6:else 7: { 8:for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径 9: { 10:if(fun(j)) // 满足限界函数和约束条件 11: { 12: a[i] = j; 13: ... // 其他操作 14:try(i+1); 15:回溯前的清理工作（如a[i]置空值等）; 16: } 17: } 18: } 19: } 5分支限界法 5.1基本描述 类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 （1）分支搜索算法 所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。 选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。 1）FIFO搜索 2）LIFO搜索 3）优先队列式搜索 （2）分支限界搜索算法 5.2分支限界法的一般过程 由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。 5.3回溯法和分支限界法的一些区别 有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢？ 回溯法和分支限界法的一些区别： 方法对解空间树的搜索方式存储结点的常用数据结构结点存储特性常用应用 回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解 排序算法 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] 《算法与程序设计》模块练习题 一、单选题 1、模块化程序设计方法主要通过()来实现。 A.递归算法和递归程序 B.过程和函数的定义和调用 C.程序的循环结构 D.对象答案:B 2、text1.text的含义正确的是()。 A.text1是控件名称，text是控件属性 B.text1是窗体名称，text 是控件 C.text1是控件名称，text是方法 D.text1是控件属性，text是控 件答案:A 3、以下程序段运行后S的值是()。 s = 0 For i = 1 To 14 x = 2 * i - 1 If x Mod 3 = 0 Then s = s + 1 Next i A.0 B.4 C.5 D.14 答案:C 4、数列1，4，7，10，13，……的递推公式为()。 A.f(1)=1;f(n)=n+3 B.f(1)=1;f(n)=n*2-1 C.f(1)=1;f(n)=n*2+1 D.f(1)=1;f(n)=f(n-1)+3 答案:D 5、对于对象及其特征的错误理解是()。 A.对象都具有一个标识自己以区别其他对象的名字。 B.对象都具有自身的属性及其属性值。 C.对象一般只用数据表示属性，但不用代码表示行为。 D.对象都具有自身的行为(操作)。 答案:C 6、VB函数Left ()从字串左端取部分字串，那么Left("Visual Basic 6.0", 8)的值为()。 A.Visual B B.Visual C.Visual Ba D.asic 6.0 答案:A 7、程序段如下： c ="1234" For i = 1 To 4 Print _____， Next 如果要让程序运行后得到如下结果： 1 1 2 12 3 1234 则在下划线处应填入的内容为()。 A.Right(c,i) B.Left(c,i) C.Mid(c,i,1) D.Mid(c,i,i) 答案:B 8、若X = True，执行If X Then X = 0 Else X = 1后X的结果为()。 HUNAN UNIVERSITY 课程实习报告 题目：排序算法的时间性能学生姓名 学生学号 专业班级 指导老师李晓鸿 完成日期 设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象） 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。 (3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 (5)要给出实验的方案及其分析。 说明 本题重点在以下几个方面： 理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。 一、需求分析 (1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比 较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。 用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数 (2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和 比较次数。 (3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机 数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据：略 二、概要设计 算法与程序设计（教科版）教案 1-1节计算机解决问题的过程 一、教学目标 1、知识与技能 （1）让学生了解算法、穷举法、程序设计语言、编写程序和调试程序等概念。 （2）让学生知道对现实问题的自然语言的描述，特别是类似程序设计语言的自然语言描述。 （3）让学生理解分析问题、设计算法、编写程序、调试程序这一用计算机解决问题的基本步骤，认识其在算法与程序设计中的作用。 2、方法与过程 （1）培养学生发现旧知识的规律、方法和步骤，并把它运用到新知识中去的能力。 （2）培养学生调试程序的能力。 （3）培养学生合作、讨论、观摩、交流和自主学习的能力。 3、情感态度和价值观 通过“韩信点兵”这个富有生动情节的实例和探究、讲授、观摩、交流等环节，让学生体验用计算机解决问题的基本过程。 二、重点难点 本节的重点用计算解决问题的过程中的分析问题、设计算法、和上机调试程序等步骤。用计算机解决问题的过程中的分析问题、设计算法也是本节的难点。 三、教学环境 1、教材处理 教学内容选用中华人民共和国教育部制订的《普通高中技术课程标准》（2003年4月版）中信息技术部分的选修模块1“算法与程序设计”第一章的第一课“计算机解决问题的过程”。教材选用《广东省普通高中信息技术选修一：算法与程序设计》第三章第一节，建议“算法与程序设计”模块在高中一年级下学期或高中二年级开设。 根据2003年4月版《普通高中技术课程标准》的阐述，“算法与程序设计”是普通高中信息技术的选修模块之1，它的前导课程是信息技术的必修模块“信息技术基础”。学生在“信息技术基础”模块里已经学习了计算机的基本操作，掌握了启动程序、窗口操作和文字编辑等基础知识。学生可以利用上述的基础知识，用于本节课的启动Visual Basic程序设计环境，输入程序代码，运行程序等操作。本节课“计算机解决问题的过程”是“算法与程序设计”模块的第一节课，上好这节课是使学生能否学好“算法与程序设计”这一模块的关键。本节课的教学目的是让学生理解分析问题、设计算法、编写程序和调试程序等用计算机解决问题的基本过程，认识其在算法与程序设计中的地位和作用，它也是后续课程如模块化程序设计、各种算法设计等课程的基础。 让学生在人工解题中发现分析问题、设计算法等步骤，并把它应用到用计算机解决问题中去，这是构建主义中知识迁移的方法。本节课还采用了探究、讲授、观摩、交流、阅读材料等多种教学活动的有机结合的方法。 2、预备知识 本节课相联系的旧知识是计算机的基本操作中鼠标、键盘操作，启动、关闭程序，窗口、菜单操作和文字编辑等基础知识，还有解决数学问题的步骤等知识。 3、硬件要求 论文中常用的研究方法 调查法 调查法是科学研究中最常用的方法之一。它是有目的、有计划、有系统地搜集有关研究对象现实状况或历史状况的材料的方法。调查方法是科学研究中常用的基本研究方法，它综合运用历史法、观察法等方法以及谈话、问卷、个案研究、测验等科学方式，对教育现象进行有计划的、周密的和系统的了解，并对调查搜集到的大量资料进行分析、综合、比较、归纳，从而为人们提供规律性的知识。 调查法中最常用的是问卷调查法，它是以书面提出问题的方式搜集资料的一种研究方法，即调查者就调查项目编制成表式，分发或邮寄给有关人员，请示填写答案，然后回收整理、统计和研究。 观察法 观察法是指研究者根据一定的研究目的、研究提纲或观察表，用自己的感官和辅助工具去直接观察被研究对象，从而获得资料的一种方法。 科学的观察具有目的性和计划性、系统性和可重复性。在科学实验和调查研究中，观察法具有如下几个方面的作用：①扩大人们的感性认识。②启发人们的思维。③导致新的发现。 实验法 实验法是通过主支变革、控制研究对象来发现与确认事物间的因果联系的一种科研方法。其主要特点是：第一、主动变革性。观察与调查都是在不干预研究对象的前提下去认识研究对象，发现其中的问题。而实验却要求主动操纵实验条件，人为地改变对象的存在方式、变化过程，使它服从于 科学认识的需要。第二、控制性。科学实验要求根据研究的需要，借助各种方法技术，减少或消除各种可能影响科学的无关因素的干扰，在简化、纯化的状态下认识研究对象。第三，因果性。实验以发现、确认事物之间的因果联系的有效工具和必要途径。 文献研究法 文献研究法是根据一定的研究目的或课题，通过调查文献来获得资料，从而全面地、正确地了解掌握所要研究问题的一种方法。文献研究法被子广泛用于各种学科研究中。其作用有：①能了解有关问题的历史和现状，帮助确定研究课题。②能形成关于研究对象的一般印象，有助于观察和访问。③能得到现实资料的比较资料。④有助于了解事物的全貌。 实证研究法 实证研究法是科学实践研究的一种特殊形式。其依据现有的科学理论和实践的需要，提出设计，利用科学仪器和设备，在自然条件下，通过有目的有步骤地操纵，根据观察、记录、测定与此相伴随的现象的变化来确定条件与现象之间的因果关系的活动。主要目的在于说明各种自变量与某一个因变量的关系。 定量分析法 在科学研究中，通过定量分析法可以使人们对研究对象的认识进一步精确化，以便更加科学地揭示规律，把握本质，理清关系，预测事物的发展趋势。 定性分析法 FBI变态心理测试题 1.某天，一位曾去过南极站参与太阳能设备调试工作的工程师在家里吃了妻子端给他的肉 食后，觉得味道很怪，就问妻子这是什么肉。妻子回答说这是企鹅肉。那工程师沉默了一会之后，用餐叉刺进了自己的喉咙。为什么？ 答案：工程师在南极曾经遇险，一个同事死掉了。后来他和其他人依靠吃一种据说是企鹅肉的东西才维持到营救人员赶到。他在尝到了企鹅肉的真正味道之后，才知道他当时吃的其实是死去同事的肉。 2. 一名身患宿疾的男子四处求医，最终在一家医院内彻底治愈了。可是在他返乡的火车上，他忽然歇斯底里地大哭大叫，狂乱中打伤了几名乘客后，撞碎车窗，跳出了车外。结果被卷入车轮，粉身碎骨。为什么？ 答案：男子的宿疾是失明。痊愈后，本以为自己可以重见光明，结果列车经过了一个隧道，黑暗中男子以为自己旧疾复发，绝望之余跳车自尽。 3. 有个男子和女友在河边散步，女友失足落入水中，挣扎了几下就沉没了。男子慌忙跳入水中，可是却没有将女友救上来。几年后，男子重游伤心地，看见一个老者在钓鱼。男子发现老者钓上的鱼身上都干干净净的，就问老者鱼身上为什么没有水草。老者回答说：这条河里从来就没有水草。男子听后，一言不发，跳入河中自杀了。为什么？ 答案：当时男子跳入河中挽救女友的时候，曾抓住类似水草的东西，男子就放手了。后来从老者的回答中，他终于知道他当时抓住的并不是水草，而是女友的头发。 4. 一个人头朝下死在沙漠里，身边是几个大大小小的行李箱。死者手中紧紧捏着半根火柴。这个人死怎么死的。 答案：这个人乘坐的飞机发生了故障，所有人需要跳伞逃生，结果发现降落伞少了一个。于是大家决定抽签决定生死，抽到半根火柴的人只能自己跳下去。结果死者不幸抽到了半根火柴。 实验课程：算法分析与设计 实验名称：几种排序算法的平均性能比较（验证型实验） 实验目标： （1）几种排序算法在平均情况下哪一个更快。 （2）加深对时间复杂度概念的理解。 实验任务： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。 （2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于围（0，105）的整数。 对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： (1)明确实验目标和具体任务； (2)理解实验所涉及的几个分类算法； (3)编写程序实现上述分类算法； (4)设计实验数据并运行程序、记录运行的结果； (5)根据实验数据及其结果得出结论； (6)实验后的心得体会。 问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）： 选择排序：令A[1…n]为待排序数组，利用归纳法，假设我们知道如何对后n-1个元素排序， 即对啊[A…n]排序。对某个j,1<=j<=n,设A[j]是最小值。首先，如果就！=1，我们交换A[1] 和A[j]。然后由假设，已知如何对A[2..n]排序，因此可对在A[2…n]中的元素递归地排序。 可把递归改为迭代。算法程序实现如下： void SelectionSort(int *Array,int n,int &c) { int i,j,k; int aa; c=0; for(i=0;i 高中信息技术《算法与程序设计VB （选修）》 知识要点 相关知识点 （一）算法 1.定义 相关题解： 1算法：就是解决问题的方法和步骤。算法是程序设计的“灵魂”，算法+数据结构＝程序。 单选题 1、运用计算机程序解决实际问题时，合理的步骤是（B ）。 A 、设计算法→分析问题→编写程序→调试程序 B 、分析问题→设计算法→编写程序→调试程序 C 、分析问题→编写程序→设计算法→调试程序 D 、设计算法→编写程序→分析问题→调试程序 2．算法的描述方法： 1算法的描述：可分多种表达方法，一般用自然语言、流程图和伪代码进行描述。 2自然语言描述法：指用人们日常生活中使用的语言（本国语言），用自然语言描述符合我们的习惯，且容易理解。 3流程图描述：也称程序框图，它是算法的一种图形化表示方法。且描述算法形象、直观，更易理解。 4伪代码描述法：是介于自然语言和计算机程序语言之间的一种算法描述。是专业软件开发人员常用方法。 相关题解： 单选题 1、图形符号"在算法流程图描述中表示( B ). A 处理或运算的功能 B 输入输出操作 C D 算法的开始或结束 2、图形符号在算法流程图描述中表示( A ). A 输入输出操作 C 用来判断条件是否满足需求 D 算法的开始或结束 3、以下哪个是算法的描述方法( A ) A 流程图描述法 B 枚举法 C 顺序法 D 列表法 4、以下哪个是算法的描述方法( D ) A 顺序法 B 列表法 C 集合法 D 自然语言描述法 介于自然语言和计算机语言之间的一种算法描述是下列哪个选项（ ） B、流程图 C、高级语言 D、VB 程序设计语言 （二）程序设计基础 （1）常用高级编程语言：BASIC、VB、Pascal、C、C++、Java 1面向对象的程序设计语言：其中的对象主要是系统设计好的对象，包括窗体等、控件等 2控件：是指工具箱中的工具在窗体中画出的、能实现一定功能的部件，如文本框，命令按钮等。 对象属性＝属性值 对象中属性可以在设计界面时通过属性窗中设置，也可以在运行时通过程序代码设置,方法如下例：给文本框“Txt123”的“Text”属性赋值为字符串“20”，代码如下 =”20” 做课题与科研项目常用的研究方法 这段时间申报课题，看到很多老师对研究方法的名称写得不规范，故发如下内容： 研究方法不出“硬伤” 1、常用的研究方法有文献研究法、教育观察法、经验总结法、个案研究 法、行动研究法、实验研究法、历史研究法、调查研究法、比较研究法、叙事研究法等。 2、研究类型或途径、或某种提法口号不等于具体的研究方法。如实证研 究，调查研究、理论研究不能与具体的研究方法并列；理论联系实际、以点带面、上下结合等不是研究方法。 3、准确把握每种研究方法的概念特征、步骤方法。 如，文献研究法? A、概念特征：主要指围绕某个教育问题，搜集、鉴别、整理相关文献，并通过对文献的阅读与研究，形成对教育问题及其事实的科学认识的方法。 B、主要渠道： 。中国期刊网：。 C、查阅核心：（1）代表着作和论文；（2）研究问题的程度和主要观点；（3）存在的不足或有待进一步研究的问题。 D、成果形式：文献综述、研究述评或研究背景等。 再如，教育观察法 A、概念特征：是指主持人有目的、有计划地通过感官和辅助工具，对处于自 然状态下的教育现象进行系统观察，从而获得关于某一事物或者问题的第一手资料，并得出分析结果的一种研究方法。 B、研究步骤：①明确观察目的。②编制观察量表。③组建观察团队。④ 实施观察过程。⑤整理观察材料。⑥分析观察结果。 C、案例描述：观察目的、过程描述、观察数据表、事实描述、结论分析。 D、成果形式：观察日记、观察笔记、观察报告。 还如，个案研究法 A、概念特征：是对单一的研究对象（可以是个人或者团体机构）进行深入而具体研究的一种方法。又称“解剖麻雀法”和“个案追踪法”。其特征是个案的典型性、深入性、全面性。 B、研究分类：（1）追踪法。确定追踪研究的课题、实施追踪研究、整理和分析资料、提出改进意见。（2）追因法。确定问题、假设原因、设置对比、数据检验、结果分析。 （3）产品分析法。通过分析学生的活动产品，如日记、作文、书信、作业、自传、绘画、特长等，以了解学生的能力、倾向、技能、知识、情感等。 B、研究步骤：①确定研究对象。②搜集个案资料。③分析个案资料。④实施个案指导。⑤追踪指导研究。⑥撰写个案研究报告。 又如，经验总结法 1、概念特征：是指通过调查、总结、归纳、解决问题的经验和教训，揭示教育现象的本质及规律的一种研究方法。其特征是经验的新颖性、普遍性、实践性、发展性、实用性。特别注重经验的转化。 2、研究特点：概括主题、归纳要素、形成观点、揭示规律、验证理论。 3、基本步骤：①确立总结对象。②搜集相关材料。③现场相关调查。④分析关键资料。⑤撰写总结报告。 比如，叙事研究法 ? 1、概念特征：是指通过描述和分析有意义的教学事件、师生生活和教育教学实践经验，来发掘或揭示内隐于日常工作、事件和行为背后的意义、思想或理念，从中发现教育问题，探究教育思想，揭示教育活动特点和规律的一种方法。 ?2、研究特点：以“故事”为研究载体，以叙事为主要研究途径，采用口述、现场记录、日记、开放式访谈、自传等方式开展研究。 3.基本步骤：①确定研究问题。②选择研究对象。③记录教育故事。④分析得出结论。 再如，行动研究法 毕业论文 各种排序算法性能比较 系 专业姓名 班级学号 指导教师职称 设计时间 目录 摘要 (2) 第一章绪论 (3) 1.1 研究的背景及意义 (3) 1.2 研究现状 (3) 1.3 本文主要内容 (4) 第二章排序基本算法 (5) 2.1 直接插入排序 (5) 2.1.1基本原理 (5) 2.1.2排序过程 (5) 2.1.3时间复杂度分析 (5) 2.2 直接选择排序 (6) 2.2.1基本原理 (6) 2.2.2 排序过程 (6) 2.2.3 时间复杂度分析 (6) 2.3冒泡排序 (7) 2.3.1基本原理 (7) 2.3.2排序过程 (7) 2.3.3 时间复杂度分析 (8) 2.4 Shell排序 (8) 2.4.1基本原理 (8) 2.4.2排序过程 (9) 2.4.3时间复杂度分析 (9) 2.5堆排序 (9) 2.5.1基本原理 (9) 2.5.2排序过程 (10) 2.5.3时间复杂度分析 (13) 2.6快速排序 (13) 2.6.1基本原理 (13) 2.6.2排序过程 (14) 2.6.3时间复杂度分析 (15) 第三章系统设计 (16) 3.1数据定义 (16) 3.2 程序流程图 (16) 3.3 数据结构设计 (17) 3.4 系统的模块划分及模块功能实现 (17) 3.4.1系统模块划分 (17) 3.4.2各排序模块功能实现 (18) 第四章运行与测试 (29) 第五章总结 (31) 致谢 (32) 参考文献 (33) 江苏信息职业技术学院毕业论文 摘要 排序算法是数据结构这门课程核心内容之一。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。本毕业论文对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序以及堆排序算法进行比较。 我们设置待排序表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的比较次数和关键字的移动次数。 经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这六种算法中，快速排序比较和移动的次数是最少的。也是最快的一种排序方法。堆排序和快速排序差不多，属于同一个数量级。直接选择排序虽然交换次数很少，但比较次数较多。 关键字：直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序； 算法与程序设计思想 【基本信息】 【课标要求】 （一）利用计算机解决问题的基本过程 （1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。 （2）经历用自然语言、流程图或伪代码等方法描述算法的过程。 （4）了解程序设计语言、编辑程序、编译程序、连接程序以及程序开发环境等基本知识。 【学情分析】 高一年级的学生已具备了一定的观察、思考、分析和解决问题能力，也已有了顺序结构、分支结构、循环结构等知识的储备。因此，对于如何将解决问题的思路画成流程图已有一定的基础，但可能还不很熟练，尤其对刚学过的循环结构，教师在课堂上要注意引导。 『此处说“已有了顺序结构、分支结构、循环结构等知识的储备”，应该是指在必修部分对“计算机解决实际问题的基本过程”已有所体验与了解，或是指已学习过数学中相关模块的知识，这是本案例教学得以实施的必不可少的前提条件。』 【教学目标】 1.知识与技能： 建立求一批数据中最大值的算法设计思想，并将算法的设计思想用流程图表示出来。 2.过程与方法： 利用现实生活中比较身高的活动，以及对武术比赛中“打擂台”流程的逐步梳理，让学生学会从此类生活实际中提炼出求最大值的思想方法，即算法思想。 培养学生分析问题、解决问题的能力，让学生学会在面对问题时能梳理出解决问题的清晰思路，进而设计出解决某个特定问题的有限步骤，从而理解计算机是如何解决、处理某种问题的。 『在过程上，通过现实生活中的实例来引导学生总结“求最大值”的算法思想。过程的实现关键在于实例引用是否贴切，是否有利于学生向抽象结论的构建。本案例的实例选择是符合这一要求的。在方法上，注重培养学生分析、解决问题的一般能力，再次体验与理解应用计算机解决问题的基本过程，为后面更一步的学习打下基础，积累信心。』 3.情感态度与价值观： 研究方法归纳 调查法 调查法是科学研究中最常用的方法之一。它是有目的、有计划、有系统地搜集有关研究对象现实状况或历史状况的材料的方法。调查方法是科学研究中常用的基本研究方法，它综合运用历史法、观察法等方法以及谈话、问卷、个案研究、测验等科学方式，对教育现象进行有计划的、周密的和系统的了解，并对调查搜集到的大量资料进行分析、综合、比较、归纳，从而为人们提供规律性的知识。 调查法中最常用的是问卷调查法，它是以书面提出问题的方式搜集资料的一种研究方法，即调查者就调查项目编制成表式，分发或邮寄给有关人员，请示填写答案，然后回收整理、统计和研究。 观察法 观察法是指研究者根据一定的研究目的、研究提纲或观察表，用自己的感官和辅助工具去直接观察被研究对象，从而获得资料的一种方法。科学的观察具有目的性和计划性、系统性和可重复性。在科学实验和调查研究中，观察法具有如下几个方面的作用：①扩大人们的感性认识。②启发人们的思维。③导致新的发现。 实验法 实验法是通过主支变革、控制研究对象来发现与确认事物间的因果联系的一种科研方法。其主要特点是：第一、主动变革性。观察与调查都是在不干预研究对象的前提下去认识研究对象，发现其中的问题。而实验却要求主动操纵实验条件，人为地改变对象的存在方式、变化过程，使它服从于科学认识的需要。第二、控制性。科学实验要求根据研究的需要，借助各种方法技术，减少或消除各种可能影响科学的无关因素的干扰，在简化、纯化的状态下认识研究对象。第三，因果性。实验以发现、确认事物之间的因果联系的有效工具和必要途径。 文献研究法 文献研究法是根据一定的研究目的或课题，通过调查文献来获得资料，从而全面地、正确地了解掌握所要研究问题的一种方法。文献研究法被子广泛用于各种学科研究中。其作用有：①能了解有关问题的历史和现状，帮助确定研究课题。②能形成关于研究对象的一般印象，有助于观察和访问。③能得到现实资料的比较资料。④有助于了解事物的全貌。 实证研究法 实证研究法是科学实践研究的一种特殊形式。其依据现有的科学理论和实践的需要，提出设计，利用科学仪器和设备，在自然条件下，通过有目的有步骤地操纵，根据观察、记录、测定与此相伴随的现象的变化来确定条件与现象之间的因果关系的活动。主要目的在于说明各种自变量与某一个因变量的关系。 定量分析法 在科学研究中，通过定量分析法可以使人们对研究对象的认识进一步精确化，以便更加科学地揭示规律，把握本质，理清关系，预测事物的发展趋势。 一、逻辑判断：每题给出一段陈述，这段陈述被假设是正确的，不容置疑的。要求你根据这段陈 述，选择一个答案。注意，正确的答案应与所给的陈述相符合，不需要任何附加说明即可以从陈述 中直接推出 1．以下是一则广告：就瘘痛而言，四分之三的医院都会给病人使用"诺维克斯"镇痛剂。因此，你想 最有效地镇瘘痛，请选择"诺维克斯"。以下哪项如果为真，最强地削弱该广告的论点?( ) A．一些名牌的镇痛剂除了减少瘘痛外，还可减少其他的疼痛 B．许多通常不用"诺维克斯"的医院，对那些不适应医院常用药的人，也用"诺维克斯" C．许多药物制造商，以他们愿意提供的最低价格，销售这些产品给医院，从而增加他们产品的 销售额 D．和其他名牌的镇痛剂不一样，没有医生的处方，也可以在药店里买到"诺维克斯" 正确答案:C 2．会骑自行车的人比不会骑自行车的人学骑三轮车更困难。由于习惯于骑自行车，会骑自行车的人 在骑三轮车转弯时，对保持平衡没有足够的重视。据此可知骑自行车( )。 A．比骑三轮车省力 B．比三轮车更让人欢迎 C．转弯时比骑三轮车更容易保持平衡 D．比骑三轮车容易上坡 正确答案:C 解题思路：题干已知，不会骑自行车的人反而比会骑的人更容易学习骑三轮车，原因 是骑三轮车在转弯时需要更多地控制平衡，由此可以推断出选项C为正确答案，选项A、B、D与题干 无关。故选C。 3．长久以来认为，高水平的睾丸激素荷尔蒙是男性心脏病发作的主要原因。然而，这个观点不可能 正确，因为有心脏病的男性一般比没有心脏病的男性有显著低水平的睾丸激素。上面的论述是基于 下列哪一个假设的?( )。 A．从未患过心脏病的许多男性通常有低水平的睾丸激素 B．患心脏病不会显著降低男性的睾丸激素水平 C．除了睾丸激素以外的荷尔蒙水平显著影响一个人患心脏病的可能性 D．男性的心脏病和降低睾丸激素是一个相同原因的结果 正确答案:B 解题思路：题干推理过程为：有心脏病的男性的睾丸激素水平低于无心脏病的，所以高水平的睾丸激素荷尔蒙不是男性心脏病发作的主要原因。这里忽略了一个前提，即得了心脏病以后会不会降低原有的睾丸激素，如会，则推理不成立，如不会，则推理成立，所以答案为B。 4．某大学工会在三八妇女节组织卡拉OK大赛，关于外语学院由哪些人来参加比赛，领导 排序算法性能之比较 ----19090107 李萍 ?课程题目： 编程实现希尔、快速、堆排序、归并排序算法。要求随机产生待排数据存入磁盘文件，然后读入数据文件，实施排序后将数据写入另一个文件。 ?开发平台： ?算法描述： ◆希尔排序： 希尔排序(Shell Sort)是对直接插入排序的一种改进，其基本思想为：先将整个待排序列划分成若干子序列，在子序列内分别进行直接插入排序，然后重复上述的分组和排序；只是分组方法不同；最后对整个序列进行直接插入排序。 ◆快速排序： 快速排序几乎是最快的排序算法，被称为20世纪十大算法之一。其基本思想为：从待排序记录序列中选取一个记录(通常选取第一个记录为枢轴)，其关键字值设为k，将关键字值小于k的记录移到前面，而将关键字值大于k的记录移到后面，结果将待排序记录序列分成两个子表，最后将关键字值为k的记录插入到分界线处。这是一次“划分”。对划分后的子表继续按上述原则进行划分，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序序列。 ◆堆排序： 堆排序是选择排序的一种改进。堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左、右孩子结点的值(小顶堆)；或者每个结点都大于或等于其左、右孩子的值(大顶堆)。堆排序基本思想为(采用大顶堆)：首先待排序的记录序列构造成一个堆，此时选出堆中所有记录的最大者，即堆顶记录，然后将它从堆中移走(通常将堆顶记录和堆中最后一个记录交换)，并将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中只有一个记录为止。 ◆归并排序： 归并就是将两个或两个以上的有序序列合并成一个有序序列。归并排序的主要思想是：将若干有序序列逐步归并，最终归并为一个有序序列。 各种排序算法稳定性的探讨 首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。为了简便下面讨论的都是不降序排列的情形，对于不升序排列的情形讨论方法和结果完全相同。 其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。 回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。 (1)冒泡排序 冒泡排序是通过相邻比较、实时交换、缩小范围实现排序的。第1次操作n个元素，通过相邻比较将0~n-1中的最大元素交换到位置n-1上，第2次操作n-1个元素，通过相邻比较将0~n-2中的最大元素交换到位置n-2上……第n-1次操作2个元素，通过相邻比较将0~1上的最大元素交换到位置1上完成排序。在相邻比较时如果两个元素相等，一般不执行交换操作，因此冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是通过不断缩小排序序列长度来实现的。第1次操作n个元素，选择0~n-1中的最小者交换到位置0上，第2次操作n-1个元素，选择1~n-1中的最小者交换到位置1上……第n-1次操作2个元素，选择n-2~n-1上的最小者交换到位置n-2上完成排序。在每次选择最小元素进行交换时，可能破坏稳定性。这种情况可以描述为：约定要发生交换的位置称为当前位置，被交换的位置称为被交换位置，被交换位置上的元素为选中的最小元素。如果当前位置之后和被交换位置之前存在与当前位置相等的元素，执行交换后就破坏了稳定性。如序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 (3)插入排序 插入排序是通过不断扩大排序序列的长度来实现的。第1次操作1个元素，直接放到位置0上即可；第2次操作2个元素，在0~1上为当前元素找到合适位置并插入；第3次操作3个元素，用在0~2上为当前元素找到合适位置并插入它……第n次操作n个元素，在0~n-1上为当前元素找到合适位置并插入完成排序。讨论元素的插入过程，假设当前是第n次操作，要在0~n-1上为当前元素寻找合适位置，设置一个工作指针初始化为n-1，向前移动工作指针直到遇到一个不大于当前元素的元素，就在这个元素的后面插入当前元素，仔细体会这个插入过程，不难理解插入排序是稳定的。 (4)快速排序 快速排序有两个方向，左边的i下标当a[i] <= a[center]时一直往右走，其中center是中枢元素的数组下标，一般取为当前排序段的第一个元素。而右边的j下标当a[j] > a[center]时一直往左走。如果i和j都走不动了，这时必有结论a[i] > a[center] >= a[j]，我们的目的是将a 分成不大于a[center]和大于a[center]的两个部分，其中前者位于左半部分后者位于右半部分。所以如果i>j(i不能等于j，为什么？)表明已经分好，否则需要交换两者。当左右分好时，j 指向了左侧的最后一个元素，这时需要将a[center]与a[j],交换，这个时侯可能会破坏稳定性。 高一第二学期《算法与程序设计》学分认定试题 学校：_____________ 班级：____________ 学号：____________ 姓名：____________ 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么”，然后再确定程序“如何做”请问“如何做”是属于用计算机解决问题的哪一个步骤（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、 D、 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式A+B+C 研究方案（研究内容、研究方法） 研究内容：本文主要的研究目的是揭示我国图书馆危机管理的现状，发现存在的问题，进而提出办法将其解决。 拟从以下几个方面进行研究： 1 首先拟介绍危机管理论点的提出，分析危机管理理论的产生背景，及其引入我国图书馆学界所带来的重大意义； 2 拟分析图书馆危机管理的含义、成因以及特征，分析图书馆危机的存在对图书馆建设和发展的不利影响； 3 拟介绍对图书馆进行危机管理的意义，重点分析对图书馆进行危机管理的必要性，突出论文的主题； 4 拟分析国内外不同图书馆的危机管理现状，需要结合对国内图书馆的了解以及通过资料阅览得到的有关国外图书馆的情况的了解，进行论述，发现我国图书馆危机管理中存在的问题； 5 拟分析图书馆危机管理中存在的制约因素，以及这些制约因素对我国图书馆危机管理所带来的危害和影响； 6拟根据图书馆危机管理存在的制约因素，提出改进的措施，从不同的方面提出对策，如危机意识方面、管理机制方面、读者和政府方面，分别解决产生于不同方面的问题； 7 拟结合前文的综合论述，进行总结，同时重申论文的研究目标以及对图书馆事业的展望。 研究方法：结合本文的特点，本文的研究会用到以下几种方法 1文献检索法 本文的研究需要首先阅读大量的文献成果，才能总结出现在该论题的研究进展情况，找出以前研究的不足和避免研究内容的重复性；在了解国外图书馆危机管理现状和我国图书馆危机事件时，由于无法亲自调查研究，也需要借助文献检索法，通过各种资料的介绍进行分析总结。2比较分析法 在论文中将对国内与国外图书馆的服务现状进行分析，需要对两者的管理方式、技术、内容等各方面进行比较，总结出不同的特点，看出国内与国外存在的差距，还要分析出国内图书馆危机管理方面的不足，进而根据不足提出对策。 3理论联系实际的方法 对图书馆危机管理理论进行分析，结合管理理论分析我国图书馆危机管理发展的现状以及图书馆危机的产生原因及特征，提出改善图书馆危机管理现状对图书馆发展必要性；结合图书馆学的理论知识，提出各种解决的对策。 【下载本文档，可以自由复制内容或自由编辑修改内容，更多精彩文章，期待你的好评和关注，我将一如既往为您服务】 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统 —— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图： —— main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到各种排序算法比较
算法与程序设计习题
数据结构各种排序算法的时间性能
算法与程序设计(教科版)教案
论文中常用的研究方法
FBI变态心理测试题
几种排序算法的平均性能比较(实验报告)
高中信息技术算法及程序设计
做课题与科研项目常用的研究方法
各种排序算法性能比较
算法与程序设计教案
论文研究方法归纳
50道经典逻辑题及答案
排序算法性能比较报告
排序算法稳定性
算法与程序设计试题带答案
毕业论文的研究方案(研究内容、研究方法)
南邮数据结构上机实验四内排序算法的实现以及性能比较