### 2020傲梦第二届等级测评复习资料（C++五级）
#### 知识点解析
##### 冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
**示例分析**：
初始数组：`10, 4, 6, 2, 17, -5`
**第一趟排序**：
- `10 > 4` 交换 -> `4, 10, 6, 2, 17, -5`
- `10 > 2` 交换 -> `4, 2, 10, 6, 17, -5`
- `10 > 6` 交换 -> `4, 2, 6, 10, 17, -5`
- `10 < 17` 不交换 -> `4, 2, 6, 10, 17, -5`
- `17 > -5` 交换 -> `4, 2, 6, 10, -5, 17`
**第二趟排序**：
- `4 > 2` 交换 -> `2, 4, 6, 10, -5, 17`
- `4 < 6` 不交换 -> `2, 4, 6, 10, -5, 17`
- `6 < 10` 不交换 -> `2, 4, 6, 10, -5, 17`
- `10 > -5` 交换 -> `2, 4, 6, -5, 10, 17`
**第三趟排序**：
- `2 < 4` 不交换 -> `2, 4, 6, -5, 10, 17`
- `4 < 6` 不交换 -> `2, 4, 6, -5, 10, 17`
- `6 > -5` 交换 -> `2, 4, -5, 6, 10, 17`
**第四趟排序**：
- `2 < 4` 不交换 -> `2, 4, -5, 6, 10, 17`
- `4 > -5` 交换 -> `2, -5, 4, 6, 10, 17`
**第五趟排序**：
- `2 > -5` 交换 -> `-5, 2, 4, 6, 10, 17`
**最终结果**：`-5, 2, 4, 6, 10, 17`
对于`n`个数进行冒泡排序，需要进行`n-1`趟，每趟都会将当前未排序部分的最大值“冒”到最后的位置。
---
##### 选择排序
选择排序是一种简单直观的排序算法。它的基本思想是：在未排序序列中找到最小（或最大）元素放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
**示例分析**：
初始数组：`1.2, 1.4, 1.45, 1.73, 1.6, 1.65`
**第一趟排序**：选择最小值`1.2`放到第一位 -> `1.2, 1.4, 1.45, 1.73, 1.6, 1.65`
**第二趟排序**：选择第二小值`1.4`放到第二位 -> `1.2, 1.4, 1.45, 1.73, 1.6, 1.65`
**第三趟排序**：选择第三小值`1.45`放到第三位 -> `1.2, 1.4, 1.45, 1.73, 1.6, 1.65`
**第四趟排序**：选择第四小值`1.6`放到第四位 -> `1.2, 1.4, 1.45, 1.6, 1.73, 1.65`
**第五趟排序**：选择第五小值`1.65`放到第五位 -> `1.2, 1.4, 1.45, 1.6, 1.65, 1.73`
**最终结果**：`1.2, 1.4, 1.45, 1.6, 1.65, 1.73`
---
##### 桶排序（简单计数排序）
桶排序是一种分布式的排序算法，适用于元素在一定范围内均匀分布的情况。其基本思想是将待排序的元素分配到若干个“桶”中，然后再对每个“桶”中的元素分别排序。
**示例分析**：
初始数组：`1.2, 1.4, 1.45, 1.73, 1.6, 1.65`
假设桶的个数为`n`，则每个桶的区间为`(max-min)/n`。这里我们假设桶的个数为数组长度，即`6`。
**分配到桶**：
- `[1.2]`
- `[1.4]`
- `[1.45]`
- `[1.6]`
- `[1.65]`
- `[1.73]`
**合并**：`1.2, 1.4, 1.45, 1.6, 1.65, 1.73`
**最终结果**：`1.2, 1.4, 1.45, 1.6, 1.65, 1.73`
---
##### 排序算法比较
| 排序算法 | 平均时间复杂度 | 最坏情况时间复杂度 | 空间复杂度 |
|---------|--------------|------------------|----------|
| 冒泡排序 | O(n^2) | O(n^2) | O(1) |
| 选择排序 | O(n^2) | O(n^2) | O(1) |
| 桶排序 | O(n+k) | O(n+k) | O(n+k) |
其中，`n`为元素数量，`k`为桶的数量。
---
##### 二分查找
二分查找是一种在有序数组中查找特定元素的高效算法。其工作原理是通过将查找区间分成大致相等的两半，然后确定目标值在哪一半，从而减少搜索范围。这一过程重复进行，直至找到目标值或者搜索区间为空为止。
**示例分析**：
假设要在一个已排序的数组中查找某个元素`x`。
**步骤**：
1. 计算中间位置`mid`。
2. 如果`arr[mid] == x`，返回`mid`。
3. 如果`arr[mid] < x`，则在右半部数组中查找。
4. 如果`arr[mid] > x`，则在左半部数组中查找。
5. 重复上述过程，直到找到元素或搜索区间为空。
**时间复杂度**：O(log n)
---
以上内容总结了C++五级复习资料中的主要知识点，包括冒泡排序、选择排序、桶排序以及二分查找的基本概念与实现方法，并通过具体的示例进行了详细的解释。希望这些知识点能帮助大家更好地理解并掌握相关算法的原理与应用。
