選擇排序算法

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

推薦度：

點(diǎn)擊下載本文 文檔為doc格式

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

.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}

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

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

1. 算法步驟

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

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

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

2. 動圖演示

代碼實(shí)現(xiàn)JavaScript 代碼實(shí)現(xiàn)實(shí)例 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]) { ? ? // 尋找最小的數(shù)? ? ? ? ? ? ? ? minIndex = j; ? ? ? ? ? ? ? ? // 將最小數(shù)的索引保存? ? ? ? ? ? }? ? ? ? }? ? ? ? temp = arr[i];? ? ? ? arr[i] = arr[minIndex];? ? ? ? arr[minIndex] = temp;? ? }? ? return arr;}Python 代碼實(shí)現(xiàn)實(shí)例 def selectionSort(arr):? ? for i in range(len(arr) - 1):? ? ? ? # 記錄最小數(shù)的索引? ? ? ? minIndex = i? ? ? ? for j in range(i + 1, len(arr)):? ? ? ? ? ? if arr[j] < arr[minIndex]:? ? ? ? ? ? ? ? minIndex = j? ? ? ? # i 不是最小數(shù)時(shí)，將 i 和最小數(shù)進(jìn)行交換? ? ? ? if i != minIndex:? ? ? ? ? ? arr[i], arr[minIndex] = arr[minIndex], arr[i]? ? return arrGo 代碼實(shí)現(xiàn)實(shí)例 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 代碼實(shí)現(xiàn)實(shí)例 public class SelectionSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? // 總共要經(jīng)過 N-1 輪比較? ? ? ? for (int i = 0; i < arr.length - 1; i++) {? ? ? ? ? ? int min = i;? ? ? ? ? ? // 每輪需要比較的次數(shù) N-i? ? ? ? ? ? for (int j = i + 1; j < arr.length; j++) {? ? ? ? ? ? ? ? if (arr[j] < arr[min]) {? ? ? ? ? ? ? ? ? ? // 記錄目前能找到的最小值元素的下標(biāo)? ? ? ? ? ? ? ? ? ? min = j;? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? ? ? // 將找到的最小值和i位置所在的值進(jìn)行交換? ? ? ? ? ? if (i != min) {? ? ? ? ? ? ? ? int tmp = arr[i];? ? ? ? ? ? ? ? arr[i] = arr[min];? ? ? ? ? ? ? ? arr[min] = tmp;? ? ? ? ? ? }? ? ? ? }? ? ? ? return arr;? ? }}PHP 代碼實(shí)現(xiàn)實(shí)例 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 語言實(shí)例 void swap(int *a,int *b) //交換兩個(gè)變數(shù){? ? 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; ? ?//紀(jì)錄最小值? ? ? ? ? ? ? ? swap(&arr[min], &arr[i]); ? ?//做交換? ? ? ? }}C++實(shí)例 template //整數(shù)或浮點(diǎn)數(shù)皆可使用，若要使用物件（class）時(shí)必須設(shè)定大於（>）的運(yùn)算子功能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#實(shí)例 static void selection_sort(T[] arr) where T : System.IComparable{//整數(shù)或浮點(diǎn)數(shù)皆可使用? ? ? ? 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實(shí)例 import Foundation/// 選擇排序////// - Parameter list: 需要排序的數(shù)組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

以下是熱心網(wǎng)友對選擇排序算法的補(bǔ)充，僅供參考：

熱心網(wǎng)友提供的補(bǔ)充1：

Kotlin 實(shí)現(xiàn)

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