（2）快速排序
基本思想：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。 快速排序的平均时间复杂度为O(nlog2n)。
基准元素初始序列第1次交换后第2次交换后第3次交换后第4次交换后【46 55 13 42 94 05 17 70 】i【17iijjjj13 42 94 55 70 】ij55 70 】j55 13 42 94 05 70 】【17 13 42 94 05 55 70 】i【17 05i【17 05 13 42 94ijj完成一趟排序【17 05 13 42】46【94 55 70 】
真题讲解：2005年4月选择题第3题，2006年4月填空题第1题。 2、插入类排序法
基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
方法：简单插入排序，希尔排序。 （1）简单插入排序法
16
基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。 在最坏的情况下，需要n(n-1)/2次比较。
初始序列第1趟排序第2趟排序第3趟排序第4趟排序第5趟排序第6趟排序第7趟排序【49】38 65 97 76 13 27 49(38) 【38 49】65 97 76 13 27 49(65) 【38 49 65】97 76 13 27 49(97) 【38 49 65 97】76 13 27 49(76) 【38 49 65 76 97】13 27 49(13) 【13 38 49 65 76 97】27 49(27) 【13 27 38 49 65 76 97】49(49) 【13 27 38 49 4965 76 97】
（2）希尔排序
基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个增量h的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。
增量序列一般取 ，其中n为
2hi?n/2(k?1,2,?,[logkn])待排序序列的长度。
在最坏情况下，希尔排序的时间复杂度为 。
O(n1.5) 17
初始序列49 38 65 97 76 13 27 4949 13 38 27 65 4955 0497 55 76 04 第1趟排序结果13 27 4955 04 49 38 65 97 7613 55 38 7627 04 65 49第2趟排序结果第3趟排序结果13 04 4949 97 38 27 49 55 65 97 7604 13 27 38 49 49 55 65 76 97
3、选择类排序法
基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕。
方法：简单选择排序，堆排序。 （1）简单选择排序法
基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。
最坏情况下，需要比较n(n-1)/2次。
初始序列第1趟排序第2趟排序第3趟排序第4趟排序第5趟排序第6趟排序第7趟排序【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 【76 97 65 49】13 27 38 49 49【97 65 76】13 27 38 49 4913 27 38 49 4965 【97 76】65 76 【97】
（2）堆排序法
18
堆的定义：具有n个元素的序列，当且仅当满足 ?h??hi?h2i?1i?h2i ① 或 ②
时称之为堆。①称为大根堆；②称为小根堆 。
建堆：在建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。 堆排序：
1）首先将一个无序序列建成堆。
2）然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。
反复做步骤2），直到剩下的子序列为空为止。
19
2556157010?hi?h2i??hi?h2i?130155610253070(a)大根堆(b)小根堆在最坏情况下，堆排序法需要比较的次数为O(nlog2n)。 总结：各种排序法比较：
第二章 程序设计基础
2.1 程序设计风格
要形成良好的程序设计风格，主要应注重和考虑下述一些因素：源程序文档化、数据说明的方法、语句的结构、输入和输出。
原则：清晰第一，效率第二。 *：注释分序言性注释和功能性注释。 真题讲解：2006年9月选择题第1题。
2.2 结构化程序设计（面向过程的程序设计方法） 结构化程序设计方法的主要原则可以概括为：自顶向下，逐步求精，模块化，限制使用goto语句。
1、自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体
20