Visual Studio中的冒泡排序和选择排序

目录

一、冒泡排序

1.介绍

2.使用模板

3.示例

4.注意事项

二、选择排序

1.介绍

2.使用模板

3.示例

4.注意事项

三、两者对比

四、总结

一、冒泡排序

1.介绍

冒泡排序是一种简单的排序算法，通过相邻元素的比较与交换将最大（或最小）的元素逐步“冒泡”到数组的末端。重复此过程直到整个数组有序。

2.使用模板

3.示例

对数组[3, 1, 4, 1, 5]进行冒泡排序：

1. 第1轮：比较相邻元素，交换3和1→[1, 3, 1, 4, 5]
2. 第2轮：交换3和1→[1, 1, 3, 4, 5]
3. 第3轮：无交换，提前退出。

4.注意事项

• 优化标志：添加swapped标志可避免不必要的循环，提升效率。
• 数组越界：内循环条件需为j < n - 1 - i，避免访问array[j+1]时越界。
• 稳定性：冒泡排序是稳定排序（相同元素相对位置不变）。

二、选择排序

1.介绍

选择排序通过每次从未排序部分选择最小（或最大）元素，将其放到已排序部分的末尾。重复此过程直到整个数组有序。

2.使用模板

3.示例

对数组[3, 1, 4, 1, 5]进行选择排序：

1. 第1轮：找到最小元素1（索引1），交换到位置0 →[1, 3, 4, 1, 5]
2. 第2轮：找到最小元素1（索引3），交换到位置1 →[1, 1, 4, 3, 5]
3. 第3轮：找到最小元素3（索引3），交换到位置2 →[1, 1, 3, 4, 5]

4.注意事项

• 交换次数少：选择排序交换次数固定为n-1次，优于冒泡排序。
• 不稳定性：选择排序是不稳定排序（相同元素可能交换位置，例如[2, 2, 1]排序后变为[1, 2, 2]，但原顺序可能改变）。
• 性能：时间复杂度始终为O(n²)，无优化空间。

三、两者对比

四、总结

• 冒泡排序：适合数据基本有序的场景，通过优化可减少不必要的比较。
• 选择排序：交换次数少，适合元素交换成本较高的情况（如大型对象排序）。
• 性能对比：在随机数据下，两者效率相近，但选择排序通常更快（交换次数少）。