文章目錄
- 一、算法介紹
- 二、算法特點
- 三、代碼實現與解析
- 四、代碼解析
- 1. 打印數組函數
- 2. 選擇排序核心邏輯
- 3. 動態展示實現
- 4. 主函數
- 五、算法優化思路與實現
- 優化1：減少交換次數
- 優化原理：
- 優化2：雙向選擇排序
- 優化原理：
- 優化3：提前終止檢查
- 優化原理：
- 總結：
一、算法介紹
選擇排序(Selection Sort)是一種簡單直觀的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
二、算法特點
時間復雜度：O(n2)
空間復雜度：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(n2)，但仍可以做一些優化來提高實際性能：
優化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(n2)，不適合大規模數據排序
通過優化可以減少交換次數和排序輪數，提高實際性能
對于大規模數據排序，建議使用更高效的算法如快速排序、歸并排序等。
Created by LiuJinTao on 2025/9/13.
)
歸并排序)
