2018计算机二级考试公共基础知识点:排序技术

考点交换类排序方法11

考试链接:

考点11是比较难的内容，一般以选择题的形式考查。考核概率30%，分值2分左右。读者应该熟悉几种排序算法的基本流程。

冒泡排序法和快速排序法都属于交换排序法。

(1)冒泡排序法

首先从表头开始向后扫描线性表，逐个比较相邻两个元素的大小。如果前一个元素大于后一个元素，则进行交换，两个相邻元素中最大的一个不断向后移动，最后最大的一个到达线性表的末尾。

然后从后向前扫描剩下的线性表，逐个比较相邻两个元素的大小。如果后一个元素小于前一个元素，则将它们交换，两个相邻元素中较小的一个继续向前移动，最后最小的一个来到线性表的前面。

对剩余的线性表重复上述过程，直到剩余的线性表为空，此时已经排列好顺序。

在最坏的情况下，冒泡排序需要比较n(n-1)/2。

(2)快速排序法

其基本思想是:以待排序序列中的任意元素为基准(一般为第一个元素)，通过一次排序将待排序元素分成两个子序列，左子序列元素的排序码小于或等于基准元素的排序码，右子序列大于基准元素的排序码，然后继续分别对两个子序列进行排序，直到整个序列有序。