（3）选择排序 (Selection Sort)
最后更新于：2022-04-01 21:03:25
[TOC]
## 算法原理
> 选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的序列进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
[](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/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://docs.gechiui.com/gc-content/uploads/sites/kancloud/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)
';