【算法篇】选择排序算法JavaScript版

选择排序算法：原理与最优实现

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是在未排序的序列中找到最小（或最大）的元素，存放到已排序序列的末尾，然后再从未排序的序列中找到最小（或最大）的元素，存放到已排序序列的末尾，直到所有元素均排序完毕。

选择排序算法的原理

选择排序算法的基本步骤如下：

1. 从未排序的序列中找到最小（或最大）的元素，将其存放在已排序序列的起始位置。
2. 从未排序的序列中找到最小（或最大）的元素，将其存放在已排序序列的末尾。
3. 重复步骤2，直到所有元素均排序完毕。

选择排序的时间复杂度为O(n²)，其中n表示数组的长度。由于它在每轮迭代中都需要寻找最小（或最大）的元素，因此它不适合处理大规模数据。然而，对于小规模数据或者要求简单实现的场景，选择排序算法仍然是一个不错的选择。

选择排序算法的实现

以下是使用JavaScript实现的选择排序算法示例：

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

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // 在未排序的序列中找到最小值的索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // 将找到的最小值与已排序序列的末尾元素交换
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// 示例用法
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // 输出：[11, 12, 22, 25, 34, 64, 90]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在这个实现中，我们使用了两个嵌套循环。外层循环负责控制排序的轮数，内层循环负责在未排序的序列中寻找最小值的索引。在每一轮排序中，我们将找到的最小值与已排序序列的末尾元素交换。这样可以确保已排序序列始终包含最小的元素。

总结

这个实现遵循了选择排序算法的基本原理，并且没有引入额外的复杂度。在实际应用中，虽然选择排序算法不如快速排序、归并排序等高效，但它的实现简单，易于理解，适用于小规模数据或要求简单实现的场景。