时间/空间复杂度
补充：空间复杂度，如果一个函数运行下来，占用的内存是3个字节，那么空间复杂度是O(1)。如果占用的内存字节数跟逻辑处理是线性关系，那么空间复杂度就是O(n)。
总结：时间复杂度，看的是运行次数，空间复杂度，看的是占用的内存。
image.png
冒泡排序
思路：每一轮都两两比较，把其中较大的数放到右边
// 冒泡排序
function bubbleSort(arr) {
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
选择排序
思路：每一轮都会选择中最小的一个数，把这个数放到左边
// 选择排序
function selectSort(arr) {
const len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[i]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
return arr;
}
题目： 922. 按奇偶排序数组 II
思路：首先设定目标数组奇数位和偶数位游标，然后遍历源数组，如果是奇数就放到奇数位游标的位置上，如果是偶数就放到偶数位游标的位置上。
function sortArrayByParity(arr) {
// 进行升序排序
arr.sort((a, b) => a - b);
// 声明一个空数组用来存储奇偶排序后的数组
let r = [];
// 记录奇数，偶数位下标
let odd = 1;
let even = 0;
// 对数组进行遍历
arr.forEach(item => {
if (item % 2 === 1) {
r[odd] = item;
odd += 2;
} else {
r[even] = item;
even += 2;
}
});
return r;
}
题目： 215. 数组中的第K个最大元素
常规做法：先降序排序，然后取第k个元素
function findKthLargest(arr, k) {
return arr.sort((a, b) => b - a)[k - 1];
}
弊端：性能不好，其实没有必要全部都排序好
更好做法：冒泡排序做到第k次
function findKthLargest(arr, k) {
for (let i = arr.length - 1; i > arr.length - 1 - k; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr[arr.length - k];
}
说明：虽然代码量比方法1要多，但是性能提高了
题目：164. 最大间距
常规做法：先降序排序，然后取第k个元素
function maximumGap(arr) {
// 如果长度小于2，返回0
if (arr.length < 2) {
return 0;
}
// 排序
arr.sort();
// 保存相邻元素的最大差值
let max = 0;
let tmp = 0;
for (let i = 0, len = arr.length; i < len - 1; i++) {
tmp = arr[i + 1] - arr[i];
if (tmp > max) {
max = tmp;
}
}
return max;
}
弊端：同时有sort()和for循环，性能不好
更好做法：在冒泡排序的每一轮中取得最大两个元素间的差值
function maximumGap(arr) {
// 如果长度小于2，返回0
if (arr.length < 2) {
return 0;
}
// 保存相邻元素的最大差值
let max = 0;
let tmp = 0;
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
// 从第二轮开始计算差值
if (i < arr.length - 1) {
tmp = arr[i + 1] - arr[i];
}
if (tmp > max) {
max = tmp;
}
}
// 注意还需要跟arr[1] - arr[0]的结果做比较
return Math.max(max, arr[1] - arr[0]);
}
说明：相比常规做法，少做了一次for循环，性能更好
题目：41. 缺失的第一个正数
常规做法：先排序再找缺失的正数
function firstMissingPositive(arr) {
// 过滤掉非正数
arr = arr.filter(item => item > 0);
// 正整数数组是不是空
if (arr.length) {
// 升序，目的：方便从左到右取最小值arr[0]
arr.sort();
// 如果第一个元素不为1，返回1
if (arr[0] !== 1) {
return 1;
} else {
// 从左到右遍历，只要下一个元素和当前元素的差值 >1，返回当前元素的下一个值(+1)
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i + 1] - arr[i] > 1) {
return arr[i] + 1;
}
}
// 如果数组是连续的正数[1,2,3,4,5,6]
return arr.pop() + 1;
}
} else {
return 1;
}
}
弊端：同时有sort()和for循环，性能不好
更好做法：在选择排序的每一轮中找缺失的正数
function firstMissingPositive(arr) {
// 过滤掉非正数
arr = arr.filter(item => item > 0);
let len = arr.length;
// 正整数数组是不是空
if (len) {
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[i]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
// arr[i]是本轮中最小的数
if (i > 0) {
// 当前元素与前一个元素的差值 >1，返回前一个元素的下一个值(+1)
if (arr[i] - arr[i - 1] > 1) {
return arr[i - 1] + 1;
}
} else {
// 如果第一个元素不为1，返回1
if (arr[i] !== 1) {
return 1;
}
}
}
return arr.pop() + 1;
} else {
return 1;
}
}
说明：相比常规做法，少做了一次for循环，性能更好
