介绍
今天给大家介绍选择排序算法中的——简单选择排序，该排序算法很容易理解，一句话表述:
每一次遍历找到最小的数和最前面的待排序数互换位置，直到所有数都已排序。
还是以这组被我用各种算法玩的待排序数为例（升序, 粗体字为已排序数；标红字为需互换数）：[77, 6, 37, 96, 34, 6, 14]
| 遍历 | 数组情况 | 解释 |
|---|---|---|
| 1 | [77, 6, 37, 96, 34, 6, 14] |
第1次遍历后发现6是最小的，和第1个待排序数77互换
|
| 2 | [6, 77, 37, 96, 34, 6, 14] |
第2次遍历后发现6是最小的，和第1个待排序数77互换
|
| 3 | [6, 6, 37, 96, 34, 77, 14] |
第3次遍历后发现14是最小的，和第1个待排序数37互换
|
| 4 | [6, 6, 14, 96, 34, 77, 37] |
第4次遍历后发现34是最小的，和第1个待排序数96互换
|
| 5 | [6, 6, 14, 34, 96, 77, 37] |
第5次遍历后发现37是最小的，和第1个待排序数96互换
|
| 6 | [6, 6, 14, 34, 37, 96, 77] |
第6次遍历后发现77是最小的，和第1个待排序数96互换
|
| - | [6, 6, 14, 34, 37, 77, 96] | 排序完成 |
例子
js实现如下(升序)：
function sort(arr) {
for(let i = 0; i < arr.length; i++){
let minIndex = i;
for(let j = i + 1; j < arr.length; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; //解构互换位置
}
return arr;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]
时间复杂度
遍历次数的计算与冒泡排序类似：n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 - 0.5 * n，所以时间复杂度为O(n^2)。
感谢阅读！欢迎关注！持续更新中...
网友评论