选择排序

每一趟（如第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,7

1,2,3,9,4,5,6,8,7

1,2,3,9,4,5,6,8,7

1,2,3,4,9,5,6,8,7

1,2,3,4,5,9,6,8,7

1,2,3,4,5,6,9,8,7

1,2,3,4,5,6,7,8,9

1,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. 稳定性： 不稳定