直接選擇排序時間復雜度

選擇排序是一種簡單直觀的排序算法，無論什么數據進去都是 O(n?) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間。

推薦度：

導讀選擇排序是一種簡單直觀的排序算法，無論什么數據進去都是 O(n?) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間。

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。以下是選擇排序算法：

選擇排序是一種簡單直觀的排序算法，無論什么數據進去都是 O(n?) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。

1. 算法步驟

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。

重復第二步，直到所有元素均排序完畢。

2. 動圖演示

代碼實現JavaScript 代碼實現實例 function selectionSort(arr) {? ? var len = arr.length;? ? var minIndex, temp;? ? for (var i = 0; i < len - 1; i++) {? ? ? ? minIndex = i;? ? ? ? for (var j = i + 1; j < len; j++) {? ? ? ? ? ? if (arr[j] < arr[minIndex]) { ? ? // 尋找最小的數? ? ? ? ? ? ? ? minIndex = j; ? ? ? ? ? ? ? ? // 將最小數的索引保存? ? ? ? ? ? }? ? ? ? }? ? ? ? temp = arr[i];? ? ? ? arr[i] = arr[minIndex];? ? ? ? arr[minIndex] = temp;? ? }? ? return arr;}Python 代碼實現實例 def selectionSort(arr):? ? for i in range(len(arr) - 1):? ? ? ? # 記錄最小數的索引? ? ? ? minIndex = i? ? ? ? for j in range(i + 1, len(arr)):? ? ? ? ? ? if arr[j] < arr[minIndex]:? ? ? ? ? ? ? ? minIndex = j? ? ? ? # i 不是最小數時，將 i 和最小數進行交換? ? ? ? if i != minIndex:? ? ? ? ? ? arr[i], arr[minIndex] = arr[minIndex], arr[i]? ? return arrGo 代碼實現實例 func selectionSort(arr []int) []int {? ? ? ? length := len(arr)? ? ? ? for i := 0; i < length-1; i++ {? ? ? ? ? ? ? ? min := i? ? ? ? ? ? ? ? for j := i + 1; j < length; j++ {? ? ? ? ? ? ? ? ? ? ? ? if arr[min] > arr[j] {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? min = j? ? ? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? arr[i], arr[min] = arr[min], arr[i]? ? ? ? }? ? ? ? return arr}Java 代碼實現實例 public class SelectionSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? // 總共要經過 N-1 輪比較? ? ? ? for (int i = 0; i < arr.length - 1; i++) {? ? ? ? ? ? int min = i;? ? ? ? ? ? // 每輪需要比較的次數 N-i? ? ? ? ? ? for (int j = i + 1; j < arr.length; j++) {? ? ? ? ? ? ? ? if (arr[j] < arr[min]) {? ? ? ? ? ? ? ? ? ? // 記錄目前能找到的最小值元素的下標? ? ? ? ? ? ? ? ? ? min = j;? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? ? ? // 將找到的最小值和i位置所在的值進行交換? ? ? ? ? ? if (i != min) {? ? ? ? ? ? ? ? int tmp = arr[i];? ? ? ? ? ? ? ? arr[i] = arr[min];? ? ? ? ? ? ? ? arr[min] = tmp;? ? ? ? ? ? }? ? ? ? }? ? ? ? return arr;? ? }}PHP 代碼實現實例 function selectionSort($arr){? ? $len = count($arr);? ? for ($i = 0; $i < $len - 1; $i++) {? ? ? ? $minIndex = $i;? ? ? ? for ($j = $i + 1; $j < $len; $j++) {? ? ? ? ? ? if ($arr[$j] < $arr[$minIndex]) {? ? ? ? ? ? ? ? $minIndex = $j;? ? ? ? ? ? }? ? ? ? }? ? ? ? $temp = $arr[$i];? ? ? ? $arr[$i] = $arr[$minIndex];? ? ? ? $arr[$minIndex] = $temp;? ? }? ? return $arr;}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 //整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能void selection_sort(std::vector& 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]);? ? ? ? }}C#實例 static void selection_sort(T[] arr) where T : System.IComparable{//整數或浮點數皆可使用? ? ? ? int i, j, min, len = arr.Length;? ? ? ? T temp;? ? ? ? for (i = 0; i < len - 1; i++) {? ? ? ? ? ? ? ? min = i;? ? ? ? ? ? ? ? for (j = i + 1; j < len; j++)? ? ? ? ? ? ? ? ? ? ? ? if (arr[min].CompareTo(arr[j]) > 0)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? min = j;? ? ? ? ? ? ? ? temp = arr[min];? ? ? ? ? ? ? ? arr[min] = arr[i];? ? ? ? ? ? ? ? arr[i] = temp;? ? ? ? }}Swift實例 import Foundation/// 選擇排序////// - Parameter list: 需要排序的數組func selectionSort(_ list: inout [Int]) -> Void {? ? for j in 0.. list[i] {? ? ? ? ? ? ? ? minIndex = i? ? ? ? ? ? }? ? ? ? }? ? ? ? list.swapAt(j, minIndex)? ? }}

原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md

參考地址：https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F

以下是熱心網友對選擇排序算法的補充，僅供參考：

熱心網友提供的補充1：

Kotlin 實現

class SelectionSort { 
    /** 
    * 拓展IntArray為他提供數據兩個數交換位置的方法 
    * @param i 第一個數的下標 
    * @param j 第二個數的下標 
    */ 
    fun IntArray.swap(i:Int,j:Int){ 
        var temp=this[i] 
        this[i]=this[j] 
        this[j]=temp 
    } 
    fun selectionSort(array: IntArray):IntArray{
        for (i in array.indices){ 
            //假設最小值是i 
            var min=i 
            var j=i+1 
            while (j in array.indices){ 
                if (array[j]以上為選擇排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用一張圖概括： 
關于時間復雜度
平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。
關于穩定性
穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。
不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋：
n：數據規模
k："桶"的個數
In-place：占用常數內存，不占用額外內存
Out-place：占用額外內存
穩定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同