選擇排序法

選擇排序法是一種不穩定的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的數據元素排完。

基本介紹

• 中文名：選擇排序法
• 外文名：Selection sort method
• 學科：計算機科學
• 分類：簡單選擇排序，樹型選擇排序
• 特點：不穩定
• 領域：數據結構

簡介

基本思想

排序定義。所謂計算機中的排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。而排序算法（Sorting algorithm）則是一種能將一串數據依照特定的方式進行排列的一種算法。

排序方式。利用所需重排記錄的排序碼（Sort Key）的值的大小，按照升序或降序將原紀錄的順序重新安排。排序類別。內排序可以分為插入排序（insertion sort）、選擇排序（selection sort）、交換排序（exchange sort）、歸併排序（merge sort）以及分配排序（distribution sort）。

選擇排序法是在要排序的一組數中，選出最小（或最大）的一個數與第一個位置的數交換；在剩下的數當中找最小的與第二個位置的數交換，即順序放在已排好序的數列的最後，如此循環，直到全部數據元素排完為止。

算法描述

選擇排序法的第一層循環從起始元素開始選到倒數第二個元素，主要是在每次進入的第二層循環之前，將外層循環的下標賦值給臨時變數，接下來的第二層循環中，如果發現有比這個最小位置處的元素更小的元素，則將那個更小的元素的下標賦給臨時變數，最後，在二層循環退出後，如果臨時變數改變，則說明，有比當前外層循環位置更小的元素，需要將這兩個元素交換。

類別

常見的選擇排序可以分為直接選擇排序（Straight selection sort）、樹形選擇排序（Tree-type selection sort）以及堆排序（Heap 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 arr
if __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;
            }
        }
    }