数据结构与算法中的数组、排序及复杂度分析

# 数据结构与算法中的数组、排序及复杂度分析 ## 1. 数组操作与 Big O 表示法 ### 1.1 类对象与数组处理 类对象可以像基本类型一样，由数据存储结构进行处理。不过，如果使用姓氏作为键编写程序，需要考虑姓氏重复的情况，这会使编程变得复杂。 ### 1.2 Big O 表示法简介 汽车按大小分为不同类别，如超小型、紧凑型、中型等，这样能快速了解汽车大小，无需提及实际尺寸。类似地，在计算机科学中，“Big O” 表示法用于简洁描述计算机算法的效率。在比较算法时，说 “算法 A 比算法 B 快两倍” 意义不大，因为随着数据项数量的变化，这种比例关系会发生很大改变。我们需要一种能体现算法速度与数据项数量关系的比较方法。 ### 1.3 不同算法的时间复杂度 - **无序数组插入**：插入无序数组时，新元素总是放在下一个可用位置，即 `a[nElems]`，然后 `nElems` 加 1。插入所需时间与数组中元素的数量无关，是一个常数 `K`，即 `T = K`。在实际情况中，插入所需的实际时间与微处理器速度、编译器生成代码的效率等因素有关，通过测量插入操作的时间可得到 `K` 的值。 - **线性搜索**：在数组中进行线性搜索时，平均需要进行的比较次数是元素总数的一半。若数组元素总数为 `N`，搜索时间 `T` 与 `N/2` 成正比，即 `T = K * N / 2`。为了方便，可将 `2` 合并到 `K` 中，得到 `T = K * N`，这表明平均线性搜索时间与数组大小成正比。 - **二分搜索**：二分搜索的时间 `T` 与 `log2(N)` 成正比，即 `T = K * log2(N)`。由于不同底数的对数之间存在常数关系，可将该常数合并到 `K` 中，得到 `T = K * log(N)`。 ### 1.4 Big O 表示法的应用 Big O 表示法去掉了常数 `K`，只关注 `T` 随 `N` 的变化情况。线性搜索的时间复杂度为 `O(N)`，二分搜索为 `O(log N)`，无序数组插入为 `O(1)`（常数时间）。常见算法的 Big O 时间复杂度总结如下表： | 算法 | Big O 表示法下的运行时间 | | --- | --- | | 线性搜索 | O(N) | | 二分搜索 | O(log N) | | 无序数组插入 | O(1) | | 有序数组插入 | O(N) | | 无序数组删除 | O(N) | | 有序数组删除 | O(N) | 根据 Big O 时间复杂度与元素数量的关系图，可对不同的 Big O 值进行主观评级：`O(1)` 优秀，`O(log N)` 良好，`O(N)` 一般，`O(N²)` 较差。`O(N²)` 常见于冒泡排序和一些图算法中。 ### 1.5 数组的局限性 数组虽然能完成数据存储任务，但存在一些缺点。无序数组插入快（`O(1)`），但搜索和删除慢（`O(N)`）；有序数组搜索快（`O(logN)`），但插入慢（`O(N)`）。而且，数组删除操作平均需要移动一半的元素，时间复杂度为 `O(N)`。另外，数组创建时大小固定，若预估过大，会浪费内存；若预估过小，会导致数组溢出，可能引发程序错误。相比之下，链表等其他数据结构更灵活，可根据插入元素的数量动态扩展。Java 中的 `Vector` 类类似数组，但具有可扩展性，不过会损失一些效率。 ## 2. 简单排序算法 ### 2.1 排序的重要性 在创建大型数据库时，通常需要对数据进行各种排序，如按字母顺序排列姓名、按成绩排列学生等。排序也是搜索的预处理步骤，有序数组可使用二分搜索，比线性搜索快得多。 ### 2.2 简单排序算法