文章目录
- 一、算法介绍
- 二、算法特点
- 三、代码实现与解析
- 四、代码解析
- 1. 打印数组函数
- 2. 选择排序核心逻辑
- 3. 动态展示实现
- 4. 主函数
- 五、算法优化思路与实现
- 优化1：减少交换次数
- 优化原理：
- 优化2：双向选择排序
- 优化原理：
- 优化3：提前终止检查
- 优化原理：
- 总结：
一、算法介绍
选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
二、算法特点
时间复杂度：O(n²)
空间复杂度：O(1)
不稳定排序算法
原地排序算法
三、代码实现与解析
#include <stdio.h>
#include <windows.h> // 用于Sleep函数（Windows环境）// 打印数组
void loop_print_array(int arr[], int len) {for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}printf("\n");
}// 选择排序（添加动态展示逻辑）
void selection_sort(int arr[], int len) {for (int i = 0; i < len - 1; i++) {for (int j = i + 1; j < len; j++) {if (arr[i] > arr[j]) {// 交换元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;// 🔴 关键：交换后打印当前数组 + 暂停system("cls"); // Windows下清屏，让显示更连贯（Linux/macOS用system("clear")）printf("第 %d 轮比较，交换 arr[%d] 和 arr[%d] 后：\n", i+1, i, j);loop_print_array(arr, len);Sleep(1000); // 暂停800毫秒（可调整速度，单位：毫秒）}}}
}
int main() {// 设置控制台输出编码为UTF-8，避免中文乱码SetConsoleOutputCP(CP_UTF8);SetConsoleCP(CP_UTF8);int arr[10] = {5, 8, 1, 4, 2, 9, 10, 3, 7, 6};int len = sizeof(arr) / sizeof(int);printf("排序前：\n");loop_print_array(arr, len);Sleep(1000); // 先暂停1秒，看清初始数组selection_sort(arr, len);printf("\n排序完成：\n");loop_print_array(arr, len);return 0;
}
四、代码解析
1. 打印数组函数
c
void loop_print_array(int arr[], int len) {
for (int i = 0; i < len; i++) {
printf(“%d “, arr[i]);
}
printf(”\n”);
}
这个函数负责遍历数组并打印所有元素，方便我们观察排序过程中数组的变化。
2. 选择排序核心逻辑
void selection_sort(int arr[], int len) {for (int i = 0; i < len - 1; i++) {for (int j = i + 1; j < len; j++) {if (arr[i] > arr[j]) {// 交换元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;// 动态展示部分system("cls");printf("第 %d 轮比较，交换 arr[%d] 和 arr[%d] 后：\n", i+1, i, j);loop_print_array(arr, len);Sleep(1000);}}}
}
选择排序的核心是双重循环：
-
外层循环控制排序的轮数，每轮确定一个最小元素的位置
-
内层循环用于查找未排序部分的最小元素
-
当找到比当前基准更小的元素时，进行交换
3. 动态展示实现
代码中添加了动态展示逻辑：
使用 system(“cls”) 清屏，使每次输出更加清晰
打印当前操作信息（第几轮比较，交换了哪些元素）
使用 Sleep(1000) 暂停1秒，方便观察每一步的变化
4. 主函数
int main() {SetConsoleOutputCP(CP_UTF8);SetConsoleCP(CP_UTF8);int arr[10] = {5, 8, 1, 4, 2, 9, 10, 3, 7, 6};int len = sizeof(arr) / sizeof(int);// 初始数组展示printf("排序前：\n");loop_print_array(arr, len);Sleep(1000);// 执行排序selection_sort(arr, len);// 最终结果展示printf("\n排序完成：\n");loop_print_array(arr, len);return 0;
}
主函数中：
设置控制台编码为UTF-8，避免中文乱码
初始化待排序数组
展示排序前的数组
调用选择排序函数
展示排序后的最终结果
五、算法优化思路与实现
虽然选择排序的时间复杂度固定为O(n²)，但仍可以做一些优化来提高实际性能：
优化1：减少交换次数
原始实现中每次找到更小的元素就立即交换，实际上我们可以记录最小值的索引，在一轮比较完成后只交换一次：
// 优化版本1：减少交换次数
void selection_sort_optimized(int arr[], int len) {for (int i = 0; i < len - 1; i++) {int min_index = i; // 记录最小元素的索引for (int j = i + 1; j < len; j++) {if (arr[j] < arr[min_index]) {min_index = j; // 更新最小元素的索引}}// 只有在找到更小元素时才交换if (min_index != i) {int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;// 动态展示system("cls");printf("第 %d 轮，找到最小值 arr[%d]=%d，与 arr[%d]=%d 交换后：\n", i+1, min_index, arr[i], i, arr[min_index]);loop_print_array(arr, len);Sleep(1000);}}
}
优化原理：
减少不必要的交换操作，每轮最多只交换一次
对于大型对象或复杂数据结构，交换操作可能成本较高，此优化能显著提高性能
优化2：双向选择排序
同时寻找最大值和最小值，减少排序轮数：
// 优化版本2：双向选择排序
void selection_sort_bidirectional(int arr[], int len) {int left = 0, right = len - 1;while (left < right) {int min_index = left, max_index = right;// 确保min_index <= max_indexif (arr[min_index] > arr[max_index]) {int temp = arr[min_index];arr[min_index] = arr[max_index];arr[max_index] = temp;}// 在剩余部分中查找最小和最大值for (int i = left + 1; i < right; i++) {if (arr[i] < arr[min_index]) {min_index = i;} else if (arr[i] > arr[max_index]) {max_index = i;}}// 将最小值放到左边if (min_index != left) {int temp = arr[left];arr[left] = arr[min_index];arr[min_index] = temp;// 如果最大值原本在left位置，现在被移到了min_index位置if (max_index == left) {max_index = min_index;}}// 将最大值放到右边if (max_index != right) {int temp = arr[right];arr[right] = arr[max_index];arr[max_index] = temp;}// 动态展示system("cls");printf("范围 [%d,%d]，最小值放左边，最大值放右边后：\n", left, right);loop_print_array(arr, len);Sleep(1000);left++;right--;}
}
优化原理：
每轮同时找到最小和最大元素，分别放到序列的两端
减少大约一半的排序轮数
对于随机数据，性能提升约50%
优化3：提前终止检查
添加提前终止检查，当数组已经有序时提前结束排序：
// 优化版本3：添加提前终止检查
void selection_sort_early_termination(int arr[], int len) {for (int i = 0; i < len - 1; i++) {int min_index = i;bool swapped = false; // 标记本轮是否发生交换for (int j = i + 1; j < len; j++) {if (arr[j] < arr[min_index]) {min_index = j;swapped = true;}}if (min_index != i) {int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;// 动态展示system("cls");printf("第 %d 轮，交换 arr[%d] 和 arr[%d] 后：\n", i+1, i, min_index);loop_print_array(arr, len);Sleep(1000);} else if (!swapped) {// 如果没有找到更小的元素且未发生交换，说明数组已有序printf("第 %d 轮检测到数组已有序，提前终止排序\n", i+1);break;}}
}
优化原理：
当某一轮未发生任何交换时，说明数组已经有序，可以提前终止排序
对于近乎有序的数组，能显著提高性能
性能对比
为了直观展示优化效果，我们可以添加简单的性能测试代码：
#include <time.h>// 性能测试函数
void performance_test() {const int SIZE = 10000;int arr1[SIZE], arr2[SIZE], arr3[SIZE];// 初始化随机数组for (int i = 0; i < SIZE; i++) {int val = rand() % 1000;arr1[i] = val;arr2[i] = val;arr3[i] = val;}clock_t start, end;// 测试原始版本start = clock();selection_sort(arr1, SIZE);end = clock();printf("原始版本耗时: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);// 测试优化版本1start = clock();selection_sort_optimized(arr2, SIZE);end = clock();printf("优化版本1耗时: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);// 测试优化版本2start = clock();selection_sort_bidirectional(arr3, SIZE);end = clock();printf("优化版本2耗时: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
}运行效果
运行程序后，控制台会逐步展示排序过程：
首先显示初始数组：5 8 1 4 2 9 10 3 7 6
每一轮比较后，清屏并显示当前数组状态和操作信息
最后显示排序完成的有序数组：1 2 3 4 5 6 7 8 9 10
适用场景与总结
选择排序是一种简单但低效的排序算法，主要适用于：
-
小规模数据排序
-
对内存使用有严格限制的场景
-
作为算法学习的入门示例
总结：
选择排序的时间复杂度为O(n²)，不适合大规模数据排序
通过优化可以减少交换次数和排序轮数，提高实际性能
对于大规模数据排序，建议使用更高效的算法如快速排序、归并排序等。
Created by LiuJinTao on 2025/9/13.
)
归并排序)
