当前位置：首页 > article >正文

选择排序js

article 2024/11/8 8:50:09

选择排序（Selection Sort） 是一种简单的排序算法，它的基本思想是每次从未排序的部分选择最小（或最大）元素，将其放到已排序部分的末尾。通过不断选择最小元素并交换位置，逐步完成排序。

选择排序的工作原理

初始状态：假设数组的第一个元素是最小值（或者最大值，根据排序顺序而定）。
遍历剩余元素：从数组的第二个元素开始，依次遍历其余元素。
选择最小值：在遍历过程中，记录当前遍历的最小元素的位置。
交换位置：将最小元素与当前元素交换位置，这样就确保了当前元素位于已排序部分。
重复过程：继续处理未排序的部分，直到整个数组排序完成。

选择排序的时间复杂度

时间复杂度：最坏情况和最好情况都是 O(n²)，因为需要两次循环：
- 外层循环遍历所有元素。
- 内层循环遍历剩下的元素，找出最小（或最大）值。
所以总的时间复杂度是 O(n²)。
空间复杂度：O(1)，选择排序是原地排序算法，交换位置时不需要额外的存储空间。

选择排序的优缺点

优点：
- 实现简单，容易理解。
- 不需要额外的存储空间，空间复杂度为 O(1)。
缺点：
- 效率较低，尤其是对于大量数据，时间复杂度是 O(n²)。
- 无论数据是否已经部分排序，算法始终会遍历所有元素，性能不佳。

选择排序的 JavaScript 实现

下面是使用 JavaScript 实现的选择排序算法：

function selectionSort(arr) {
    let 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;
}

// 测试
let arr = [64, 25, 12, 22, 11];
console.log(selectionSort(arr));  // 输出: [11, 12, 22, 25, 64]

解释

初始化：
- minIndex 是用来记录当前未排序部分最小元素的索引。初始时将其设为当前循环的索引 i。
外层循环：
- 外层循环从第一个元素开始，遍历数组中的每个元素，确保每次找到的最小元素能够被放到已排序部分的末尾。
内层循环：
- 内层循环遍历未排序部分（即从 i + 1 到数组末尾），找到比当前最小元素更小的元素，并更新 minIndex。
交换：
- 如果 minIndex 被更新，说明找到了更小的元素。我们用 swap（交换语句）把 arr[i] 和 arr[minIndex] 的位置互换，确保每轮迭代都将最小元素放到已排序部分的末尾。

选择排序的可视化示例

假设我们有一个数组 [64, 25, 12, 22, 11]：

第一次遍历：
- minIndex = 0（假设最小值是 64）。
- 遍历数组的剩余部分，发现 11 是最小的，将 11 和 64 交换。
- 数组变为 [11, 25, 12, 22, 64]。
第二次遍历：
- minIndex = 1（假设最小值是 25）。
- 遍历数组的剩余部分，发现 12 是最小的，将 12 和 25 交换。
- 数组变为 [11, 12, 25, 22, 64]。
第三次遍历：
- minIndex = 2（假设最小值是 25）。
- 遍历数组的剩余部分，发现 22 是最小的，将 22 和 25 交换。
- 数组变为 [11, 12, 22, 25, 64]。
第四次遍历：
- minIndex = 3（假设最小值是 25）。
- 没有发现比 25 更小的元素，不需要交换，排序完成。