课堂练习

1. 【NOIP2011】体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于( )算法。
   A. 快速排序
   B. 插入排序
   C. 冒泡排序
   D. 归并排序
   【答案】B
   【分析】插入排序基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
2. 【NOIP2018】以下排序算法中，不需要进行关键字比较操作的算法是( )。
   A. 基数排序
   B. 冒泡排序
   C. 堆排序
   D. 直接插入排序
   【答案】A
   【分析】冒泡排序、堆排序和插入排序都是基于两两元素关键字比较的排序。基数排序是直接将元素通过某些规则放到数组的相应位置，不是基于两两元素关键字比较的排序。
3. 【NOIP2009】排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列排序算法不稳定的是( )。
   A. 冒泡排序
   B. 插入排序
   C. 归并排序
   D. 快速排序
   【答案】D
   【分析】快速排序会使数据左右调换，让值相同的两个元素的相对位置发生变化，而这个变化是不稳定的原因。
4. 【NOIP2009】快速排序最坏情况下的算法复杂度为( )。
   A. $O(logn)$
   B. $O(n)$
   C. $O(nlogn)$
   D. $O(n^{2})$
   【答案】D
   【分析】假设当快速排序时选择的轴值总数是最靠边的数，且当输入数据有序时，快速排序就退化成了冒泡排序。
5. 【NOIP2009】快速排序平均情况和最坏情况下的算法时间复杂度分别为( )。
   A. 平均情况$O(nlogn)$，最坏情况$O(n^{2})$
   B. 平均情况$O(n)$，最坏情况$O(n^{2})$
   C. 平均情况$O(n)$，最坏情况$O(nlogn)$
   D. 平均情况$O(logn)$，最坏情况$O(n^{2})$
   【答案】A
   【分析】快速排序平均情况时间复杂度是$O(n log_{2} n)$，最坏情况是$O(n^{2})$ 。
6. 【NOIP2012】如果不在快速排序中引入随机化，有可能导致的后果是( )。
   A. 数组访问越界
   B. 陷入死循环
   C. 排序结果错误
   D. 排序时间退化为平方级
   【答案】D
   【分析】快速排序的期望时间复杂度是$O(nlogn)$，最坏情况（例如排一个已经排好序的序列）是$O(n^{2})$ 。
7. 【NOIP2010】基于比较的排序时间复杂度的下限是( )，其中$n$是待排的元素个数。
   A. $O(n)$
   B. $O(nlogn)$
   C. $O(logn)$
   D. $O(n^{2})$
   【答案】B
   【分析】快速排序、归并排序都是基于比较的排序，时间复杂度不会低于$nlogn$。而桶排序、基数排序都不是基于比较的排序。
8. 【NOIP2013】( )的平均时间复杂度为$O(nlogn)$，其中$n$是待排序的元素个数。
   A. 快速排序
   B. 插入排序
   C. 冒泡排序
   D. 基数排序
   【答案】A
   【分析】快速排序平均时间复杂度均为$O(nlogn)$，而插入排序和冒泡排序的平均时间复杂度为$O(n^{2})$ 。基数排序的时间复杂度，还取决于待排序的数字的位数。
9. 【NOIP2014】以下时间复杂度不是$O(n^{2})$的排序方法是( )。
   A. 插入排序
   B. 归并排序
   C. 冒泡排序
   D. 选择排序
   【答案】B
   【分析】归并排序的时间复杂度是$O(nlogn)$。
10. 【NOIP2017】对于给定的序列$\{a_{k}\}$，我们把$(i, j)$称为逆序对当且仅当$i<j$且$a_{i}>a_{j}$ 。那么序列1, 7, 2, 3, 5, 4的逆序对数为( )个。
    A. 4
    B. 5
    C. 6
    D. 7
    【答案】B
    【分析】按照逆序对的标准，依次清点一下即可，每个数字查看右侧有几个比自己小的。逆序对为$(7, 2)$，$(7, 3)$，$(7, 5)$，$(7, 4)$，$(5, 4)$。
11. 【NOIP2012】使用冒泡排序对序列进行升序排序，每执行一次交换操作将会减少1个逆序对，因此序列5, 4, 3, 2, 1需要执行( )次交换操作，才能完成冒泡排序。
    A. 0
    B. 5
    C. 10
    D. 15
    【答案】C
    【分析】在数组中，如果$i<j$但$a[i]>a[j]$，我们称其为一对逆序对。根据题目意思每交换一次会减少一个逆序对，所以交换次数等于逆序对数等于10，逆序对分别为$(5, 4)$、$(5, 3)$、$(5, 2)$、$(5, 1)$、$(4, 3)$、$(4, 2)$、$(4, 1)$、$(3, 2)$、$(3, 1)$、$(2, 1)$。
12. 【NOIP2017】设$A$和$B$是两个长为$n$的有序数组，现在需要将$A$和$B$合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做( )次比较。
    A. $n^{2}$
    B. $nlogn$
    C. $2n$
    D. $2n - 1$
    【答案】D
    【分析1】考察归并排序算法中归并的过程。对于两个长度为$n$的有序数组，首先我们考虑合并有序数组的方式肯定是比较序列的头，选一个出来放到新的序列中，当某个序列为空的时候，就另外一个序列的数组依次放到最后。最坏情况下显然是两个数组依次弹出数字，直到最后一个数组仅剩下一个数字。这种情况下，除去最后一个数字以外每一个数字都进行了一次比较，所以总共需要比较$2n - 1$次。 【分析2】归并排序当有一方为空的时候，就可以不用再进行比较，直接将另一方剩余元素接在数组后面即可。否则每进行一次比较，均有一个元素可以接到数组后面，故总比较次数为总元素个数减去一方为空时另一方的剩余元素个数。所以，最少的剩余元素是1，最多的比较次数为$2n - 1$。

不定项选择题

1. 【NOIP2009】排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列排序算法稳定的是( )。
   A. 插入排序
   B. 基数排序
   C. 归并排序
   D. 冒泡排序
   【答案】ABCD
   【分析】希尔排序、快速排序、选择排序、堆排序都是不稳定的。
2. 【NOIP2017】下列算法中，( )是稳定的排序算法。
   A. 快速排序
   B. 堆排序
   C. 希尔排序
   D. 插入排序
   【答案】D
   【分析】稳定的排序指的是对于原序列两个相等的元素，在排完序之后前后位置关系仍然保持不变。只有插入排序是相邻元素的比较，碰到相等不需要交换，所以可以保持相等元素的顺序不改变，其他三个排序都不是相邻元素的比较，因此并不是稳定的排序。
3. 【NOIP2010】原地排序是指在排序过程中（除了存储待排序元素以外的）辅助空间的大小与数据规模无关的排序算法。以下属于原地排序的有( )。
   A. 冒泡排序
   B. 插入排序
   C. 基数排序
   D. 选择排序
   【答案】ABD
   【分析】只有基数排序需要额外的“桶”记录临时排序结果，其余选项均为原地排序。
4. 【NOIP2016】下列算法中运用分治思想的有( )。
   A. 快速排序
   B. 归并排序
   C. 冒泡排序
   D. 计数排序
   【答案】AB
   【分析】快速排序和归并排序都是分治算法的经典案例。
5. 【NOIP2013】( )的平均时间复杂度为$O(nlogn)$，其中$n$是待排序的元素个数。
   A. 快速排序
   B. 插入排序
   C. 冒泡排序
   D. 归并排序
   【答案】AD
   【分析】快速排序和归并排序的平均时间复杂度均为$O(nlogn)$，而插入排序和冒泡排序的平均时间复杂度为$O(n^{2})$ 。
6. 【NOIP2017】以下排序算法在最坏情况下时间复杂度最优的有( )。
   A. 冒泡排序
   B. 快速排序
   C. 归并排序
   D. 堆排序
   【答案】CD
   【分析】冒泡排序和快速排序最坏情况下的时间复杂度为$O(n^{2})$ ，而归并排序和堆排序是稳定的$O(nlogn)$。
7. 【NOIP2011】对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉( )会使逆序对的个数减少3。
   A. 7
   B. 5
   C. 3
   D. 6
   【答案】CD
   【分析】对于一个包含$N$个非负整数的数组$A[1…]$，如果有$i<j$，且$A[i]>A[j]$ ，则称$(A[i], A[j])$为数组$A$中的一个逆序对。此序列的逆序列有14对：$(7, 5)$，$(7, 1)$，$(7, 3)$，$(7, 6)$，$(7, 4)$，$(5, 1)$，$(5, 3)$，$(5, 4)$，$(9, 3)$，$(9, 6)$，$(9, 8)$，$(9, 4)$，$(6, 4)$，$(8, 4)$。如果要使其逆序列的个数减少3对，则将其中出现了3次的数字删除即可。7出现了5次，5出现了4次，1出现了2次，9出现了4次，3出现了3次，6出现了3次，8出现了2次，4出现了5次。故数字3和6是满足题意的。