• 本文已收錄于專欄《資料結構入門》

零、📃前言

??這個系列的文章中，我會著重講解一些常見的 「演算法和資料結構」 的設計思想，并且配上動圖，希望讀者能夠帶上自己的 「思考」，主要針對面試中常見的問題和新手朋友們比較難理解的點進行決議，當然，這個系列的文章，后面也會給出面向演算法競賽的提綱，如果有興趣深入學習的歡迎在「評論區留言，一起成長交流」 ，
??零基礎學演算法的最好方法，莫過于刷題了，當然，刷題是不夠的，刷的程序中也要多多總結，多多思考，養成 「經常思考」 的習慣，這就是所謂的 「 流水不腐，戶樞不蠹 」，任何事情都是需要堅持的，刷題也一樣，沒有刷夠足夠的題，就很難做出系統性的總結，所以上大學的時候，我花了三年的時間來刷題， 作業以后還是會抽點時間出來刷題，
??千萬不要用作業忙來找借口，時間擠一擠總是有的，當然，每天不需要花太多時間在這個上面，把這個事情做成一個規劃，按照長期去推進，反正也沒有 KPI 壓力，就當成是作業之余的一種消遣，還能夠提升思維能力，
??所以，無論你是 小學生，中學生，高中OIer，大學ACMer，職場人士，只要想開始，一切都不會太晚！
??今天要講的主要內容是：「 選擇排序 」，希望讀者朋友給個面子，幫我完成閱讀，不能完讀，我可就完犢子了 🤣，當然，如果你覺得還可以，給我個「 贊 」 和 「 收藏 」，這個對我很重要，謝謝了！

??「 選擇排序 」 是比較直觀且編碼簡單的排序演算法，雖然效率不是很高，但一般也出現在各種 「資料結構」 的教科書上，于是，我來了，我會盡量做到「深入淺出」，讓 90% 的 「零基礎小白 」 也都能理解，真正做到 「讓天下沒有難學的演算法」 ，我知道這很難，但是我愿意嘗試！我會盡量把文章寫得有趣，

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌
究極演算法奧義！深度學習！ 🟣《深度學習100例》🟣

那么，我的教程和別人的教程有什么不同的地方呢？
??「第一步」簡單釋義： 我會簡單解釋一下這個演算法的目的、思想、以及為什么叫這個名字以幫助記憶，
??「第二步」核心思想： 我會大致介紹一下這個演算法的核心思想，
??「第三步」動圖演示： 我會引入一個動圖，并且用一個切實的例子展示一下演算法執行的全程序，
??「第四步」演算法前置： 在學習這個演算法之前，我們需要學習的前置內容有哪些？這些內容是需要事先去攻克的，
??「第五步」演算法描述： 細致的講解整個演算法的執行流程，
??「第六步」演算法分析： 對演算法的時間復雜度和空間復雜度進行一個詳細的分析，
??「第七步」優化方案： 介紹一些可以優化的點，
??「第八步」代碼實踐： 用 C/C++ 來實作上述演算法，
??「第九步」代碼驗證： 最后，我會推薦一些比較好用的在線評測系統來驗證我們實作的演算法的正確性，

一、🎯簡單釋義

1、演算法目的

??將原本亂序的陣列變成有序，可以是 「升序」 或者 「降序」 （為了描述統一，本文一律只討論 「 升序」 的情況），

2、演算法思想

??通過不斷從未排序的元素中，「比較」 和 「交換」，從而 「選擇」 出一個最小的， 直到最后變成一個「升序」 序列，則演算法結束，

3、命名由來

??每次都是「選擇」 出一個最小的元素，故此命名 「 選擇排序 」 ，

二、🧡核心思想

• 「迭代」：類似的事情，不停地做，
• 「比較」：關系運算子 小于( < \lt <) 的運用，
• 「交換」：變數或者物件的值的互換，

三、🔆動圖演示

1、樣例

• 初始情況下的資料如 圖二-1-1 所示，基本屬于亂序，純隨機出來的資料，

2、演算法演示

• 接下來，我們來看下排序程序的影片演示，如 圖二-2-1 所示：

3、樣例說明

??我們發現，首先從 「第一個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第一個元素」 進行 「交換」；
??然后，從 「第二個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第二個元素」 進行 「交換」，
??最后，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

• 這個演算法本身需要做一些「 回圈 」進行迭代計算，所以你至少需要知道「 回圈 」 的含義，這里以 「 c++ 」 為例，來看下一個簡單的「 回圈 」是怎么寫的，代碼如下：

int n = 5201314;
for(int i = 0; i < n; ++i) {
    // TODO ： ，，，
}

• 這個陳述句就是一個最簡單的回圈陳述句，它會將回圈體內的陳述句執行 n n n 次，而這里的 n n n 等于 5201314 5201314 5201314，也就是會執行 5201314 5201314 5201314 次，

2、比較的實作

• 「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「小于運算子（即 <）」 ，
• 我們可以將兩個數的「比較」寫成一個函式smallerThan，以 「 c++ 」 為例，實作如下：

#define Type int
bool smallerThan(Type a, Type b) {
    return a < b;
}

• 其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、交換的實作

• 所謂「交換」，就是對于兩個變數，將它們的值進行互換，
• 在 「Python」 中，我們可以直接寫出下面這樣的代碼就實作了變數的交換，

a, b = b, a

• 在 「 c++ 」 里，這個語法是錯誤的，
• 我們可以這么理解，你有兩個杯子 a a a 和 b b b，兩個杯子里都盛滿了水，現在想把兩個杯子里的水「交換」一下，那么第一個想到的方法是什么？

當然是再找來一個臨時杯子：
??1）先把 a a a 杯子的水倒進這個臨時的杯子里；
??2）再把 b b b 杯子的水倒進 a a a 杯子里；
??3）最后把臨時杯子里的水倒進 b b b 杯子；

• 這種就是臨時變數法，以 「 c++ 」 為例，實作如下：

#define Type int
void swap(Type* a, Type* b) {
    Type tmp = *a;     // 把 a 杯子的水倒進臨時杯子
    *a = *b;           // 把 b 杯子的水倒進 a 杯子
    *b = tmp;          // 把 臨時杯子 的水 倒進 b 杯子
}

• 這里*涉及到的「指標」相關知識，屬于語法層面，請自行學習，

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「 選擇排序 」將陣列按照 「升序」排列，

2、演算法程序

整個演算法的執行程序分以下幾步：
??1） 回圈迭代變數 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1；
??2） 每次迭代，令 m i n = i min = i min=i， j = i + 1 j = i+1 j=i+1；
??3） 回圈執行比較 a [ j ] a[j] a[j] 和 a [ m i n ] a[min] a[min]，如果產生 a [ j ] < a [ m i n ] a[j] \lt a[min] a[j]<a[min] 則執行 m i n = j min = j min=j，執行 j = j + 1 j = j + 1 j=j+1，繼續執行這一步，直到 j = = n j == n j==n；
??4） 交換 a [ i ] a[i] a[i] 和 a [ m i n ] a[min] a[min]，回到 1），

六、🧶演算法分析

1、時間復雜度

• 我們假設 「比較」 和 「交換」 的時間復雜度為 O ( 1 ) O(1) O(1)，
• 「 選擇排序 」 中有兩個嵌套回圈，

外回圈正好運行 n ? 1 n-1 n?1 次迭代， 但內部回圈運行變得越來越短：
??當 i = 0 i = 0 i=0，內層回圈 n ? 1 n-1 n?1 次「比較」操作，
??當 i = 1 i = 1 i=1，內層回圈 n ? 2 n-2 n?2 次「比較」操作，
??當 i = 2 i = 2 i=2，內層回圈 n ? 3 n-3 n?3 次「比較」操作，
??……
??當 i = n ? 3 i = n-3 i=n?3，內層回圈 2 2 2 次「比較」操作，
??當 i = n ? 2 i = n-2 i=n?2，內層回圈 1 1 1 次「比較」操作，

• 因此，總「比較」次數如下：
• ( n ? 1 ) + . . . + 2 + 1 = n ( n ? 1 ) 2 (n-1) + ... + 2 + 1 = \frac {n(n-1)}{2} (n?1)+...+2+1=2n(n?1)?
• 總的時間復雜度為： O ( n 2 ) O(n^2) O(n2)

2、空間復雜度

• 由于演算法在執行程序中，只有「選擇最小元素」的時候，需要事先將最小元素的下標存入臨時變數min，而其它沒有采用任何的額外空間，所以空間復雜度為 O ( 1 ) O(1) O(1)，

七、🧢優化方案

??「 選擇排序 」在眾多排序演算法中效率較低，時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，
?? 想象一下，當有 n = 1 0 5 n = 10^5 n=105 個數字， 即使我們的計算機速度超快，并且可以在 1 秒內計算 1 0 8 10^8 108 次操作，但冒泡排序仍需要大約一百秒才能完成，
??考慮一下，每一個內層回圈是從一個區間中找到一個最小值，并且更新這個最小值，是一個「 動態區間最值 」問題，所以這一步，我們是可以通過「 線段樹 」 來優化的，這樣就能將內層回圈的時間復雜度優化成 O ( l o g 2 n ) O(log_2n) O(log2?n) 了，總的時間復雜度就變成了 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，
??由于「 線段樹 」不是本文討論的重點，有興趣了解「 線段樹 」相關內容的讀者，可以參考以下這篇文章：夜深人靜寫演算法（三十九）- 線段樹，

八、💙原始碼詳解

#include <stdio.h>

int a[1010];

void input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void SelectionSort(int n, int *a) {  // (1)
    int i, j;
    for(i = 0; i < n - 1; ++i) {     // (2)
        int min = i;                 // (3)
        for(j = i+1; j < n; ++j) {   // (4)
            if(a[j] < a[min]) {
                min = j;             // (5)
            }
        }
        swap(&a[i], &a[min]);        // (6) 
    }
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        input(n, a);
        SelectionSort(n, a);
        output(n, a);
    }
    return 0;
} 

• ( 1 ) (1) (1) void SelectionSort(int n, int *a)為選擇排序的實作，代表對a[]陣列進行升序排序，
• ( 2 ) (2) (2) 從首元素個元素開始進行 n ? 1 n-1 n?1 次跌迭代，
• ( 3 ) (3) (3) 首先，記錄min代表當前第 i i i 輪迭代的最小元素的下標為 i i i，
• ( 4 ) (4) (4) 然后，迭代列舉第 i + 1 i+1 i+1 個元素到 最后的元素，
• ( 5 ) (5) (5) 選擇一個最小的元素，并且存盤下標到min中，
• ( 6 ) (6) (6) 將 第 i i i 個元素 和 最小的元素 進行交換，

九、💗代碼驗證

• 比如，你可以在百度上搜索 代碼在線提交、OnlineJudge、LeetCode、洛谷、HDOJ、POJ 等等的關鍵詞，然后去找對應的題目提交驗證你的代碼的正確性，

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌