# 選擇排序算法 > 原文： [https://www.programiz.com/dsa/selection-sort](https://www.programiz.com/dsa/selection-sort) #### 在本教程中，您將學習選擇排序的工作方式。 此外，您還將找到使用 C，C++ ，Java 和 Python 進行選擇排序的工作示例。 選擇排序是一種算法，它在每次迭代中從未排序列表中選擇最小的元素，并將該元素放在未排序列表的開頭。 * * * ## 選擇排序如何工作？ 1. 將第一個元素設置為`minimum`。  選擇第一個元素作為最小值 2. 將`minimum`與第二個元素進行比較。 如果第二個元素小于`minimum`，則將第二個元素指定為`minimum`。 將`minimum`與第三個元素進行比較。 同樣，如果第三個元素較小，則將`minimum`分配給第三個元素，否則不執行任何操作。 該過程一直進行到最后一個元素。  將其余元素的最小值進行比較 3. 每次迭代后，`minimum`都放在未排序列表的前面。  以最少的 交換第一個 4. 對于每次迭代，索引從第一個未排序元素開始。 重復步驟 1 到 3，直到所有元素都放置在正確的位置。  第一次迭代  第二次迭代  第三次迭代 [  第四次迭代 * * * ## 選擇排序算法 ``` selectionSort(array, size) repeat (size - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element < currentMinimum set element as new minimum swap minimum with first unsorted position end selectionSort ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change > to < in this line # select the minimum element in each loop if array[i] < array[min_idx]: min_idx = i # put min at the correct position (array[step], array[min_idx]) = (array[min_idx], array[step]) data = [-2, 45, 0, 11, -9] size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data) ``` ```java // Selection sort in Java import java.util.Arrays; class SelectionSort { void selectionSort(int array[]) { int size = array.length; for (int step = 0; step < size - 1; step++) { int min_idx = step; for (int i = step + 1; i < size; i++) { // To sort in descending order, change > to < in this line. // Select the minimum element in each loop. if (array[i] < array[min_idx]) { min_idx = i; } } // put min at the correct position int temp = array[step]; array[step] = array[min_idx]; array[min_idx] = temp; } } // driver code public static void main(String args[]) { int[] data = { 20, 12, 10, 15, 2 }; SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); } } ``` ```c // Selection sort in C #include <stdio.h> // function to swap the the position of two elements void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void selectionSort(int array[], int size) { for (int step = 0; step < size - 1; step++) { int min_idx = step; for (int i = step + 1; i < size; i++) { // To sort in descending order, change > to < in this line. // Select the minimum element in each loop. if (array[i] < array[min_idx]) min_idx = i; } // put min at the correct position swap(&array[min_idx], &array[step]); } } // function to print an array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // driver code int main() { int data[] = {20, 12, 10, 15, 2}; int size = sizeof(data) / sizeof(data[0]); selectionSort(data, size); printf("Sorted array in Acsending Order:\n"); printArray(data, size); } ``` ```cpp // Selection sort in C++ #include <iostream> using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // function to print an array void printArray(int array[], int size) { for (int i = 0; i < size; i++) { cout << array[i] << " "; } cout << endl; } void selectionSort(int array[], int size) { for (int step = 0; step < size - 1; step++) { int min_idx = step; for (int i = step + 1; i < size; i++) { // To sort in descending order, change > to < in this line. // Select the minimum element in each loop. if (array[i] < array[min_idx]) min_idx = i; } // put min at the correct position swap(&array[min_idx], &array[step]); } } // driver code int main() { int data[] = {20, 12, 10, 15, 2}; int size = sizeof(data) / sizeof(data[0]); selectionSort(data, size); cout << "Sorted array in Acsending Order:\n"; printArray(data, size); } ``` * * * ## 復雜度 | 周期 | 比較次數 | | --- | --- | | 第一 | （`n-1`） | | 第二 | （`n-2`） | | 第三 | （`n-3`） | | ... | ... | | 最后 | 1 | 比較次數：`(n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2`幾乎等于`n^2`。 **復雜度** = `O(n^2)` 同樣，我們可以通過簡單地觀察循環數來分析復雜度。 有 2 個循環，因此復雜度為`n*n = n^2`。 **時間復雜度**： * **最壞情況的復雜度**： `O(n^2)` 如果我們要以升序排序，而數組是以降序排序，那么會發生最壞情況。 * **最佳情況復雜度**： `O(n^2)` 在對數組進行排序時會發生 * **平均情況復雜度**： `O(n^2)` 當數組的元素處于混亂順序（既不升也不降）時，會發生這種情況。 選擇排序的時間復雜度在所有情況下都是相同的。 在每一步中，您都必須找到最小的元素并將其放在正確的位置。 直到沒有到達數組的末尾，才知道最小元素。 **空間復雜度**： 空間復雜度為`O(1)`，因為使用了額外的變量`temp`。 * * * ## 選擇排序應用 在以下情況下使用選擇排序： * 要排序的一個小列表 * 交換成本無所謂 * 必須對所有要素進行檢查 * 寫入存儲器的成本就像閃存一樣重要（與冒泡排序的`O(n^2)`相比，寫入/交換的次數為`O(n)`）