需要有肌肉记忆的五种排序方法 | 刷题打卡

我心飞翔 分类:javascript

本文正在参与掘金团队号上线活动,点击 查看大厂春招职位

chrome v8 在处理 sort 方法时,使用了插入排序和快排两种方案。当目标数组长度小于 10 时,使用插入排序;反之,使用快排。

所以对我们来说是有必要了解一下这些排序方法的,这些方法有时候也是做其他算法题的基石。

题目描述

给你一个整数数组 nums,请你将该数组升序排列。

示例 1:

输入:nums = [5,2,3,1]

输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

来源:力扣(LeetCode)

链接:leetcode-cn.com/problems/so…

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

冒泡排序

思路

  1. 比较两个相邻的元素,然后根据条件不断的交换位置(重点:不断比较相邻的两个元素)
  2. 每一轮下来最大的或者最小的值就会在末尾了
  3. 执行 n-1 轮这个过程就好了

buddleSort

图片来源:visualgo.net/zh/sorting

题解

function bundleSort (arr) {
  // 一共需要遍历n轮
  for (let i = 0; i < arr.length; i += 1) {
    // 因为每一轮都会把最大的值放到末尾,所以下次遍历的时候,就不用遍历到排序好的下标处了
    // 所以这里用了arr.length - 1 - i
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        const tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
};
 

选择排序

思路

  1. 假设数组的开头是最小值的下标,然后每次遍历的时候更新最小值
    1. 内层循环就是找到每轮中最小的,然后对调位置
    2. 外层循环就是不断重复内层循环的操作,直到所有值排列完毕
  2. 将最小值与当前遍历的数组头部做交换
    1. 每一轮结束都会将最小值放到头部,所以下次遍历的时候要将排序好的排除掉

selectionSort

图片来源:visualgo.net/zh/sorting

题解

function selectSort(arr) {
  // 遍历n轮
  for (let i = 0; i < arr.length; i += 1) {
    // 找到当前数组范围内的最小值的小标
    let minIndex = i;
    for (let j = i; j < arr.length; j += 1) {
      // 找到最小的
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    // 如果最小值下标和头部下标不同就进行交换
    if (minIndex !== i) {
      const tmp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = tmp;
    }
  }
};

 

插入排序

思路

  1. 插入排序就是从数组的第二项开始,与它前面的值进行比较
  2. 如果比前面的值小,就将前一位的值往后挪
  3. 然后继续拿这个值与前面的进行比较,直到遇到比他小的,进行插入

说是插入排序,其实感觉就是暂定一个值,然后不断的与他前面的值进行比较,如果前面的值大,那就挪到下一位(这里的挪其实就是让 arr[i+1] == arr[i]).
直到找到比他小的值或者是下标为 0 的时候就停止,将当前坐标的值更改为我暂定的这个值(这一步就是插入)

insertSort

图片来源:visualgo.net/zh/sorting

题解

function insertSort(arr) {
  for (let i = 1; i < arr.length; i += 1) {
    // 选择一个值与他前面的值进行比较
    let p = i;
    const tmp = arr[p];
    // 遍历在他前面的所有值
    while (p) {
      // 如果选择的这个值要小,就将前面的值后移
      if (tmp < arr[p - 1]) {
        arr[p] = arr[p - 1];
      } else {
        // 否则就跳出循环
        break;
      }
      // 将坐标不断前移比较
      p -= 1;
    }
    arr[p] = tmp;
  }
};
 

归并排序

思路

    1. 找出中点,递归将数组一分为 2,直到数组中被分的只剩一个元素
    1. 新建一个数组,将分好的元素的头部进行比较,按照规则取出队头放入 res 中

题解

function mergeSort(nums) {
// 创建递归函数
const innerSort = (nums) => {
// 递归的出口,数组中剩一个元素的时候返回
if (nums.length === 1) return nums;
/** ================分================*/
// 找中点
const mid = Math.floor(nums.length / 2);
// 分为左半部分
const left = nums.slice(0, mid);
// 分为右半部分
const right = nums.slice(mid, nums.length);
// 递归进行分,在这里分好的是已经执行了下面“合”操作的,所以已经是排序好的数组了
const orderLeft = innerSort(left);
const orderRight = innerSort(right);
/** ================合================*/
// 创建数组进行接收
const res = [];
// 遍历
while (orderLeft.length || orderRight.length) {
// 左右数组都存在值的情况
if (orderLeft.length && orderRight.length) {
// 谁小谁就出队,压入res中
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
} else if (orderLeft.length) {
// 只有左侧有值时就将剩余的值不断压入res中即可
res.push(orderLeft.shift());
} else {
// 只有右侧有值时不断压入res
res.push(orderRight.shift);
}
}
// 返回结果
return res;
};
// 调用函数
return innerSort(nums);
}

复杂度

前面几种的复杂度都比较好分析,归并排序的复杂度我们注意一下:

  • 时间复杂度: O(n*logn)
    • 分: O(logN)
    • 和: O(n)
  • 空间复杂度:O(n) 数组的长度

快速排序

思路

  1. 找到基准点(通常使用数组的开头)
  2. 把基准点后面的值进行与基准值比较,如果比基准小就放入左侧,否则放入右侧
  3. 将左、基准、右侧组合成新数组
  4. 递归执行上面的步骤

题解

function quickSort(nums) {
const innerQuickSort = (arr) => {
// 如果当前数组只要一个值或者没有值,直接返回即可
if (arr.length <= 1) return arr;
// 左侧分区
const left = [];
// 右侧分区
const right = [];
// 基准点
const base = arr[0];
// 从当前数组的第二项开始与基准点进行比较
for (let i = 1; i < arr.length; i += 1) {
// 如果比基准点小,就放入左侧
if (arr[i] < base) {
left.push(arr[i]);
} else {
// 比基准点大,就放入右侧
right.push(arr[i]);
}
}
// 进行递归
const orderLeft = innerQuickSort(left);
const orderRight = innerQuickSort(right);
// 讲排序好的数组组合在一起
return [...orderLeft, base, ...orderRight];
};
return innerQuickSort(nums);
}

总结

排序算法可以说是算法入门的敲门砖了,而且我们日常工作中会有很多涉及到排序的东西,虽然我们已经有了现成的方法可以去调用,但是还是需要知道这下面存在的猫腻,退一万步说如果面试官不让你用现成的你怎么办(狗头保命)

回复

我来回复
  • 暂无回复内容