思想

1. 首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。
2. 再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
3. 重復(fù)第二步，直到所有元素均排序完畢。

img

實(shí)現(xiàn)

/*
  選擇排序:
  平均時間復(fù)雜度:O(n2), 最差時間復(fù)雜度:O(n2), 是不穩(wěn)定排序, 需要額外空間O(1) 
 */
function select(array) {
  for (let i = 0; i < array.length -1 ; i++) {
    let minIndex = i
    let min = array[i]
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < min) {
        min = array[j]
        minIndex = j
      }
    }
    if (minIndex != i) {
      array[minIndex] = array[i]
      array[i] = min
    }
  }
}
let array = [101, 34, 119, 1]
select(array)
console.log(array);