内容发布更新时间 : 2024/5/5 14:55:05星期一 下面是文章的全部内容请认真阅读。

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

排序

排序（Sorting）是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。 简单排序算法

简单排序算法包括冒泡排序、插入排序、选择排序。这三种算法容易理解、编写方便，适用于数据规模较小的情形。 冒泡排序

基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

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

首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。

重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。

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

效率分析

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

时间效率：总共要进行n-1趟冒泡，对n个记录的表进行一趟冒泡需要n-1次数值大小比较。

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

基本思想：依次将每个记录插入到一个有序中去。就是说，第i遍整理时，A1,A2,...,Ai-1已经是排好序的子序列；取出第i个元素Ai，在已排好序的子序列为Ai找到一个合适的位置，并将它插到该位置上。易知上述排序当i=1时实际上为空操作，故可直接从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!) ——有时搜索算法的时间复杂度