JS 选择排序实现教程：原理、代码与应用详解

今天 9508阅读

引言

在计算机科学领域，排序算法是一项基础且重要的技能。排序算法能够将一组无序的数据按照特定的顺序（如升序或降序）重新排列，方便后续的数据处理和分析。选择排序（Selection Sort）是众多排序算法中的一种，它以其简单易懂的原理和实现方式，成为学习排序算法的入门之选。本文将详细介绍选择排序的原理、JavaScript 实现方法以及其应用场景。

选择排序的原理

选择排序的核心思想是每一轮从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

具体步骤如下：

JS 选择排序实现教程：原理、代码与应用详解

假设数组长度为 n，从第 0 个元素开始，遍历整个数组，找到最小的元素。
将找到的最小元素与第 0 个元素交换位置。
从第 1 个元素开始，重复步骤 1 和 2，直到遍历完整个数组。

JavaScript 实现选择排序

下面是使用 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 unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray);

代码解释

外层循环：for (let i = 0; i < n - 1; i++) 控制排序的轮数，每一轮确定一个最小元素的位置。
内层循环：for (let j = i + 1; j < n; j++) 用于在剩余未排序的元素中找到最小元素的索引。
交换元素：使用解构赋值 [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] 交换当前元素和最小元素的位置。

选择排序的复杂度分析

时间复杂度

选择排序的时间复杂度为 $O(n^2)$，其中 $n$ 是数组的长度。这是因为对于长度为 $n$ 的数组，需要进行 $n - 1$ 轮排序，每一轮需要遍历剩余的元素，因此总的比较次数为 $(n - 1) + (n - 2) + \cdots + 1 = \frac{n(n - 1)}{2}$，时间复杂度为 $O(n^2)$。