資訊專欄INFORMATION COLUMN
摘要：選擇排序算法實現實現選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個數組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實現前面我們說到了，我們為了突出排序算法的思想，將所有的例子僅限在數組排序中。
“算法”的入門，從“排序算法”開始，希望通過“排序算法”這一部分的學習，能夠讓我們認識到“算法”的威力，“算法”不僅僅只存在與我們的面試中（那時只是因為我不知道“算法”而已），“算法”無處不在，“算法”很有用。
下面是一些說明：
1、會直接使用“空間復雜度”和“時間復雜度”的概念，不妨先有個印象，實在糾結的話，可以去翻翻書，“空間復雜度”和“時間復雜度”最多的應用就在于比較不同算法的優劣；
2、“排序算法”這一章節為了方便說明，使用的例子都是以“整數數組”為例，并且是“升序排序”，學習過 Java 語言的朋友就知道，待排序的也可以是對象，只要實現了相關的接口，實現了相應的比較規則，就可以進行排序。
我們選擇“選擇排序”作為算法入門的開篇。理由如下：
1、“選擇排序”算法的思想十分簡單，非常接近我們的思維方式：先找最小的數、再找第 2 小的數，依次類推，最后剩下的就是數組中最大的元素；
2、“選擇排序”的實現也很簡單。
一、通過具體例子理解“選擇排序”的思想思想：不斷地選擇剩余元素之中的最小者。
“選擇排序”算法的特點1、每一輪交換都能排定一個元素，交換的總次數是固定的；
說明：“交換的總次數”等于“元素的總數 - 1”，因此算法的時間復雜度取決于比較的次數；
2、運行時間和輸入無關，即：一個“已經有序”的數組、一個所有的元素都相等的數組、一個元素隨機排列的數組所用的排序時間是一樣的；
說明：后續我們會編寫一些測試用例，比較不同的算法在不同的測試用例上的運行時間。這些測試用例中，就有以下 $3$ 種。
（1）一個“已經有序”的數組：例如：[4, 5, 6, 8, 9, 10]，以后我們學習的排序算法中，就有一種算法名叫“插入排序”就能檢測出數組是不是有序的，極端情況下，“插入排序”算法看一遍數組中的元素，就知道數組已經有序了，后續就什么都不用做了。而“選擇排序”得一遍又一遍看數組的元素好幾遍，“幾乎是”有多少個數，就會看數組多少遍，每一遍選出當前沒有排定元素中的最小者；
（2）一個所有的元素都相等的數組，例如：[6, 6, 6, 6, 6, 6]；
（3）一個元素隨機排列的數組，就是我們一般意義下，雜亂無序的數組，例如：[8, 18, 10, 6, 5, 4, 20]。
3、數據移動是最少的。
這點應該說是“選擇排序”的優點了，如果我們的排序任務對交換操作非常敏感，不妨考慮“選擇排序”。
例如：我們待排序的是碼頭上的集裝箱，交換集裝箱的成本是很高的，此時“選擇排序”就是最好的選擇。
小貼士：這一部分內容不需要記住，等到后面接觸了“插入排序”、“歸并排序”、“快速排序”等其它排序算法以后，再與“選擇排序”進行比較，就不難理解了。
“選擇排序”算法實現Python 實現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)
說明：交換兩個數組中的元素，在 Python 中有更簡單的寫法，這是 Python 的語法糖，其它語言中是沒有的。
Python 實現2：主體部分和“Python 實現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]
這就是“選擇排序”算法。
如果你看到自己編寫的程序不正確，可以在程序中增加打印輸出，幫助你調試程序：
二、時間復雜度與空間復雜度 時間復雜度：O(n^2)分析：第 1 輪要看 n 個元素；
第 2 輪要看 n-1 個元素；
第 3 輪要看 n-2 個元素；
……
第 n 輪要看 1 個元素；
對它們求和，用等差數列的通項公式。不過其實你也不用計算它，“時間復雜度”的計算我們只看次數最高的，所以“選擇排序”是平方時間復雜度。
空間復雜度：O(1)分析：我們在交換兩個數組元素位置的時候，使用了 1 個輔助的空間。
三、熱身練習是不是覺得很簡單，后面難度會一點一點加上來。此時，我們不妨做一些熱身的練習，我們后面會用到。這些練習只是減輕一點我們后面編寫測試用例的工作量，自己設計函數參數就好。
練習1：編寫三個函數，分別生成上文中提到的 3? 種類型的數組，要求能夠自定義生成數組的大小，這樣我們以后編寫測試用例的時候，就可以使用這些函數了。
練習2：編寫一個函數，判斷一個數組是否是升序排序。這個函數用于判斷我們的算法是否正確。
四、補充知識以下補充的知識是針對零基礎的朋友們的，因為我也是零基礎過來的，覺得這些東西可以說一下。
1、交換兩個變量的值交換兩個變量的值，在排序中是常見的操作，并且也是程式化的，特別好記。先給出 Java 的寫法，再給出 Python 的寫法，最后給出“不是人的寫法”。
Java 寫法：
int temp = a; a = b; b = temp;
說明：這段代碼其實很好理解，要交換兩個變量的值，給要讓變量 a 把位置讓出來，即 int temp = a，然后把另一個變量 b 的值復制給 a，即 a = b，最后把之前 a 放在 temp 里的值賦給 b。這么說比較拗口，但其實我每次寫這段代碼的時候，都不用想這個過程的。因為這段代碼有規律可循：首先引入一個輔助變量 temp，這是必要的，然后就開始“首尾相接”了，你們看一下，是不是這個特點，最后接回 temp，記住這個規律就可以了。在 Python 中是這樣寫的：
Python 寫法1：
temp = a a = b b = temp
不過，Python 是一門神奇的編程語言，它提供了語法糖。
使用 Python 語法糖交換兩個變量的值a, b = b, a
就可以交換兩個變量的值，不妨動手驗證一下：
是不是很酷，Python 的寫法有的時候更像偽代碼，更符合人的思維，但我沒有說 Python 更好的意思。其實 Python 解釋器在后臺也是引入了輔助變量完成兩個變量的交換。其實，交換兩個變量的值，有更高效的做法，下面給出兩個交換變量的代碼，這兩種方法都不用引入輔助變量，相信聰明的你一定不難理解。
基于加減法交換兩個變量的值 基于異或運算交換兩個變量的值這里利用到了異或運算的特點：異或運算可以理解成不進位的加法。那么一個數兩次異或同一個數，就和原來的數相等。上面基于異或運算交換兩個變量的值就利用這個性質。如果你還不熟悉異或運算，不妨查閱一些資料。
2、Java 和 Python 語言中比較器的實現前面我們說到了，我們為了突出排序算法的思想，將所有的例子僅限在數組排序中。事實上 Java 和 Python 這些面向對象的編程語言都支持對象的排序，只要給它們定義相應的比較規則即可。有兩種方式，Python 和 Java 都是支持的：
（1）為對象添加用于比較的函數
在 Python 中，有一個魔法函數，實現它即可：
def __cmp__(self, other):
pass
定義這個魔法函數，就可以使用對象集合進行排序了。
在 Java 中，實現 Comparable 接口中的 compareTo 方法。
如果你覺得給對象添加用于比較的函數，這種做法的侵入性比較強（因為修改了類），那么你可以在排序的方法中，傳入比較規則。
（2）在排序的方法中，傳入比較規則
在 Python 中，比較規則可以通過 lambda 表達式傳入：
在 Java 中，可以傳入一個實現了 Comparator 接口的對象。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/45037.html
摘要：數據科學其實就是機器學習，數據分析和數據可視化。機器學習通過實現算法，該算法能夠自動檢測輸入中的模式。一般應用于人臉識別語音識別熱門機器學習算法包括神經網絡深度學習支持向量機隨機森林進行數據分析可視化進行數據可視化時，是非常熱門的庫。 ...
摘要：現在發出來的版本，我重新使用了語言實現。其實我之前介紹的老師課程也大量參考和使用算法這本書上的思路和例題。看這本書主要是讓我覺得算法可以以比較輕松的方式入門。劍指這本書主要用于準備算法面試，在網絡上備受好評。 我是一個半路出家的程序員，在我剛開始從事編碼工作的頭幾年，我沒有接觸過算法和數據結構，覺得它們是只會在我找工作的時候用得到的知識。盡管有很多人跟我說過算法和數據結構無比重要，我也...
摘要：我是布小禪，一枚自學萌新，跟著我每天進步一點點吧說了這么多暫時也就夠了，那么就告辭吧 文章目錄 ?? 前言 ??? 作者簡介 ??文件操作?1??、open函數...
摘要：服務層這一層有點東西了，算是整個框架的核心，如果你跟敖丙一樣以后都是從事后端開發的話，我們基本上整個技術生涯，大部分時間都在跟這一層的技術棧打交道了，各種琳瑯滿目的中間件，計算機基礎知識，操作，算法數據結構，架構框架，研發工具等等。 前言 自學/學習路線這樣的一期我想寫很久了，因為一直想寫的...
閱讀 1846·2021-11-25 09:43
閱讀 3688·2021-11-24 10:32
閱讀 1076·2021-10-13 09:39
閱讀 2328·2021-09-10 11:24
閱讀 3344·2021-07-25 21:37
閱讀 3464·2019-08-30 15:56
閱讀 858·2019-08-30 15:44
閱讀 1449·2019-08-30 13:18
