（2）插入类排序法
插入类排序法主要有简单插入排序法和希尔排序法。
简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。在这种排序方法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n–1)/2次比较。
希尔排序法对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。
（3）选择类排序
选择类排序主要有简单选择类排序法和堆排序法。
简单选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的线性表，在最坏情况下需要比较n(n–1)/2次。
堆排序法也属于选择类排序法。具有n个元素的序列（h1, h2, …, hn），当且仅当满足条件：
或
(i=1, 2, …, n/2）时称之为堆。可见，堆顶元素（即第一个元素）必为最大项。
堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。
程序设计基础
1．程序设计方法与风格
除了好的程序设计方法和技术外，程序设计风格也是很重要的内容。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。要形成良好的程序设计风格，主要应注重和考虑下述一些因素。
（1）源程序文档化
符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。
程序注释：注释一般分为序言性注释和功能性注释。序言性注释通常位于每个程序的开头部分，它给出程序的整体说明；而功能性注释的位置一般嵌在源程序体中，主要描述其后的语句或程序做什么。
视觉组织：可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。
（2）数据说明的方法
主要包括数据说明的次序规范化、说明语句中变量安排有序化和使用注释来说明复杂数据结构等。
（3）语句的结构
语句构造应该简单直接，不应该为提高效率而把语句复杂化。
（4）输入和输出
输入和输出方式和格式应尽可能方便用户的使用。
2．结构化程序设计
结构化程序设计的主要原则、设计要素应是重点掌握的内容。
由于软件危机的出现，人们开始研究程序设计方法，其中最受关注的是结构化程序设计方法。结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化、限制使用goto语句。
在结构化程序设计的具体实施中，要注意把握如下要素。
（1）使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。
（2）使用的控制结构只准许有一个入口和一个出口。
（3）程序语句组成容易识别的块，每块只有一个入口和一个出口。
（4）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。
（5）语言中所没有的控制结构，应该采用前后一致的方法来模拟。
（6）严格控制goto语句的使用。
3．面向对象的程序设计及其重要概念
面向对象的程序设计方法及其有关概念是重点掌握的内容，也是考试的重点。
面向对象的程序方法主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。它具有与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好等优点。
在面向对象的程序方法中，有如下重要的概念。
（1）对象
用来表示客观世界中的任何实体，即应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象。它既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界和意义的东西。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。
操作描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。
（2）类和实例
将属性、操作相似的对象归为类，即是具有共同属性、共同方法的对象的集合。因此，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。
（3）消息
面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息，它请示对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。一个消息由接收消息的对象的名称、消息标识符（即消息名）、零个或多个参数组成。
（4）继承
继承是面向对象的方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当做基类来引用，则新类相应地可当做派生类来引用。一个类的上层可以有父类，下层可以有子类。一个类直接继承其父类的描述（数据和操作）或特性，子类自动地共享基类中定义的数据和方法。
（5）多态性
对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。
