带你读《图解算法小抄》十四、排序（3）

带你读《图解算法小抄》十四、排序（2）https://developer.aliyun.com/article/1348148?groupCode=tech_library

4）复杂度

5）参考资料

• 维基百科
• YouTube
• 
  

2.选择排序

选择排序（Selection Sort）是一种排序算法，具体来说是一种原地比较排序算法。它的时间复杂度是 O(n^2)，在大型列表上效率低下，并且通常比类似的插入排序表现更差。选择排序以其简单性而闻名，在某些情况下，特别是在辅助内存有限的情况下，它在性能上优于更复杂的算法。

1）选择排序流程

选择排序是一种简单直观的排序算法，它的主要思想是在未排序序列中找到最小（或最大）的元素，然后将其放到已排序序列的末尾。以下是选择排序的步骤：

创建一个函数 selectionSort，它接受一个数组作为参数。

在 selectionSort 函数内部，使用一个循环遍历未排序序列的所有元素，记为 i，并假设当前元素为最小值。

在循环中，再嵌套一个循环用于找到未排序序列中的最小元素的索引，从 i+1 到数组末尾。记最小元素索引为 minIndex。

如果 minIndex 不等于 i，则交换 i 和 minIndex 处的元素，将当前最小元素放到已排序序列的末尾。

循环结束后，数组将按升序排列。

function selectionSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}
// 示例用法：const array = [64, 25, 12, 22, 11];const sortedArray = selectionSort(array);
console.log(sortedArray); // 输出：[11, 12, 22, 25, 64]

selection_sort

带你读《图解算法小抄》十四、排序（4）https://developer.aliyun.com/article/1348146?groupCode=tech_library