任务四 数组的排序
任务四 数组的排序
- 先从生活例子开始理解
想象一下你要整理一副扑克牌，按照从小到大的顺序排列：
初始牌序：9, 105, 23, 19, 1 选择排序的思路就像这样：
找最小：在未排序部分中找到最小元素
记录位置：记录最小元素的索引，而不是直接交换
一次交换：每轮外层循环只进行一次交换
- 用简单语言解释算法步骤
// 假设我们有这些数字：9, 105, 23, 19, 1
// 第1轮：找到最小的数字1，和第一个数字9交换
// 结果：1, 105, 23, 19, 9
// 第2轮：从剩下的数字中找到最小的9，和第二个数字105交换
// 结果：1, 9, 23, 19, 105
// 第3轮：从剩下的数字中找到最小的19，和第三个数字23交换
// 结果：1, 9, 19, 23, 105
// 第4轮：剩下的已经有序，不需要交换
// 最终结果：1, 9, 19, 23, 105
- 基础代码演示（带详细注释）
using System;
class Program
{
static void Main()
{
// 我们要排序的数字数组
int[] numbers = { 9, 105, 23, 19, 1 };
Console.WriteLine("原始数组: " + string.Join(", ", numbers));
// 调用选择排序方法
SelectionSort(numbers);
Console.WriteLine("排序后数组: " + string.Join(", ", numbers));
}
static void SelectionSort(int[] arr)
{
// 数组长度
int n = arr.Length;
// 外层循环：控制排序的轮数
// 每轮确定一个最小元素的位置
for (int i = 0; i < n - 1; i++)
{
Console.WriteLine($"\n=== 第{i+1}轮开始 ===");
Console.WriteLine("当前数组: " + string.Join(", ", arr));
// 假设当前轮次的第一个元素是最小的
int minIndex = i;
Console.WriteLine($"假设位置{i}的数字{arr[i]}是最小的");
// 内层循环：在剩余元素中寻找真正的最小值
for (int j = i + 1; j < n; j++)
{
Console.WriteLine($" 比较: 当前最小值{arr[minIndex]} vs 位置{j}的数字{arr[j]}");
// 如果找到更小的数字，更新最小值的索引
if (arr[j] < arr[minIndex])
{
minIndex = j;
Console.WriteLine($" → 发现更小的数字! 新的最小值是位置{minIndex}的数字{arr[minIndex]}");
}
}
// 如果最小值不在当前位置，进行交换
if (minIndex != i)
{
Console.WriteLine($"交换位置{i}的数字{arr[i]}和位置{minIndex}的数字{arr[minIndex]}");
// 交换两个数字
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
Console.WriteLine($"交换后数组: " + string.Join(", ", arr));
}
else
{
Console.WriteLine("最小值已在正确位置，不需要交换");
}
}
}
}
- 可视化执行过程
让我用表格展示每一轮的变化：
轮次
操作
结果数组
初始
[9, 105, 23, 19, 1]
第1轮
找到最小值1，与9交换
[1, 105, 23, 19, 9]
第2轮
找到最小值9，与105交换
[1, 9, 23, 19, 105]
第3轮
找到最小值19，与23交换
[1, 9, 19, 23, 105]
第4轮
找到最小值23，已在正确位置
[1, 9, 19, 23, 105]
- 关键概念解释
什么是"索引"（Index）？
int[] numbers = {9, 105, 23, 19, 1};
// 索引: 0 1 2 3 4
索引就是每个数字的位置编号
C#中索引从0开始计数
为什么用 minIndex 而不是直接比较值？
// 正确做法：记录最小值的索引
int minIndex = i;
if (arr[j] < arr[minIndex])
{
minIndex = j; // 只更新索引，不修改数组
}
// 错误做法：直接修改数组值
if (arr[j] < arr[minIndex])
{
arr[minIndex] = arr[j]; // 这样会丢失数据！
}
- 练习：自己动手试试
任务1： 修改代码，实现从大到小排序
// 提示：只需要修改比较条件 // 把 < 改为 > 任务2： 对字符串数组按字母顺序排序
string[] words = {"banana", "apple", "cherry", "date"};
// 提示：字符串比较用 CompareTo 方法
- 常见问题解答
Q: 为什么外层循环是 i < n-1 而不是 i < n？ A: 因为当确定了n-1个元素的位置后，最后一个元素自然就在正确位置了。
Q: 选择排序快吗？ A: 对于小数据集可以，大数据集比较慢。时间复杂度是O(n²)。
Q: 什么时候用选择排序？ A: 当数据量小，或者需要简单易懂的排序方法时。
- 总结
选择排序的核心思想：
找：在未排序部分中找到最小元素
换：把最小元素放到已排序部分的末尾
重复：直到所有元素都排好序
记住这个口诀："找最小，放前面，重复做，就排好！"
冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，如果顺序错误就交换它们。
基本思想
从列表的第一个元素开始，比较相邻的两个元素
如果顺序错误（前一个比后一个大），就交换它们
对每一对相邻元素重复这个过程，直到列表末尾
重复上述步骤，每次遍历都会将最大的元素"冒泡"到正确位置
int[] arr = { 6, 3, 4, 1, 2 };
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = 0; j < arr.Length - i- 1; j++)
{
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
Console.WriteLine(string.Join(",",arr));
}
为什么是n-1?
有n个元素，需要确定n个位置
但每轮冒泡可以确定1个最大元素的位置
当确定了n-1个元素的位置后，最后1个元素自然就在正确位置
所以只需要 n-1 轮
原始数组: [5, 3, 8, 1, 2] (n=5)
第1轮: 将最大的8冒泡到最后 → [3, 5, 1, 2, 8]
第2轮: 将第二大的5冒泡到最后 → [3, 1, 2, 5, 8]
第3轮: 将第三大的3冒泡到最后 → [1, 2, 3, 5, 8]
第4轮: 将第四大的2冒泡到最后 → [1, 2, 3, 5, 8]
```
此时只剩下1个元素[1]，它已经在正确位置，不需要第5轮！
为什么是n-i-1
因为每一轮排序后，最大的元素会“冒泡”到当前未排序序列的末尾。因此，下一轮就不需要再比较已经排好序的部分。 第0轮（i=0）时，未排序部分包括所有n个元素，我们需要比较n-1次（因为比较是相邻两个元素，所以从0到n-2）。 第1轮（i=1）时，最后一个元素已经排好序，所以只需要比较前n-1个元素，即比较n-2次。 所以，内层循环的边界是j < n - i - 1。
比如：内层循环中我们比较的是 arr[j] 和 arr[j+1]：
当 j = n-2 时，比较的是 arr[n-2] 和 arr[n-1]
如果 j 达到 n-1，那么 j+1 = n 就会数组越界！
初始: [5, 3, 8, 1, 2]
↑ ↑ ↑ ↑ ↑
索引: 0 1 2 3 4
第1轮(i=0): j < 4 → 比较: 0-1, 1-2, 2-3, 3-4
第2轮(i=1): j < 3 → 比较: 0-1, 1-2, 2-3 (跳过索引4)
第3轮(i=2): j < 2 → 比较: 0-1, 1-2 (跳过索引3-4)
第4轮(i=3): j < 1 → 比较: 0-1 (跳过索引2-4)
冒泡排序 vs 选择排序
特性
冒泡排序
选择排序
交换次数
较多
较少
比较次数
相同
相同
稳定性
稳定
不稳定
适用场景
小规模或基本有序数据
小规模数据
冒泡排序虽然效率不高，但它的实现简单，是理解排序算法原理的好起点！
1. 用生活中的比喻开始
想象一下你在整理一排水杯，从左到右按从矮到高的顺序排列：
初始顺序：5, 3, 8, 1, 2
冒泡排序就像这样工作：
从左边开始，比较相邻的两个水杯
如果左边的比右边的高，就交换它们的位置
一轮比较下来，最高的水杯就会"冒泡"到最右边
重复这个过程，直到所有水杯都排好序
2. 简单直观的解释
```csharp
// 初始：5, 3, 8, 1, 2
// 第1轮冒泡：
// 比较5和3 → 交换 → 3,5,8,1,2
// 比较5和8 → 不交换 → 3,5,8,1,2
// 比较8和1 → 交换 → 3,5,1,8,2
// 比较8和2 → 交换 → 3,5,1,2,8 （8冒泡到最后）
// 第2轮冒泡：
// 比较3和5 → 不交换 → 3,5,1,2,8
// 比较5和1 → 交换 → 3,1,5,2,8
// 比较5和2 → 交换 → 3,1,2,5,8 （5冒泡到倒数第二）
// 继续这个过程...
- 基础代码演示（带详细注释）
using System;
class Program
{
static void Main()
{
// 我们要排序的数字数组
int[] numbers = { 5, 3, 8, 1, 2 };
Console.WriteLine("=== 冒泡排序演示 ===");
Console.WriteLine("原始数组: " + string.Join(", ", numbers));
// 调用冒泡排序方法
BubbleSort(numbers);
Console.WriteLine("\n最终结果: " + string.Join(", ", numbers));
}
static void BubbleSort(int[] arr)
{
int n = arr.Length;
// 外层循环：控制需要多少轮冒泡
// 每轮会让一个最大的数"冒泡"到正确位置
for (int i = 0; i < n - 1; i++)
{
Console.WriteLine($"\n🎯 第{i+1}轮冒泡开始:");
Console.WriteLine("当前数组: " + string.Join(", ", arr));
// 内层循环：进行相邻元素的比较和交换
for (int j = 0; j < n - i - 1; j++)
{
// 显示比较的两个数字
Console.Write($" 比较 [{arr[j]}] 和 [{arr[j+1]}]");
// 如果左边的数比右边大，就交换它们
if (arr[j] > arr[j + 1])
{
// 交换两个数字
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
Console.WriteLine(" → 🔄 交换!");
}
else
{
Console.WriteLine(" → ✅ 顺序正确，不交换");
}
}
// 显示本轮结束后的结果
Console.WriteLine($"第{i+1}轮结束: " + string.Join(", ", arr));
// 显示哪个数字"冒泡"到了右边
if (n - i - 1 > 0)
{
Console.WriteLine($"数字 {arr[n - i - 1]} 冒泡到了正确位置");
}
}
}
}
- 可视化执行过程
用箭头和颜色展示每一轮的变化：
初始: [5, 3, 8, 1, 2]
第1轮:
5↔3 → 交换 → [3, 5, 8, 1, 2]
5↔8 → 不换 → [3, 5, 8, 1, 2]
8↔1 → 交换 → [3, 5, 1, 8, 2]
8↔2 → 交换 → [3, 5, 1, 2, 8] ← 8冒泡到最后
第2轮:
3↔5 → 不换 → [3, 5, 1, 2, 8]
5↔1 → 交换 → [3, 1, 5, 2, 8]
5↔2 → 交换 → [3, 1, 2, 5, 8] ← 5冒泡到倒数第二
第3轮:
3↔1 → 交换 → [1, 3, 2, 5, 8]
3↔2 → 交换 → [1, 2, 3, 5, 8] ← 3冒泡到倒数第三
第4轮:
1↔2 → 不换 → [1, 2, 3, 5, 8] ← 排序完成!
- 关键概念解释
为什么叫"冒泡"排序？
因为大的数字会像气泡一样慢慢向上浮（向右移动）到正确的位置。
相邻比较的重要性
// 我们只比较相邻的两个元素
if (arr[j] > arr[j + 1]) // j和j+1是相邻的
{
// 交换它们
}
为什么内层循环条件是 j < n - i - 1？
n - i：排除已经排好序的元素（每轮结束后，右边的i个元素已经有序）
-1：防止数组越界（因为我们要比较j和j+1）
- 优化版本：提前结束
如果一轮中没有发生任何交换，说明数组已经有序，可以提前结束：
static void OptimizedBubbleSort(int[] arr)
{
int n = arr.Length;
bool swapped; // 标记是否发生了交换
for (int i = 0; i < n - 1; i++)
{
swapped = false; // 每轮开始时重置标记
Console.WriteLine($"\n第{i+1}轮开始:");
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
// 交换代码...
swapped = true; // 发生了交换
}
}
// 如果一轮中没有发生交换，说明已经有序
if (!swapped)
{
Console.WriteLine("🌟 没有发生交换，数组已经有序！");
break; // 提前结束排序
}
}
}
- 动手练习
练习1： 修改代码实现从大到小排序
// 提示：只需要修改比较符号
// 把 > 改为 <
练习2： 对字符串数组按字母顺序排序
string[] words = {"banana", "apple", "cherry", "date"};
// 提示：使用 string.Compare(str1, str2)
- 常见问题解答
Q: 冒泡排序和选择排序有什么区别？ A:
选择排序：每轮找到最小的放到前面
冒泡排序：每轮通过相邻比较让最大的冒泡到最后
Q: 冒泡排序快吗？ A: 对于小数据量可以，大数据量比较慢。但实现简单，容易理解。
Q: 为什么内层循环每次都要从头开始？ A: 因为我们需要确保每个大的数字都能一步步"冒泡"到正确位置。
- 记忆口诀
"相邻比较，大的右移， 一轮结束，最大沉底， 重复进行，直到有序。"
- 总结
冒泡排序的核心思想：
比较：比较相邻的两个元素
交换：如果顺序错误就交换
重复：多次遍历直到没有交换发生
插入排序
int[] arr = { 5, 2, 4, 6, 1, 3 };
// 从第二个元素开始（索引1），因为第一个元素默认已排序
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];// 当前要插入的"新牌"
int j = i - 1;// 从当前元素的前一个开始比较
// 将比key大的元素都向右移动一位
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j]; // 向右移动元素
j--;// 继续与前一个元素比较
}
arr[j + 1] = key; // 插入到正确位置
Console.WriteLine(string.Join(",",arr));
}
二分查找法
二分查找（Binary Search）是一种高效的查找算法，它比顺序查找快得多，但有一个重要前提：数据必须是有序的。
- 核心思想：猜数字游戏
想象一下猜数字游戏：我心中想一个1-100之间的数字，你每次猜一个数，我会告诉你"大了"、"小了"还是"对了"。
最聪明的策略：总是猜中间的数！
第一次猜50
如果我说"大了"，你就猜25（1-50的中间）
如果我说"小了"，你就猜75（50-100的中间）
这样每次都能排除一半的可能性！这就是二分查找的核心思想。
- 算法步骤详解
假设我们在有序数组 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 中查找 23：
确定范围：开始时，整个数组都是查找范围
左边界 left = 0（第一个元素）
右边界 right = 9（最后一个元素）
计算中间位置：mid = (0 + 9) / 2 = 4（取整）
中间值 arr[4] = 16
目标值 23 > 16，所以在右半部分继续查找
调整范围：左边界移动到 mid + 1 = 5
新范围：索引 5 到 9
新中间：mid = (5 + 9) / 2 = 7
中间值 arr[7] = 45
目标值 23 < 45，所以在左半部分继续查找
继续查找：右边界移动到 mid - 1 = 6
新范围：索引 5 到 6
新中间：mid = (5 + 6) / 2 = 5
中间值 arr[5] = 23 ← 找到了！
- C# 代码实现
迭代版本（推荐初学者使用）
static int FindNum(int[] array,int number)
{
int firstIndex = 0;
int lastIndex = array.Length - 1;
while (firstIndex <= lastIndex)
{
int middleIndex = firstIndex + (lastIndex - firstIndex) / 2;
if (number == array[middleIndex]) return middleIndex;
else if (number > array[middleIndex])
{
firstIndex = middleIndex + 1;
}
else
{
lastIndex = middleIndex - 1;
}
}
return -1;
}
static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Console.WriteLine(string.Join(",",arr));
Console.Write("请输入一个你要查找的数：");
int n = Convert.ToInt32(Console.ReadLine());
int result = FindNum(arr, n);
Console.WriteLine(result);
}
递归版本（了解即可）
// 二分查找方法 - 递归版本
static int BinarySearchRecursive(int[] array, int target, int left, int right)
{
if (left > right)
{
return -1; // 基础情况：没找到
}
int mid = left + (right - left) / 2;
if (array[mid] == target)
{
return mid; // 基础情况：找到了
}
else if (array[mid] < target)
{
// 递归调用：在右半部分查找
return BinarySearchRecursive(array, target, mid + 1, right);
}
else
{
// 递归调用：在左半部分查找
return BinarySearchRecursive(array, target, left, mid - 1);
}
}
// 使用递归版本
int result = BinarySearchRecursive(sortedNumbers, target, 0, sortedNumbers.Length - 1);
4. 完整示例：带详细日志
using System;
class BinarySearchDetailed
{
static void Main()
{
int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25 };
int[] targets = { 7, 20, 25, 0 };
foreach (int target in targets)
{
Console.WriteLine($"\n{'='.PadRight(40, '=')}");
Console.WriteLine($"查找目标值: {target}");
Console.WriteLine($"数组: [{string.Join(", ", numbers)}]");
int result = BinarySearchWithLogging(numbers, target);
if (result != -1)
{
Console.WriteLine($"✅ 成功！目标值 {target} 在索引 {result} 位置");
}
else
{
Console.WriteLine($"❌ 失败！目标值 {target} 不在数组中");
}
}
}
static int BinarySearchWithLogging(int[] array, int target)
{
int left = 0;
int right = array.Length - 1;
int steps = 0;
while (left <= right)
{
steps++;
int mid = left + (right - left) / 2;
Console.WriteLine($"步骤{steps}: 检查范围 [{left}-{right}]，中间索引 {mid}，值 {array[mid]}");
if (array[mid] == target)
{
Console.WriteLine($" 比较: {array[mid]} == {target} ✓");
Console.WriteLine($" 总共用了 {steps} 步查找");
return mid;
}
else if (array[mid] < target)
{
Console.WriteLine($" 比较: {array[mid]} < {target}，向右查找 →");
left = mid + 1;
}
else
{
Console.WriteLine($" 比较: {array[mid]} > {target}，向左查找 ←");
right = mid - 1;
}
}
Console.WriteLine($" 查找结束，总共用了 {steps} 步");
return -1;
}
}
- 算法特点分析
优点：
✅ 极快：时间复杂度 O(log n)，比顺序查找的 O(n) 快得多
✅ 高效：数据量越大，优势越明显
✅ 简单：逻辑清晰，容易理解
缺点：
❌ 必须有序：要求数据预先排序
❌ 内存连续：通常需要数组这样的连续存储结构
❌ 不适合动态数据：如果数据频繁变动，维护排序的成本高
- 时间复杂度对比
数据量
顺序查找（最坏）
二分查找（最坏）
10个元素
10次比较
4次比较
100个元素
100次比较
7次比较
1000个元素
1000次比较
10次比较
100万个元素
100万次比较
20次比较
惊人的效率差异：在100万个元素中查找，顺序查找最多需要100万次比较，而二分查找最多只需要20次！
- 重要细节说明
为什么使用 left + (right - left) / 2？
这是为了防止整数溢出。如果使用 (left + right) / 2，当 left 和 right 都很大时，left + right 可能超过 int 的最大值。
// 安全的方式（推荐）
int mid = left + (right - left) / 2;
// 有风险的方式（不推荐）
int mid = (left + right) / 2; // 可能溢出！
边界条件处理
// 检查数组是否为空
if (array == null || array.Length == 0)
{
return -1;
}
// 检查目标值是否在数组范围内（可选优化）
if (target < array[0] || target > array[array.Length - 1])
{
return -1; // 肯定不在数组中
}
- 实际应用练习
练习1：查找第一个大于等于目标的值
// 查找第一个大于或等于目标值的元素位置
static int FindFirstGreaterOrEqual(int[] array, int target)
{
int left = 0;
int right = array.Length - 1;
int result = -1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (array[mid] >= target)
{
result = mid; // 记录候选位置
right = mid - 1; // 继续向左找更小的满足条件的位置
}
else
{
left = mid + 1;
}
}
return result; // 返回第一个满足条件的位置，或-1
}
练习2：使用 C# 内置方法
// C# 提供了内置的二分查找方法
int[] numbers = { 1, 3, 5, 7, 9, 11, 13 };
int index = Array.BinarySearch(numbers, 7);
if (index >= 0)
{
Console.WriteLine($"找到在位置 {index}");
}
else
{
Console.WriteLine("未找到");
}
- 常见错误与调试技巧
常见错误：
忘记排序：对无序数组使用二分查找
边界错误：left <= right 写成 left < right
更新错误：left = mid 而不是 left = mid + 1
调试技巧：
// 添加调试输出
Console.WriteLine($"left={left}, right={right}, mid={mid}, array[mid]={array[mid]}");
// 或者使用调试器设置断点，观察变量变化
总结
二分查找是必须掌握的重要算法：
前提：数据必须有序
核心：每次排除一半的搜索范围
优势：极其高效，特别适合大型数据集
关键：正确处理边界条件和中间值计算
记住：当有人问"这个数据需要排序吗？"，如果要用二分查找，答案就是"必须排序！"
试着运行上面的代码，修改参数来体验二分查找的强大威力吧！
顺序查找法
顺序查找（Sequential Search）是最简单、最直观的查找算法，非常适合初学者学习。让我们一步步来理解它。
- 什么是顺序查找？
顺序查找就像在一本没有目录的书中找特定页码，或者在一堆杂乱的文件中找某个文件——你只能从第一个开始，一个一个地检查，直到找到为止。
核心思想：从数据集合的第一个元素开始，按顺序比较每个元素，直到找到目标或检查完所有元素。
- 算法步骤
顺序查找的过程非常简单：
从头开始：从第一个元素开始
逐个比较：将当前元素与目标值比较
找到则返回：如果相等，返回当前位置
继续下一个：如果不相等，移动到下一个元素
检查结束：如果所有元素都检查完还没找到，返回"未找到"
- 基础代码实现
版本1：返回索引（找到返回位置，找不到返回-1）
using System;
class SequentialSearch
{
// 顺序查找方法 - 返回元素索引
static int SequentialSearchIndex(int[] array, int target)
{
// 遍历数组中的每个元素
for (int i = 0; i < array.Length; i++)
{
// 如果找到目标值，返回它的索引位置
if (array[i] == target)
{
return i;
}
}
// 如果遍历完都没找到，返回-1
return -1;
}
static void Main()
{
int[] numbers = { 23, 45, 12, 67, 89, 34, 56 };
int target = 67;
int result = SequentialSearchIndex(numbers, target);
if (result != -1)
{
Console.WriteLine($"找到了！数字 {target} 在数组的第 {result} 个位置（索引从0开始）");
}
else
{
Console.WriteLine($"抱歉，数字 {target} 不在数组中");
}
}
}
版本2：返回布尔值（简单判断是否存在）
// 顺序查找方法 - 返回是否存在
static bool SequentialSearchExists(int[] array, int target)
{
foreach (int num in array)
{
if (num == target)
{
return true; // 找到了
}
}
return false; // 没找到
}
- 带详细输出的完整示例
让我们通过一个更详细的例子来理解查找过程：
using System;
class SequentialSearchDemo
{
static void Main()
{
int[] scores = { 85, 92, 78, 96, 88, 90, 76 };
int targetScore = 88;
Console.WriteLine("=== 顺序查找演示 ===");
Console.WriteLine($"数组: [{string.Join(", ", scores)}]");
Console.WriteLine($"要查找的成绩: {targetScore}");
Console.WriteLine("开始查找...\n");
bool found = false;
int position = -1;
int comparisons = 0; // 记录比较次数
// 执行顺序查找
for (int i = 0; i < scores.Length; i++)
{
comparisons++;
Console.WriteLine($"第{comparisons}次比较: 检查位置{i}的值{scores[i]}");
if (scores[i] == targetScore)
{
found = true;
position = i;
Console.WriteLine($"✓ 找到了！在位置 {i}");
break; // 找到后就退出循环
}
else
{
Console.WriteLine(" ✗ 不匹配，继续下一个...");
}
}
Console.WriteLine($"\n查找结果:");
Console.WriteLine($"- 是否找到: {found}");
Console.WriteLine($"- 位置: {position}");
Console.WriteLine($"- 总共比较次数: {comparisons}");
}
}
运行结果示例：
=== 顺序查找演示 ===
数组: [85, 92, 78, 96, 88, 90, 76]
要查找的成绩: 88
开始查找...
第1次比较: 检查位置0的值85
✗ 不匹配，继续下一个...
第2次比较: 检查位置1的值92
✗ 不匹配，继续下一个...
第3次比较: 检查位置2的值78
✗ 不匹配，继续下一个...
第4次比较: 检查位置3的值96
✗ 不匹配，继续下一个...
第5次比较: 检查位置4的值88
✓ 找到了！在位置 4
```
查找结果:
- 是否找到: True
- 位置: 4
- 总共比较次数: 5
5. 字符串数组的查找
顺序查找不仅适用于数字，也适用于字符串和其他数据类型：
```csharp
using System;
class StringSearch
{
static void Main()
{
string[] names = { "张三", "李四", "王五", "赵六", "钱七" };
string targetName = "王五";
Console.WriteLine("在姓名列表中查找...");
Console.WriteLine($"列表: [{string.Join(", ", names)}]");
int position = -1;
for (int i = 0; i < names.Length; i++)
{
if (names[i] == targetName)
{
position = i;
break;
}
}
if (position != -1)
{
Console.WriteLine($"找到了！'{targetName}' 在列表的第 {position + 1} 个位置");
}
else
{
Console.WriteLine($"抱歉，'{targetName}' 不在列表中");
}
}
}
- 算法的特点分析
优点：
✅ 简单易懂：逻辑非常直观，容易实现
✅ 无需排序：对数据的排列顺序没有要求
✅ 适用性广：适用于数组、列表等各种数据结构
缺点：
❌ 效率较低：最坏情况下需要检查所有元素
❌ 不适合大数据：数据量很大时速度很慢
- 时间复杂度
最好情况：目标在第一个位置 → O(1)
最坏情况：目标在最后一个位置或不存在 → O(n)
平均情况：目标在中间某个位置 → O(n)
其中 n 是数据集合的大小。
- 实际应用练习
练习1：查找所有匹配项
// 查找数组中所有等于目标值的位置
static List<int> FindAllPositions(int[] array, int target)
{
List<int> positions = new List<int>();
for (int i = 0; i < array.Length; i++)
{
if (array[i] == target)
{
positions.Add(i);
}
}
return positions;
}
练习2：查找最大值/最小值
// 使用顺序查找的思路找最大值
static int FindMax(int[] array)
{
int max = array[0]; // 假设第一个是最大值
for (int i = 1; i < array.Length; i++)
{
if (array[i] > max)
{
max = array[i]; // 找到更大的值，更新最大值
}
}
return max;
}
- 实用小技巧
使用 foreach 简化代码：
// 如果只需要知道是否存在，不关心位置
static bool ExistsSimple(int[] array, int target)
{
foreach (int item in array)
{
if (item == target) return true;
}
return false;
}
使用 Array.IndexOf 方法：
// C# 内置了顺序查找的方法
int[] numbers = { 1, 3, 5, 7, 9 };
int index = Array.IndexOf(numbers, 5); // 返回2
int notFound = Array.IndexOf(numbers, 10); // 返回-1
总结
顺序查找是最基础的查找算法，虽然效率不高，但：
是学习更复杂算法的基础
在小数据量时完全够用
代码简单，容易理解和调试
记住：对于大型数据集合，可以考虑使用更高效的算法如二分查找（但要求数据必须先排序）。
希望这个讲解对你有帮助！试着运行这些代码，并修改参数来加深理解。