【数据结构学习笔记】选择排序

【数据结构学习笔记】选择排序

参考电子书：排序算法精讲

算法原理

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

const nums = [1, 4, 6, 2, 0];

let minIndex;
for (let i = 0; i < nums.length; i++) {
    minIndex = i;
    for (let j = i + 1; j < nums.length; j++) {
        if (nums[j] < nums[minIndex]) {
            minIndex = j;
        }
    }
    const temp = nums[i];
    nums[i] = nums[minIndex];
    nums[minIndex] = temp;
}

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

优化方式

• 当 i = nums.length - 1 时，j = nums.length 直接跳出循环，因此可以跳过

const nums = [1, 4, 6, 2, 0];

let minIndex;
for (let i = 0; i < nums.length - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < nums.length; j++) {
        if (nums[j] < nums[minIndex]) {
            minIndex = j;
        }
    }
    const temp = nums[i];
    nums[i] = nums[minIndex];
    nums[minIndex] = temp;
}

• 如果 minIndex 没有变就跳过交换

const nums = [1, 4, 6, 2, 0];

let minIndex;
let swapped;
for (let i = 0; i < nums.length; i++) {
    minIndex = i;
    swapped = false;
    for (let j = i + 1; j < nums.length - i; j++) {
        if (nums[j] < nums[minIndex]) {
            minIndex = j;
            swapped = true;
        }
    }
    if (!swapped) continue;
    const temp = nums[i];
    nums[i] = nums[minIndex];
    nums[minIndex] = temp;
}

• 记录最小值的同时记录最大值，在排序到中间部分就会有序

const nums = [1, 4, 6, 2, 0];

let minIndex;
let maxIndex;
let swapped;
for (let i = 0; i < nums.length; i++) {
    minIndex = i;
    maxIndex = i;
    swapped = false;
    for (let j = i + 1; j < nums.length - i; j++) {
        if (nums[j] < nums[minIndex]) {
            minIndex = j;
            swapped = true;
        }
        if (nums[j] > nums[maxIndex]) {
            maxIndex = j;
            swapped = true;
        }
    }
    if (!swapped) continue;
    const temp = nums[i];
    nums[i] = nums[minIndex];
    nums[minIndex] = temp;

    if (maxIndex === i) maxIndex = minIndex;
    temp = nums[nums.length - 1 - i];
    nums[nums.length - 1 - i] = nums[maxIndex];
    nums[maxIndex] = temp;
}

相关例题

LC 215.数组中的第 k 个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let maxIndex;
    let maxIndexes = [];

    while(k-- > 0) {
        maxIndex = -1;
        for (let i = 0; i < nums.length; i++) {
            if (maxIndexes.includes(i)) continue;
            if (maxIndex === -1) {
                maxIndex = i;
                continue;
            }
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        maxIndexes.push(maxIndex);
    }
    return nums[maxIndexes[maxIndexes.length - 1]];
};

受限于 Leetcode 更新了测试用例，此题用选择排序会出现超时，但是算法思想不变即可