[TOC]
## 算法原理
> 選擇排序（Selection Sort）是一種簡單直觀的排序算法。它的工作原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優點與數據移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的序列進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種。
[](https://box.kancloud.cn/2015-07-26_55b45660efe5f.gif "圖片來源于維基百科")
圖片來源于維基百科
## 實例分析
以數組 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 為例，先直觀看一下每一步的變化，后面再介紹細節
第一次從數組 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的數 0，放到數組的最前面（與第一個元素進行交換）：
~~~
min
↓
8 5 2 6 9 3 1 4 0 7
↑ ↑
└───────────────────────────────┘
~~~
交換后：
~~~
0 5 2 6 9 3 1 4 8 7
~~~
在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的數 1，與該序列的第一個個元素進行位置交換：
~~~
min
↓
0 5 2 6 9 3 1 4 8 7
↑ ↑
└───────────────────┘
~~~
交換后：
~~~
0 1 2 6 9 3 5 4 8 7
~~~
在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的數 2，與該序列的第一個個元素進行位置交換（實際上不需要交換）：
~~~
min
↓
0 1 2 6 9 3 5 4 8 7
↑
~~~
重復上述過程，直到最后一個元素就完成了排序。
~~~
min
↓
0 1 2 6 9 3 5 4 8 7
↑ ↑
└───────┘
min
↓
0 1 2 3 9 6 5 4 8 7
↑ ↑
└───────────┘
min
↓
0 1 2 3 4 6 5 9 8 7
↑ ↑
└───┘
min
↓
0 1 2 3 4 5 6 9 8 7
↑
min
↓
0 1 2 3 4 5 6 9 8 7
↑ ↑
└───────┘
min
↓
0 1 2 3 4 5 6 7 8 9
↑
min
↓
0 1 2 3 4 5 6 7 8 9
↑
~~~
[](https://box.kancloud.cn/2015-07-26_55b4566aa59fe.gif "圖片來源于維基百科")
圖片來源于維基百科
## JavaScript 語言實現
~~~
function selectionSort(array) {
var length = array.length,
i,
j,
minIndex,
minValue,
temp;
for (i = 0; i < length - 1; i++) {
minIndex = i;
minValue = array[minIndex];
for (j = i + 1; j < length; j++) {
if (array[j] < minValue) {
minIndex = j;
minValue = array[minIndex];
}
}
// 交換位置
temp = array[i];
array[i] = minValue;
array[minIndex] = temp;
}
return array
}
~~~
## 參考文章
* [en.wikipedia.org](http://en.wikipedia.org/wiki/Selection_sort)
* [wikibooks](http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Selection_sort)
* [維基百科](http://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F)
* [Selection sort in JavaScript](http://techblog.floorplanner.com/post/20528548241/selection-sort-in-javascript)
* [直接選擇排序(Straight Selection Sort)](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.1.htm)
* [經典排序算法 - 選擇排序 Selection Sort](http://www.cnblogs.com/kkun/archive/2011/11/23/2260281.html)
* [選擇排序算法](http://sjjg.js.zwu.edu.cn/SFXX/paixu/paixu6.4.1.html)
