选择排序与冒泡排序的顺序刚好相反。如果是升序，会先把数值较小的先固定到左端，依次到最大值固定在右端。

选择排序会用到嵌套循环，外循环从数组第一个元素开始，移动到倒数第二个元素，内循环从外循环元素的下一个元素开始到最后一个元素。

原理

假设是升序

  • 从数组第一个元素开始，与后面所有的元素进行比较
  • 如果第一个元素较大，则进行交换，否则继续下一次比较
  • 直到最后一个数为止，则本轮循环结束，第一个最小值固定
  • 下一轮循环从第二个元素开始
  • 当只剩下两个不固定元素时，进行一次比较之后就结束整个循环

举例：数组 [5,2,8,4,9,1]

第一趟排序： 原始数据：5 2 8 4 9 1

最小数据1，把1放在首位，也就是1和5互换位置，

排序结果：1 2 8 4 9 5

第二趟排序：

第1以外的数据{2 8 4 9 5}进行比较，2最小，

排序结果：1 2 8 4 9 5

第三趟排序：

除1、2以外的数据{8 4 9 5}进行比较，4最小，8和4交换

排序结果：1 2 4 8 9 5

第四趟排序：

除第1、2、4以外的其他数据{8 9 5}进行比较，5最小，8和5交换

排序结果：1 2 4 5 9 8

第五趟排序：

除第1、2、4、5以外的其他数据{9 8}进行比较，8最小，8和9交换

排序结果：1 2 4 5 8 9

实现

  1. function selectionSort(arr) {
  2.   // 保存最后的索引
  3.   let len = arr.length - 1,
  4.     outer, inner, min;
  6.   // 外层遍历到倒数第二个元素
  7.   for (outer = 0; outer < len; outer++) {
  8.     min = outer; 
  9.     // 内层从 外层的下一个元素开始，遍历到最后
  10.     for (inner = outer + 1; inner <= len; inner++) {
  11.       if (arr[inner] < arr[min]) {
  12.         min = inner
  13.       }
  14.     }
  15.     // 放在外面为了减少交换次数
  16.     if (outer !== min) {
  17.       [arr[outer], arr[min]] = [arr[min], arr[outer]];
  18.     }
  19.   }
  20. }

选择排序的时间复杂度是 选择排序 - 图1