1 簡單選擇排序
簡單選擇排序（Simple Selection Sort）是一種基礎且直觀的排序算法，其核心思想是通過重復選擇未排序部分中的最小（或最大）元素，并將其放到已排序部分的末尾，逐步完成整個序列的排序。
1.1 基本概念與原理
簡單選擇排序(Simple Selection Sort)是一種基于比較的原地排序算法，其核心思想是將待排序序列分為已排序和未排序兩部分，通過不斷選擇未排序部分中的最小元素，并將其交換到已排序部分的末尾，逐步完成整個序列的排序。
該算法的主要特點包括：
?不穩定排序?：相同元素的相對位置可能在排序過程中改變
?原地排序?：不需要額外的存儲空間
?直觀簡單?：算法邏輯易于理解和實現
選擇排序的基本原理可以類比為"每次從剩余未排序元素中挑選最小的一個放到正確位置"。這種逐步選擇最小元素的策略使得算法具有確定性，無論輸入數據的初始順序如何，其比較次數都是固定的。
1.2 算法執行過程
選擇排序的具體執行步驟如下：
?1.初始化階段?：
（1）將整個數組視為未排序部分
（2）已排序部分初始為空
2?.查找最小值階段?：
（1）從當前未排序部分的第一個元素開始遍歷
（2）記錄當前最小元素的索引
?3.比較交換階段?：
（1）將當前元素與已記錄的最小元素比較
（2）如果發現更小的元素，更新最小元素索引
4?.位置交換階段?：
（1）遍歷完成后，將未排序部分的第一個元素與找到的最小元素交換
（2）此時已排序部分增加一個元素
?5.迭代重復?：
（1）縮小未排序部分的范圍
（2）重復步驟2-4，直到未排序部分只剩一個元素
執行示例
以數組[64, 25, 12, 22, 11]為例：
第一輪：找到最小值11，與64交換 → [11, 25, 12, 22, 64]
第二輪：在剩余部分找到最小值12，與25交換 → [11, 12, 25, 22, 64]
第三輪：找到最小值22，與25交換 → [11, 12, 22, 25, 64]
第四輪：找到最小值25，位置正確 → 排序完成
1.3 算法復雜度分析
時間復雜度
?最壞情況?：O(n2) - 需要進行n(n-1)/2次比較
?最好情況?：O(n2) - 即使輸入已經有序，仍需相同數量的比較
?平均情況?：O(n2) - 比較次數與輸入順序無關
空間復雜度
?空間復雜度?：O(1) - 僅需常數級別的額外空間用于交換元素
1.4 C語言實現簡單選擇排序
#include <stdio.h>#define SORT_DATA_TYPE int/*** @brief 打印數據** @param arr 數組* @param n 數組元素個數*/
void print_array(int arr[], unsigned int n)
{unsigned int i;for (i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}/*** @brief 簡單選擇排序** @param arr 待排序的數組* @param n 數組元素個數*/
void simple_selection_sort(SORT_DATA_TYPE arr[], unsigned int n)
{int swap_flg;SORT_DATA_TYPE temp;unsigned int i;unsigned int j;for (i = 0; i < (n - 1); i++){for (j = (i + 1); j < n; j++){if (arr[j] < arr[i]){temp = arr[i];arr[i] = arr[j];arr[j] = temp;}print_array(arr, n); /* 查看每次排序結構，調試使用 */}}
}int main()
{SORT_DATA_TYPE arr[] = {1, 2, 3, 4};unsigned int n = sizeof(arr) / sizeof(arr[0]);printf("old arr : ");print_array(arr, n);simple_selection_sort(arr, n);printf("new arr : ");print_array(arr, n);return 0;
}
注：
不同類型的數組直接將SORT_DATA_TYPE全部替換為需要的類型，然后刪除多余的宏定義即可支持任意類型數組的簡單選擇排序。
1.5 簡單測試
通過使用2個數組[4,3,2,1]及[1,2,3,4]演示最壞情況和最好情況簡單選擇排序的執行過程：
最壞情況：
最壞情況需要進行n(n-1)/2次比較，也就是6次比較。可以使用如下圖片演示這一過程：
最好情況：
最好情況需要進行n(n-1)/2次比較，也就是6次比較。
)
