前端基础算法--选择排序

300 阅读1分钟

上面讲到的二分查找虽然性能很好,当时有一个必要的条件就是这个list需要是一个有序数组,否则使用二分查找则是不成立的。所以,对于一个无序的数组,我们首先就是需要把它重新排序。选择排序就是其中一种。

选择排序的原理是从数组中选出一个最大(小)的数,放在另一个数组的开始,然后从剩余数组中继续选择最大(小)的数进行操作,如此重复,直到数组重组。

// 选择排序
function selectSort(list){
  if (!Array.isArray(list)) return list

  // 定义一个数组存放排序后的数组
  const arr = [];
  
  for (let i = list.length - 1; i >= 0; i--) {
    const smallestIndex = findSmallest(list)
    arr.push(list.splice(smallestIndex, 1)[0])
  }
  
  return arr
}

// 寻找最小的数
function findSmallest(list){
  let smallest = list[0]
  let smallestIndex = 0

  for (let i = 0; i < list.length; i++) {
    const ele = list[i];
    if (ele < smallest) {
      smallest = ele
      smallestIndex = i
    }
  }
  return smallestIndex
}