一、引言
在 CSP-J 备考中，算法基础是至关重要的一环。排序算法作为其中常见且基础的考点，需要我们深入理解和掌握。本文将重点对比冒泡排序、选择排序、插入排序这三种基础排序算法。
二、冒泡排序
基本思想：通过相邻元素两两比较，将较大的元素逐步“浮”到数组的末尾。每一轮比较都会将当前未排序部分的最大元素放到正确的位置。
时间复杂度：最坏情况和平均情况均为 O(n²)。
优化方向：
1. 当某一轮比较中没有发生任何交换，说明数组已经有序，可以提前结束排序。
代码实现：
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
三、选择排序
基本思想：每一轮在未排序部分中找到最小（或最大）的元素，放到已排序部分的末尾。
时间复杂度：始终为 O(n²)。
优化方向：相对较少，但可以通过减少交换次数来稍微提高效率。
代码实现：
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
四、插入排序
基本思想：将未排序部分的第一个元素插入到已排序部分的适当位置。
时间复杂度：最坏情况和平均情况均为 O(n²)，但对于部分有序的数组，性能较好。
优化方向：
1. 提前终止内层循环，当插入元素大于等于已排序部分的最后一个元素时，直接跳过。
代码实现：
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
五、总结
冒泡排序、选择排序和插入排序虽然时间复杂度相同，但在实际应用中，它们的性能特点有所不同。在备考 CSP-J 时，不仅要理解它们的基本思想和实现方式，还要通过大量的练习来熟悉它们的应用场景和优化方法，为后续更复杂的算法学习打下坚实的基础。
希望以上内容对您的 CSP-J 备考有所帮助，祝您取得优异成绩！
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
