冒泡排序是通过两两比较，不断交换，逐个推进，一轮遍历得到一个最值的方式来排序的。
冒泡排序算法费时的：一是两两比较；二是两两交换。
冒泡排序两两交换的目的就是为了找出最值。但是通过这种方式取得最值代价是很大的，因为每次遍历，都需要很多次的交换才能找到最值，而这些交换操作都是很浪费时间的。
如果能减少交换次数，同时又能找到最值，那么这就是一种改进。可以每次遍历，只选择最值元素进行交换，这样一次遍历只需要进行一次交换即可，避免了其他无价值的交换操作。

选择排序（Selection Sort）：是一种简单的排序算法，也是一种不稳定的排序算法。其实现原理是：每一轮遍历从待排序序列中选出一个最值，将其按顺序存放在已排序序列中；重复此步骤，直到待排序序列中的数据都排序完毕。

选择排序的示例：

假设待排序序列为 5、3、6、1、0，如果采用选择排序对其进行升序排序，则整个排序过程如下所示：

1. 第一轮遍历：在待排序序列 5、3、6、1、0 中找到最小值 0，并将其与 5 进行交换，此时待排序序列为 3、6、1、5，已排序序列为 0。
2. 第二轮遍历：在待排序序列 3、6、1、5 找到最小值 1，并将其与数组的 3 进行交换，此时待排序序列为 6、3、5，已排序序列为 0、1。
3. 第三轮遍历：在待排序序列 6、3、5 中找到最小值 3，并将其与数组的第一位 6 进行交换，此时待排序序列为 6、5，已排序序列为 0、1、3。
4. 第四轮遍历：在待排序序列 6、5 中找到最小值 5，并将其与 6 进行交换，此时待排序序列为 6，已排序序列为 0、1、3、5。
5. 当进行第五轮遍历时，由于待排序序列中仅剩 1 个元素，因此直接将其并入已排序序列中，此时的序列就为已排序好的序列。

选择排序的效率：

选择排序改进了冒泡排序，将交换的次数由 O(n²) 减少到 O(n)，但是比较的次数仍然是 O(n²)。

选择排序的代码实现：

需要两层循环来实现：

1. 外层循环是有 n 个元素就进行 n -1 次内层循环，寻找 n -1 遍最值。
2. 内层循环是通过比较找出最值，然后将其与被遍历数据中的第一位进行交换，也就将其排到了已找到的最值中的最后一位。

   下一次进行内层循环的时候就不需要比较已被找到的最值了，因此内层循环遍历的数据量是依次递减的。

// 选择排序：升序
ArrayList.prototype.selectionSort = function () {
  // 1. 获取列表长度
  var length = this.array.length

  // 2. 外层循环：第一次循环 i = 0，第一次循环 i = 2，直到 i = length - 2，只剩最后一个值的时候就不需要再进行遍历了
  for (var i = 0; i < length - 1 ; i++) {
    // 3. 执行第几次的外层循环，内层循环就从几开始，定义最小值的下标值就为几
    // 每次内层循环都能找到一个最值并将其放置到前端，因此，之后的遍历就不需要再操作已找到的最值了
    var minIndex = i

    // 4. 内层循环：找出最小值
    for (var j = i + 1; j < length; j++) {
      if (this.array[j] < this.array[minIndex]) {
        minIndex = j
      }
    }
    
    // 5. 将最小值与内层循环的第一位的值替换
    this.swap(minIndex, i)
  }
}

// 测试选择排序：
list.selectionSort()
console.log(list.toString()) // 1 2 4 5 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26