排序算法集锦系列之——选择

表现最稳定的算法之一, 该算法的基本思想是: 选择样本序列的minimum(maximum)元素, 依次排列在已排列序列的末尾

前置

---

时间复杂度

O(n ^ 2)

空间复杂度

O(1)

思路

---

思路一

• pos记录最小or最大值下标
• 外层遍历记录初始pos
• 内层比对更新pos
• 外层值交换

function selectionSort(arr) {
  const len = arr.length;

  for(let i = 0; i < len - 1; i++) {
    let pos = i;
    for(let j = i + 1; j < len; j++) {
      arr[j] < arr[pos] && (pos = j);
    }
    [arr[i], arr[pos]] = [arr[pos], arr[j]];
  }

  return arr;
}