選擇排序(Selection Sort)
選擇排序也是一種簡單直觀的排序算法。它的工作原理很容易理解：初始時在序列中找到最小（大）元素，放到序列的起始位置作為已排序序列；然後，再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
注意選擇排序與冒泡排序的區別：冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，從而將當前最小（大）元素放到合適的位置；而選擇排序每遍歷一次都記住了當前最小（大）元素的位置，最後僅需一次交換操作即可將其放到合適的位置。
選擇排序的代碼如下：
#include
// 分類 -------------- 內部比較排序
// 數據結構 ---------- 數組
// 最差時間複雜度 ---- O(n^2)
// 最優時間複雜度 ---- O(n^2)
// 平均時間複雜度 ---- O(n^2)
// 所需輔助空間 ------ O(1)
// 穩定性 ------------ 不穩定
void Swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
void SelectionSort(int A[], int n)
{
for (int i = 0; i < n - 1; i++) // i為已排序序列的末尾
{
int min = i;
for (int j = i + 1; j < n; j++) // 未排序序列
{
if (A[j] < A[min]) // 找出未排序序列中的最小值
{
min = j;
}
}
if (min != i)
{
Swap(A, min, i); // 放到已排序序列的末尾，該操作很有可能把穩定性打亂，所以選擇排序是不穩定的排序算法
}
}
}
int main()
{
int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 從小到大選擇排序
int n = sizeof(A) / sizeof(int);
SelectionSort(A, n);
printf("選擇排序結果：");
for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
return 0;
}
上述代碼對序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }進行選擇排序的實現過程如右圖：
使用選擇排序為一列數字進行排序的宏觀過程：
選擇排序是不穩定的排序算法，不穩定發生在最小元素與A[i]交換的時刻。
比如序列：{ 5, 8, 5, 2, 9 }，一次選擇的最小元素是2，然後把2和第一個5進行交換，從而改變了兩個元素5的相對次序。
寫在最後
初學者有什麼不懂的可以私信我，需要系統學習資料和系統學習框架圖的同學，可關注小編頭條號，歡迎留言評論和私信小編。【私信方法】文章上方處點擊“作者頭像”，進入作者首頁，在作者主頁上方點擊“關注”旁邊的“發私信”即可。私信內容：學習幫助。
喜歡小編的文章的朋友可以關注、收藏、轉發、留言，閱讀愉快！！
閱讀更多 岑寂扶你去學C 的文章
