選擇排序法是一種不穩定的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的數據元素排完。
基本介紹
- 中文名：選擇排序法
- 外文名：Selection sort method
- 學科：計算機科學
- 分類：簡單選擇排序，樹型選擇排序
- 特點：不穩定
- 領域：數據結構
簡介,基本思想,算法描述,類別,性能分析,時間複雜度,穩定性,代碼示例,
簡介
基本思想
排序定義。所謂計算機中的排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。而排序算法（Sorting algorithm）則是一種能將一串數據依照特定的方式進行排列的一種算法。
排序方式。利用所需重排記錄的排序碼（Sort Key）的值的大小，按照升序或降序將原紀錄的順序重新安排。排序類別。內排序可以分為插入排序（insertion sort）、選擇排序（selection sort）、交換排序（exchange sort）、歸併排序（merge sort）以及分配排序（distribution sort）。
選擇排序法是在要排序的一組數中，選出最小（或最大）的一個數與第一個位置的數交換；在剩下的數當中找最小的與第二個位置的數交換，即順序放在已排好序的數列的最後，如此循環，直到全部數據元素排完為止。
算法描述
選擇排序法的第一層循環從起始元素開始選到倒數第二個元素，主要是在每次進入的第二層循環之前，將外層循環的下標賦值給臨時變數，接下來的第二層循環中，如果發現有比這個最小位置處的元素更小的元素，則將那個更小的元素的下標賦給臨時變數，最後，在二層循環退出後，如果臨時變數改變，則說明，有比當前外層循環位置更小的元素，需要將這兩個元素交換。
類別
（1）直接選擇排序。①基本思想。實現思想是每步從排序記錄中選出排序碼最小（最大）的記錄，放在已排序記錄序列的最後（前）；②算法特點。直接選擇排序算法n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
（2）樹形選擇排序。①基本思想。其實現思想是保存先前比較的結果以減少比較次數，是一種不穩定的排序方法。首先對n個記錄的關鍵字進行兩兩比較，然後在n/2個較小者之間再進行兩兩比較，如此重複，直至選出最小的記錄為止。
（3）堆排序。①基本思想。堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進；②算法描述。從算法描述來看，堆排序需要兩個過程，即建立堆和堆頂與堆的最後一個元素交換位置。所以堆排序有兩個函式組成，一是建堆的滲透函式，二是反覆調用滲透函式實現排序的函式；③算法特點。堆排序可通過樹形結構保存部分比較結果，可減少比較次數。但由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的檔案。
性能分析
時間複雜度
選擇排序的交換操作介於 0 和 (n - 1） 次之間。選擇排序的比較操作為 n (n - 1） / 2 次之間。選擇排序的賦值操作介於 0 和 3 (n - 1） 次之間。比較次數O(n^2），比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1）+(n-2）+...+1=n*(n-1）/2。交換次數O(n），最好情況是，已經有序，交換0次；最壞情況交換n-1次，逆序交換n/2次。交換次數比冒泡排序少多了，由於交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。其中直接選擇排序的時間複雜度為O（n*n），空間複雜度為O（1）。樹形選擇排序的時間複雜度為O（nlog2n），空間複雜度為O（n）。堆排序的平均時間複雜度為O（nlog2n），效率高，但是實現相對複雜，空間代價為O（1）。
穩定性
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裡面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那么交換後穩定性就被破壞了。舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前後順序就被破壞了，所以選擇排序是一個不穩定的排序算法。
代碼示例
C語言
void swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp;}void selection_sort(int arr[], int len) { int i,j; for (i = 0 ; i < len - 1 ; i++) { int min = i; for (j = i + 1; j < len; j++) if (arr[j] < arr[min]) min = j; swap(&arr[min], &arr[i]); }}C++
template<typename T> void selection_sort(std::vector<T>& arr) { for (int i = 0; i < arr.size() - 1; i++) { int min = i; for (int j = i + 1; j < arr.size(); j++) if (arr[j] < arr[min]) min = j; std::swap(arr[i], arr[min]); }}Python
def selection_sort(arr): for i in range(len(arr)-1): minIndex=i for j in range(i+1,len(arr)): if arr[minIndex]>arr[j]: minIndex=j if i==minIndex: pass else: arr[i],arr[minIndex]=arr[minIndex],arr[i] return arrif __name__ == '__main__': testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12] print(selection_sort(testlist))
Java
public static void selectionSort(int[] arr) { int min, temp; for (int i = 0; i < arr.length; i++) { // 初始化未排序序列中最小數據數組下標 min = i; for (int j = i+1; j < arr.length; j++) { // 在未排序元素中繼續尋找最小元素，並保存其下標 if (arr[j] < arr[min]) { min = j; } } // 將未排序列中最小元素放到已排序列末尾 if (min != i) { temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } }