摘要：選擇排序算法實(shí)現(xiàn)實(shí)現(xiàn)選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個(gè)數(shù)組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實(shí)現(xiàn)前面我們說到了，我們?yōu)榱送怀雠判蛩惴ǖ乃枷耄瑢⑺械睦觾H限在數(shù)組排序中。

“算法”的入門，從“排序算法”開始，希望通過“排序算法”這一部分的學(xué)習(xí)，能夠讓我們認(rèn)識到“算法”的威力，“算法”不僅僅只存在與我們的面試中（那時(shí)只是因?yàn)槲也恢馈八惴ā倍眩?，“算法”無處不在，“算法”很有用。

下面是一些說明：

1、會直接使用“空間復(fù)雜度”和“時(shí)間復(fù)雜度”的概念，不妨先有個(gè)印象，實(shí)在糾結(jié)的話，可以去翻翻書，“空間復(fù)雜度”和“時(shí)間復(fù)雜度”最多的應(yīng)用就在于比較不同算法的優(yōu)劣；

2、“排序算法”這一章節(jié)為了方便說明，使用的例子都是以“整數(shù)數(shù)組”為例，并且是“升序排序”，學(xué)習(xí)過 Java 語言的朋友就知道，待排序的也可以是對象，只要實(shí)現(xiàn)了相關(guān)的接口，實(shí)現(xiàn)了相應(yīng)的比較規(guī)則，就可以進(jìn)行排序。

我們選擇“選擇排序”作為算法入門的開篇。理由如下：

1、“選擇排序”算法的思想十分簡單，非常接近我們的思維方式：先找最小的數(shù)、再找第 2 小的數(shù)，依次類推，最后剩下的就是數(shù)組中最大的元素；

2、“選擇排序”的實(shí)現(xiàn)也很簡單。

思想：不斷地選擇剩余元素之中的最小者。

1、每一輪交換都能排定一個(gè)元素，交換的總次數(shù)是固定的；

說明：“交換的總次數(shù)”等于“元素的總數(shù) - 1”，因此算法的時(shí)間復(fù)雜度取決于比較的次數(shù)；

2、運(yùn)行時(shí)間和輸入無關(guān)，即：一個(gè)“已經(jīng)有序”的數(shù)組、一個(gè)所有的元素都相等的數(shù)組、一個(gè)元素隨機(jī)排列的數(shù)組所用的排序時(shí)間是一樣的；

說明：后續(xù)我們會編寫一些測試用例，比較不同的算法在不同的測試用例上的運(yùn)行時(shí)間。這些測試用例中，就有以下 $3$ 種。

（1）一個(gè)“已經(jīng)有序”的數(shù)組：例如：[4, 5, 6, 8, 9, 10]，以后我們學(xué)習(xí)的排序算法中，就有一種算法名叫“插入排序”就能檢測出數(shù)組是不是有序的，極端情況下，“插入排序”算法看一遍數(shù)組中的元素，就知道數(shù)組已經(jīng)有序了，后續(xù)就什么都不用做了。而“選擇排序”得一遍又一遍看數(shù)組的元素好幾遍，“幾乎是”有多少個(gè)數(shù)，就會看數(shù)組多少遍，每一遍選出當(dāng)前沒有排定元素中的最小者；

（2）一個(gè)所有的元素都相等的數(shù)組，例如：[6, 6, 6, 6, 6, 6]；

（3）一個(gè)元素隨機(jī)排列的數(shù)組，就是我們一般意義下，雜亂無序的數(shù)組，例如：[8, 18, 10, 6, 5, 4, 20]。

3、數(shù)據(jù)移動(dòng)是最少的。

這點(diǎn)應(yīng)該說是“選擇排序”的優(yōu)點(diǎn)了，如果我們的排序任務(wù)對交換操作非常敏感，不妨考慮“選擇排序”。

例如：我們待排序的是碼頭上的集裝箱，交換集裝箱的成本是很高的，此時(shí)“選擇排序”就是最好的選擇。

小貼士：這一部分內(nèi)容不需要記住，等到后面接觸了“插入排序”、“歸并排序”、“快速排序”等其它排序算法以后，再與“選擇排序”進(jìn)行比較，就不難理解了。

Python 實(shí)現(xiàn)1：

def swap(nums, idx1, idx2):
    if idx1 == idx2:
        return
    temp = nums[idx1]
    nums[idx1] = nums[idx2]
    nums[idx2] = temp


def select_sort(nums):
    """
    選擇排序，記錄最小元素的索引，最后才交換位置
    :param nums:
    :return:
    """
    l = len(nums)
    for i in range(l):
        min_index = i
        for j in range(i + 1, l):
            if nums[j] < nums[min_index]:
                min_index = j
        swap(nums, i, min_index)

說明：交換兩個(gè)數(shù)組中的元素，在 Python 中有更簡單的寫法，這是 Python 的語法糖，其它語言中是沒有的。

Python 實(shí)現(xiàn)2：主體部分和“Python 實(shí)現(xiàn)1”是一樣的。

def select_sort(nums):
    """
    選擇排序，記錄最小元素的索引，最后才交換位置
    :param nums:
    :return:
    """
    l = len(nums)
    for i in range(l):
        min_index = i
        for j in range(i + 1, l):
            if nums[j] < nums[min_index]:
                min_index = j
        nums[i], nums[min_index] = nums[min_index], nums[i]

這就是“選擇排序”算法。

如果你看到自己編寫的程序不正確，可以在程序中增加打印輸出，幫助你調(diào)試程序：

分析：第 1 輪要看 n 個(gè)元素；

第 2 輪要看 n-1 個(gè)元素；

第 3 輪要看 n-2 個(gè)元素；

……

第 n 輪要看 1 個(gè)元素；

對它們求和，用等差數(shù)列的通項(xiàng)公式。不過其實(shí)你也不用計(jì)算它，“時(shí)間復(fù)雜度”的計(jì)算我們只看次數(shù)最高的，所以“選擇排序”是平方時(shí)間復(fù)雜度。

分析：我們在交換兩個(gè)數(shù)組元素位置的時(shí)候，使用了 1 個(gè)輔助的空間。

是不是覺得很簡單，后面難度會一點(diǎn)一點(diǎn)加上來。此時(shí)，我們不妨做一些熱身的練習(xí)，我們后面會用到。這些練習(xí)只是減輕一點(diǎn)我們后面編寫測試用例的工作量，自己設(shè)計(jì)函數(shù)參數(shù)就好。

練習(xí)1：編寫三個(gè)函數(shù)，分別生成上文中提到的 3? 種類型的數(shù)組，要求能夠自定義生成數(shù)組的大小，這樣我們以后編寫測試用例的時(shí)候，就可以使用這些函數(shù)了。

練習(xí)2：編寫一個(gè)函數(shù)，判斷一個(gè)數(shù)組是否是升序排序。這個(gè)函數(shù)用于判斷我們的算法是否正確。

以下補(bǔ)充的知識是針對零基礎(chǔ)的朋友們的，因?yàn)槲乙彩橇慊A(chǔ)過來的，覺得這些東西可以說一下。

交換兩個(gè)變量的值，在排序中是常見的操作，并且也是程式化的，特別好記。先給出 Java 的寫法，再給出 Python 的寫法，最后給出“不是人的寫法”。

Java 寫法：

int temp = a;
a = b;
b = temp;

說明：這段代碼其實(shí)很好理解，要交換兩個(gè)變量的值，給要讓變量 a 把位置讓出來，即 int temp = a，然后把另一個(gè)變量 b 的值復(fù)制給 a，即 a = b，最后把之前 a 放在 temp 里的值賦給 b。這么說比較拗口，但其實(shí)我每次寫這段代碼的時(shí)候，都不用想這個(gè)過程的。因?yàn)檫@段代碼有規(guī)律可循：首先引入一個(gè)輔助變量 temp，這是必要的，然后就開始“首尾相接”了，你們看一下，是不是這個(gè)特點(diǎn)，最后接回 temp，記住這個(gè)規(guī)律就可以了。在 Python 中是這樣寫的：

Python 寫法1：

temp = a
a = b
b = temp

不過，Python 是一門神奇的編程語言，它提供了語法糖。

a, b = b, a

就可以交換兩個(gè)變量的值，不妨動(dòng)手驗(yàn)證一下：

是不是很酷，Python 的寫法有的時(shí)候更像偽代碼，更符合人的思維，但我沒有說 Python 更好的意思。其實(shí) Python 解釋器在后臺也是引入了輔助變量完成兩個(gè)變量的交換。其實(shí)，交換兩個(gè)變量的值，有更高效的做法，下面給出兩個(gè)交換變量的代碼，這兩種方法都不用引入輔助變量，相信聰明的你一定不難理解。

這里利用到了異或運(yùn)算的特點(diǎn)：異或運(yùn)算可以理解成不進(jìn)位的加法。那么一個(gè)數(shù)兩次異或同一個(gè)數(shù)，就和原來的數(shù)相等。上面基于異或運(yùn)算交換兩個(gè)變量的值就利用這個(gè)性質(zhì)。如果你還不熟悉異或運(yùn)算，不妨查閱一些資料。

前面我們說到了，我們?yōu)榱送怀雠判蛩惴ǖ乃枷?，將所有的例子僅限在數(shù)組排序中。事實(shí)上 Java 和 Python 這些面向?qū)ο蟮木幊陶Z言都支持對象的排序，只要給它們定義相應(yīng)的比較規(guī)則即可。有兩種方式，Python 和 Java 都是支持的：

（1）為對象添加用于比較的函數(shù)

在 Python 中，有一個(gè)魔法函數(shù)，實(shí)現(xiàn)它即可：

def __cmp__(self, other):
    pass

定義這個(gè)魔法函數(shù)，就可以使用對象集合進(jìn)行排序了。

在 Java 中，實(shí)現(xiàn) Comparable 接口中的 compareTo 方法。

如果你覺得給對象添加用于比較的函數(shù)，這種做法的侵入性比較強(qiáng)（因?yàn)樾薷牧祟悾?，那么你可以在排序的方法中，傳入比較規(guī)則。

（2）在排序的方法中，傳入比較規(guī)則

在 Python 中，比較規(guī)則可以通過 lambda 表達(dá)式傳入：

在 Java 中，可以傳入一個(gè)實(shí)現(xiàn)了 Comparator 接口的對象。