27、🔥选择排序

算法思路

假设你的计算机存储了很多乐曲。对于每个乐队，你都记录了其作 品被播放的次数。

你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。该如何做呢？
一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。

再次这样做，找出播放次数第二多的乐队。

继续这样做，你将得到一个有序列表。

下面从计算机科学的角度出发，看看这需要多长时间。O(n)时间意味着查看列表中 的每个元素一次。例如，对乐队列表进行简单查找时，意味着每个乐队都要查看一次。
要找出播放次数最多的乐队，必须检查列表中的每个元素。正如你刚才看到的，这需要的时 间为O(n)。因此对于这种时间为O(n)的操作，你需要执行n次。 需要的总时间为 O(n × n)，即O(n2)。

排序算法很有用。你现在可以对如下内容进行排序：

• 电话簿中的人名
• 旅行日期
• 电子邮件（从新到旧）

需要检查的元素数越来越少
随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一 个。既然如此，运行时间还是O(n2)。
并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素 数依次为n -1, n-2, …, 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为O(n × 1/2 × n)。
但大O表示法省略诸如1/2这样的常数，因此简单地写 作O(n × n)或O(n2)。
选择排序是一种灵巧的算法，但其速度不是很快。

代码实现

升序

我们先来实现一个对指定数组[3, 2, 5, 4, 1]从小到大升序排序。

// 求数组中的最小值的下标
const findSmallest = (arr) => {
  let smallestValue = arr[0]
  let smallestIndex = 0
  const len = arr.length
  for (let i = 1; i < len; i++) {
    if (smallestValue > arr[i]) {
      smallestValue = arr[i]
      smallestIndex = i
    }
  }
  return smallestIndex
}
const selectionSort = (arr) => {
  const newArr = []
  while(arr.length){
    const smallIndex = findSmallest(arr)
    newArr.push(arr.splice(smallIndex, 1)[0])
  }
  return newArr
}

非常简单！
接下来我们可以优化一下，让其也可以实现降序排序

升序+降序

/**
 * 
 * @param {*} arr 
 * @param {*} type 1为求最大值，0为求最小值
 * @returns 
 */
const findSpecialIndex = (arr, type) => {
  let specialValue = arr[0]
  let specialIndex = 0
  const len = arr.length
  for (let i = 1; i < len; i++) {
    if (type) {
      if (specialValue < arr[i]) {
        specialValue = arr[i]
        specialIndex = i
      }
    } else {
      if (specialValue > arr[i]) {
        specialValue = arr[i]
        specialIndex = i
      }
    }
  }
  return specialIndex
}
/**
 * 
 * @param {*} arr 
 * @param {*} type 1表示降序， 0表示升序 
 * @returns 
 */
const selectionSort = (arr, type) => {
  const newArr = []
  while (arr.length) {
    const index = findSpecialIndex(arr, type)
    newArr.push(arr.splice(index, 1)[0])
  }
  return newArr
}