2011年计算机二级公共基础知识考点串讲（8）

文章作者 100test 发表时间 2011:07:06 05:46:22
来源 100Test.Com百考试题网

　　1.8排充技术

　　1.8.1交换类排序法 (P34—P35)

　　1. 冒泡排序法

　　冒泡排序法是一种最简单的交换类排序方法。

　　假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为n(n-1)/2。

　　2. 快速排序法

　　快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。

　　1.8.2插入类排序法 (P35—P37)

　　1. 简单插入排序法

　　自以为插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。

　　在简单插入排序法中，这种排序方法的效率与冒泡排序法相同。在最坏情况下，证券交易插入排序需要n(n-1)/2次比较。

　　2. 希尔排序法

　　希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。

　　1.8.3选择类排序法 (P37—P38)

　　1. 简单选择排序法

　　从中选出最小的元素，将它交换到表的最前面。

　　简单选择排序法在最坏情况下需要比较n(n-2)/2次。

　　2. 堆排序法

　　堆排序法属于选择类的排序方法。

　　堆排序的方法对于规模较小的线性表并不合适，但对于较大规模的来说是很有效的。