1.8　排序技术

【考点1】交换类排序法

（1）冒泡排序法

①定义：冒泡排序法是一种最简单的交换类排序方法，通过相邻数据元素的交换逐步将线性表变成有序。

②基本过程：

a．从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。

b．从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。

c．对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。

③在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。

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

（2）快速排序法

①基本思想

从线性表中选取一个元素T，将线性表后面小于T的元素移到前面，前面大于T的元素移到后面，这样就以T为分割线将线性表分割成前后两个子表。再将得到的子表按照这个过程继续下去，直到所有子表为空为止。

②快速排序在最坏情况下需要进行n（n－1）/2次比较，但实际的排序效率要比冒泡排序高得多。

【考点2】插入类排序法

（1）简单插入排序法

①定义：所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。

②插入过程：

将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j－1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。

③这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n（n－1）/2次比较。

（2）希尔排序法

①基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。

②子序列的分割方法：

将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般取h_t＝n/2^k（k＝1，2，…，[log₂n]），其中n为待排序序列的长度。

③如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为O（n^1.5）。

【真题演练】

在最坏情况下（　　）。[2015年3月真题]

A．快速排序的时间复杂度比冒泡排序的时间复杂度要小

B．快速排序的时间复杂度比希尔排序的时间复杂度要小

C．希尔排序的时间复杂度比直接插入排序的时间复杂度要小

D．快速排序的时间复杂度与希尔排序的时间复杂度是一样的

【答案】C

【解析】快速排序与冒泡排序的时间复杂度均为O(n²)，A项错误；快速排序比希尔排序的时间复杂度要大（O(n²)>O(n^1.5)），B、D项错误；希尔排序的时间复杂度比直接插入排序的时间复杂度要小（O(n^1.5)<O(n²)），C项正确。答案选择C选项。

【考点3】选择类排序法

（1）简单选择排序法

①基本思想：

扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。

②简单选择排序法在最坏情况下需要比较n（n－1）/2次。

（2）堆排序法

①堆的定义

具有n个元素的序列（h₁，h₂，…，h_n），当且仅当满足

称之为堆。

②堆排序的方法：

a．将一个无序序列建成堆；

b．将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）；

c．反复做上一步，直到剩下的子序列为空为止。

③在最坏情况下，堆排序需要比较的次数为O（nlog₂n）。

【真题演练】

1下列各序列中不是堆的是（　　）。[2014年9月真题]

A．(91,85,53,36,47,30,24,12)

B．(91,85,53,47,36,30,24,12)

C．(47,91,53,85,30,12,24,36)

D．(91,85,53,47,30,12,24,36)

【答案】C

【解析】堆可以看成一棵完全二叉树：堆中任一根结点的值大于等于左右孩子结点的值（或者小于等于）就叫做大根堆（或小根堆）。这题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显91是最大的值，而C选项是“左根右”的排序，那么91的左边只有47，其他都在右边，而右边无法按照此顺序排列，答案选择C选项。

2对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是（　　）。[2013年9月真题]

A．快速排序

B．冒泡排序

C．直接插入排序

D．堆排序

【答案】D

【解析】在最坏情况下，快速排序、冒泡排序、直接插入排序与简单选择排序法均需要比较n(n-1)/2次。堆排序需要比较的次数最少，为nlog₂n。答案选择D选项。

3堆排序最坏情况下的时间复杂度为（　　）。[2014年9月真题]

A．O(n¹⁵)

B．O(nlog₂n)

C．O(n(n-1)/2)

D．O(log₂n)

【答案】B

【解析】堆排序是指利用堆积树这种数据结构所设计的一种排序算法，属于选择排序。在对长度为n的线性表排序时，最坏情况下，冒泡排序、快速排序、直接插入排序的时间复杂度均为O(n²)，而堆排序时间复杂度为O(nlog₂n)，复杂度最小。答案选择B选项。