JS实现常见的查找、排序、去重算法示例

JS实现常见的查找、排序、去重算法示例

在 JavaScript 中，常见的算法题目也非常多，其中最常见的算法大致可以分为三类，即查找、排序和去重。在这里将对这三个方面中比较常用的算法进行一一解析，以期能够帮助大家更好的理解和掌握这些算法的使用。

一、查找

1. 二分查找

在排序好的数组中查找一个值，如何快速地找到这个值呢？这时候可以使用二分查找算法。它的原理就是先找到数组的中间位置，将待查找值与中间值比较，如果中间值等于待查找值，则查找成功，否则，如果中间值大于待查找值，则继续在低半区间查找，否则，在高半区间查找。不断重复以上步骤，直到找出目标数据。

function binarySearch(arr, target) {
  let low = 0,
      high = arr.length - 1;
  while(low <= high) {
    const mid = Math.floor((low + high) / 2);
    if(arr[mid] === target) {
        return mid;
    } else if(arr[mid] > target) {
        high = mid - 1;
    } else {
        low = mid + 1;
    }
  }
  return -1;
}

2. 线性查找

线性查找的思想是从数组的第一个元素开始，一直到数组的最后一个元素，逐个比较，直到找到目标值或者已经查找了整个数组。因此，它还称为顺序查找。

function linearSearch(arr, target) {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === target) {
        return i;
    }
  }
  return -1;
}

二、排序

1. 快速排序

快速排序是一种基于分治的排序算法，它将一个数组分为两个子数组，然后递归地将子数组排序。每次递归将位置在中间的值称为基准值，通过比较其他元素和基准值的大小关系，把小于等于基准值的元素放到基准值的左边，把大于基准值的元素放到基准值的右边，从而达到排序的目的。

function quickSort(arr) {
  if(arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];
  for(let i = 1; i < arr.length; i++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

2. 冒泡排序

冒泡排序是一种交换排序算法，它的原理就是不断地遍历要排序的元素，每一次遍历都将相邻的两个元素相互比较，如果发现他们两个位置不合适，就将他们交换位置。直到整个数组变得有序。

function bubbleSort(arr) {
  for(let i = 0; i < arr.length - 1; i++) {
    for(let j = 0; j < arr.length - 1 - i; j++) {
      if(arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}

三、去重

1. ES6 Set

ES6 中新增的 Set 类型能够帮助我们轻松地完成数组去重的任务。它是一种无序、不重复元素的集合，通过使用 Set，我们可以将数组转换为 Set，再将 Set 转化为数组，并完成去重的任务。

const arr = [1, 2, 3, 2, 1];
const uniqueArr = [...new Set(arr)];
console.log(uniqueArr); // [1, 2, 3]

2. 双重循环去重

双重循环的方式是最常见的一种数组去重方法，原理就是使用双重循环，将要去重的数组中的每个元素拿出来依次与其他元素比较，如果找到相同的值，则将该值从数组中去掉。

function uniqueArr(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[i] === arr[j]) {
        arr.splice(j, 1);
        j--;
      }
    }
  }
  return arr;
}

以上就是常见查找、排序、去重算法的实现示例，希望能够对大家有所帮助。