【DAY11 软考中级备考笔记】数据结构 查找和排序

数据结构 查找和排序 3月12日 – 天气：晴

1. 顺序查找

顺序查找就是简单的从头一个一个的进行比较，注意它的平均查找长度

2. 折半查找

折半查找和二叉排序树一致：

优点：查找效率很高

缺点：要求必须是循序存储并且表中元素必须有序

3. 分块查找

分块查找实际上是结合了折半查找和顺序查找两种方式。

注意ASL的计算方式

优点：查找效率高于顺序查找，低于折半查找

4. 哈希表

使用取余的方法，需要注意取余的值：

取余的那个值 大于等于元素个数，小于等于比当前个数大的第一个质数。假设元素个数为9，则m的取值范围为【9，11】

采用链地址法的优点和不足：

• 优点：平均查找长度短
• 缺点：需要存储大量的指针，导致空间的浪费

5. 直接插入排序

• 思想：直接插入排序的思想是向序列分为有序序列和无序序列。每次都从无序序列中取出一个值，然后跟有序序列的值一次进行比较，找到和事的位置进行插入。

• 确定性：因此插入排序中在未完成时，没有一个元素的值时确定的。

• 稳定性：稳定的

• 时间复杂度：最好的情况下，只需要比较n-1次，最坏的情况是n^2

• 空间复杂度：1

6. 希尔排序

• 思想：希尔排序是直接插入排序的改进。它首先将元素进行分组，在组内进行直接插入排序，随着增量的逐渐减小，最终使得整个序列都有序
• 确定性：不确定
• 稳定性：不稳定
• 时间复杂度：n^1.3
• 空间复杂度：1

希尔排序最后一次排序为直接插入排序

7. 冒泡排序

• 思想：两两比较元素，将如果次序相反，则交换。这样每一轮排序都会选出最大的或者最小的元素，直到所有的元素都有序
• 稳定性：稳定
• 确定性：确定，每一次都会选择出最大的元素，且该元素的位置不会再次发生变化
• 时间复杂度 n^2
• 空间复杂度 1

8. 快速排序

• 思想：在序列中任意选择一个元素，然后以这个元素为基准，将小于它的元素都放在它的左边，大于它的都放在右边。然后生成两个子序列。然后这两个子序列再一次执行上述操作。直到序列中只有一个元素
• 稳定性：不稳定
• 确定性：每次所选择的这个元素的位置是固定的
• 时间复杂度：nlog
• 空间复杂度：log （递归）

9. 简单选择排序

• 思想：每次从带排序的序列中找到最小的元素，然后放在有序序列末尾。这里注意和直接插入排序区分。直接插入的思想是每一次都从未排序的序列中选择一个元素，然后放到已经排序序列里面的合适的位置
• 稳定性：不稳定
• 确定性：确定
• 时间复杂度 n^2
• 空间复杂度：1