【C语言选择排序算法详解】+ 算法性能优化 + 动态演示实现
文章目录
一、算法介绍
选择排序(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_index
if (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);
// 测试优化版本1
start = clock();
selection_sort_optimized(arr2, SIZE);
end = clock();
printf("优化版本1耗时: %.3f 秒\n", (double)(end - start) / CLOCKS_PER_SEC);
// 测试优化版本2
start = 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.
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
21
0- 0
已为社区贡献3条内容
所有评论(0)