考点8 排序技术

1.交换类排序法

交换类排序法是指借助数据元素的“交换”进行排序的一种方法。本节介绍的冒泡排序法和快速排序法就是属于交换类排序法。

（1）冒泡排序法。

冒泡排序的基本思想。

在线性表中依次查找相邻的数据元素，将表中最大的元素不断往后移动，反复操作直到消除所有逆序。此时，该表已经排序结束。

冒泡排序法的基本过程。

①从表头开始往后查找线性表，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，前面的元素大于后面的元素，则将它们交换。

②从后向前查找剩下的线性表（除去最后一个元素），同样，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，后面的元素小于前面的元素，则将它们交换。

③对剩下的线性表重复上述过程，直到剩下的线性表变空为止，线性表排序完成。

假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n／2遍从前往后的扫描和n／2遍从后往前扫描，需要比较n（n-1）／2次，其数量级为n2。

（2）快速排序法。

快速排序法的基本思想。

在线性表中逐个选取元素，将线性表进行分割，直到所有元素全部选取完毕，此时线性表已经排序结束。

快速排序法的基本过程。

①从线性表中选取一个元素，设为T，将线性表后面小于T的元素移动到前面，而将大于T的元素移到后面，这样就将线性表分成了两部分（称为两个子表）。T就是处于分界线的位置，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后子表中的所有元素均不小于T，此过程称为线性表的分割。

②对分割后的子表再按上述原则进行反复分割，直到所有子表为空为止，则此时的线性表就变成有序。

真考链接

考核概率为25%，考生需要掌握该考点内容，主要是各种排序方法的概念、基本思想以及它们的复杂度。

2.插入类排序法

插入排序是指将无序序列中的各元素依次插入已经有序的线性表中。本节将主要介绍简单插入排序法和希尔排序法。

（1）简单插入排序法。

简单插入排序是把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n，而无序表为空，此时排序完成。

在简单插入排序中，每一次比较后最多移除一个逆序，因此，该排序方法的效率与冒泡排序法相同。一般简单插入排序需要n（n-1）／2次比较。

（2）希尔排序法。

希尔排序法是将整个无序序列分割成若干个小的子序列并分别进行插入排序。

分割方法如下：

①将相隔某个增量h的元素构成一个子序列；

②在排序过程中，逐次减少这个增量，直到h减到1时，进行一次插入排序，排序即可完成。

希尔排序的效率与所选取的增量序列有关。

3.选择类排序法

选择排序是通过每次从待排序序列中选出的最小值是元素，顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。下面就介绍选择类排序法中的简单选择排序法和堆排序法。

（1）简单选择排序法。

进行简单选择排序，首先从所有n个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的n-1个元素中选出最小的元素与第二个元素交换。重复这样的操作直到所有的元素有序为止。

简单选择排序需要比较n（n-1）／2次。

（2）堆排序法。

堆排序的方法如下：

①将一个无序序列建成堆；

②将堆顶元素与堆中最后一个元素交换。忽略已经交换到最后的那个元素，考虑前n-1个元素构成的子序列，只有左、右子树是堆，可以将该子树调整为堆。这样反复下去做第二步，直到剩下的子序列空为止。

堆排序需要比较的次数为O（nlog2n）。

真题精选

对于长度为n的线性表，下列各排序法所对应的比较次数中正确的是______。

A）冒泡排序为n／2

B）冒泡排序为n

C）快速排序为n

D）快速排序为n（n-1）／2

【答案】D

【解析】假设线性表的长度为n，则冒泡排序需要经过n／2遍的从前往后扫描和n／2遍的从后往前扫描，需要比较次数为n（n-1）／2。快速排序法在最坏的情况下，比较次数也是n（n-1）／2。

常见问题

为什么只有二叉树的前序遍历和后序遍历不能唯一确定一棵二叉树？

在二叉树遍历中前序和后序中都可以肯定根节点，在中序是由左至根及右的顺序，所以知道前序（或后序）和中序肯定能唯一确定二叉树；在前序和后序中只能确定根节点而对于左右子树的节点元素没办法正确选取，所以很难确定一个二叉树。由此可见需要确定一棵二叉树的基础是必须得知道中序遍历。