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

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

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

算法原理

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

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 更新了测试用例，此题用选择排序会出现超时，但是算法思想不变即可