信息学奥赛 NOIP初赛复习13排序与算法复杂度.pdfVIP

NOIP初赛复习13排序与算法复杂度

排序

排序（Sorting）是计算机程序设计中的一种重要操作，其功能是对一个数据元

素集合或序列重新排列成一个按数据元素某个项值有序的序列。

简单排序算法

简单排序算法包括冒泡排序、插入排序、选择排序。这三种算法容易理解、编写

方便，适用于数据规模较小的情形。

冒泡排序

基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交

换，直到没有反序的记录为止。

排序方法：依次比较相邻的两个数，将大数放在前面，小数放在后面。

首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第

3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，

小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。

重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的

交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较

到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个

数中得到一个新的最小数。

如此下去，直至最终完成排序。

效率分析

空间效率：仅用了一个辅助交换单元。

时间效率：总共要进行n-1趟冒泡，对n个记录的表进行一趟冒泡需要n-1

次数值大小比较。

移动次数：最好情况下，待排序列已有序，不需移动。

直接插入排序

基本思想：依次将每个记录插入到一个有序中去。就是说，第i遍整理时，

A,A,...,A已经是排好序的子序列；取出第i个元素A在已排好序的子序列

12i-1i，

为A找到一个合适的位置，并将它插到该位置上。易知上述排序当i=1时实际

i

上为空操作，故可直接从i=2开始。

排序方法：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列

中的适当位置，直到全部记录插入完毕为止。

效率分析

空间效率：仅用了一个辅助单元。

时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比

较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码

的初始排列。

对于NOIP提高组而言，这些算法时间复杂度过高，很难应付较大的数据规模。建议尽量

不要采用简单排序算法，除非你十分确信数据规模在可承受范围之内。

快速排序

基本思想：基于分治思想。（以从小到大排序为例）取一个数作为标记元素，将

比它大的数放在它右侧，比它小的数放在它左侧，再通过递归的方法，将左侧的

数用以上的方法排好，右侧的数也用以上的方法排好即可。

在数据规模很大时，平均情况下快排比冒泡快很多。在处理NOIP提高组含排序的问题时，

一般要选择快速排序或堆排序。

排序方法：运用分治思想，因而要用函数的递归调用来实现。

快速排序实现方法的最差情形是排列整齐的情况，这时它的运行效率会很低。为

了解决排列整齐的情形，我们可以使用随机快速排序法，即随机选取一个数作为

标记元素（实现时，将其与第一个数交换即可）。

算法时空复杂度

为了描述一个算法的优劣，我们引入算法时间复杂度和空间复杂度的概念。

时间复杂度：一个算法主要运算的次数，用O()表示。通常表示时间复杂度时，

我们只保留影响最大的项，并忽略该项的系数。

例如主要运算为赋值的算法，赋值做了3n^3+n^2+8次，则认为它的复杂度为

O(n^3)；若主要运算为比较，比较做了4*2^n+2*n^4+700次，由于数据很

大时，指数级增长的2^n影响最大，我们认为它的时间复杂度为O(2^n)。

常见的时间复杂度：

O(n)——贪心算法多数情况下为此时间复杂度

O(nlbn)——有时带有分治思想的算法的时间复杂度

(注lbn表示以2为底的n的对数)

O(n^2)——有时动态规划的时间复杂度

O(n^3)——有时动态规划的时间复杂度O(2^n)——有时有哪些信誉好的足球投注网站算法的时间复杂度

O(n!)——有时有哪些信誉好的足球投注网站算法的时间复杂度

O(m*n)——有时时间复杂度中含有两个或多个字母，比如遍历一个m*n的矩阵，时间复

杂度为O(m*n)

要注意的是，时间复杂度相同的两个算法，它的实际执行时间可能会有数倍的差

距，因而实现时要特别注意细节处的优化。

NOIP提高组执行时限常常为1s。一般认为，将数据规模代入到时间复杂度，若所得值小

于或接近于1000000，就是绝对安全的、不超时的。