前端网站开发框架,沈阳大型网站设计公司,湖南建筑一体化平台,龙华网站建设全包【数据结构学习笔记】选择排序
参考电子书#xff1a;排序算法精讲
算法原理
首先在未排序序列中找到最小#xff08;大#xff09;元素#xff0c;存放到排序序列的起始位置#xff0c;然后#xff0c;再从剩余未排序元素中继续寻找最小#xff08;大#xff09;元…【数据结构学习笔记】选择排序
参考电子书排序算法精讲
算法原理
首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕
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 更新了测试用例此题用选择排序会出现超时但是算法思想不变即可
