js的算法-选择排序（简单选择排序）

选择排序

每一趟（如第i趟）在后面n-i+1(i=1,2,……n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i 个元素，直到第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。

快速选择排序

基本思想：假设排序表为L【1……n】,第i 趟排序即从L【i……n】中选择关键字最小的元素与L（i）交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。

演示

代码展示

let ary = [3, 8, 1, 9, 4, 5, 6, 2, 7];
/*** 插入排序* @param {*} arr*/
function singleChoose(arr) {for (let i = 0; i <= arr.length - 2; i++) {//外层循环 从第一个元素到倒数第二个元素let min = arr[i];let k = i; //标记最小的元素所在的下标for (let j = i + 1; j <= arr.length - 1; j++) {// 内层循环就是一个找最小值的过程if (arr[j] < min) {min = arr[j];k = j; //同时要更新最小值所在的下表}}arr[k] = arr[i]; //让i下标的元素放到最小值所在的下标处arr[i] = min; // 在i下标处放置最小元素console.log(arr + "\n");}
}singleChoose(ary);
console.log(ary);

运行结果：

1,8,3,9,4,5,6,2,71,2,3,9,4,5,6,8,71,2,3,9,4,5,6,8,71,2,3,4,9,5,6,8,71,2,3,4,5,9,6,8,71,2,3,4,5,6,9,8,71,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9[1, 2, 3, 4, 5,6, 7, 8, 9
]

性能分析

时间复杂度	空间复杂度
最好情况下：O（n^ 2）;最坏情况下：O（n^2）;
平均时间复杂度：O（n^2）;	仅使用了常数个辅助单元，所以空间复杂度为O(1)

总结

1. 稳定性： 不稳定