JS算法中的排序、数组去重详细概述

排序算法

在JavaScript中，常用的排序算法有冒泡排序、插入排序、选择排序、快速排序等。下面将分别对他们进行介绍。

冒泡排序

冒泡排序是一种稳定的排序算法，它的基本思想是从左到右依次比较相邻两个元素的大小，并且将较大的元素向右移动，较小的元素向左移动。重复这个过程直到没有任何元素需要移动为止。

下面是冒泡排序的JavaScript代码实现：

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

插入排序

插入排序是一种稳定的排序算法，它的基本思想是每次将一个待排序的元素插入到已排好序的序列中的适当位置中。

下面是插入排序的JavaScript代码实现：

function insertionSort(arr) {
  for (let i = 1, len = arr.length; i < len; i++) {
    let j = i - 1;
    let tmp = arr[i];
    while (j >= 0 && arr[j] > tmp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = tmp;
  }
  return arr;
}

选择排序

选择排序是一种不稳定的排序算法，它的基本思想是每次从待排序序列中选择一个最小（或最大）的元素，然后把它移到序列的最前面。

下面是选择排序的JavaScript代码实现：

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

快速排序

快速排序是一种不稳定的排序算法，它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

下面是快速排序的JavaScript代码实现：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

数组去重算法

在JavaScript中，常用的数组去重算法有利用Set、利用for循环的双重遍历、利用indexOf、利用Map等。下面将分别对他们进行介绍。

利用Set实现数组去重

Set是ES6新增的一种数据结构，它类似于数组，但是它的成员是唯一的，这就可以很方便的实现对数组的去重。

下面是利用Set实现数组去重的JavaScript代码：

function unique(arr) {
  return [...new Set(arr)];
}

利用for循环的双重遍历实现数组去重

在for循环内部再嵌套一个for循环，用来和外部的循环进行比较，如果发现有相同的元素，则删除掉内部循环的元素。

下面是利用for循环的双重遍历实现数组去重的JavaScript代码：

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

利用indexOf实现数组去重

使用indexOf方法来查找元素在数组中的位置，如果能够找到，则说明数组中已经存在该元素，需要删除掉。

下面是利用indexOf实现数组去重的JavaScript代码：

function unique(arr) {
  let res = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    if (res.indexOf(arr[i]) === -1) {
      res.push(arr[i]);
    }
  }
  return res;
}

利用Map实现数组去重

利用Map来判断数组中是否有重复元素，如果没有，则将该元素添加到Map中。

下面是利用Map实现数组去重的JavaScript代码：

function unique(arr) {
  let res = [];
  let map = new Map();
  for (let i = 0, len = arr.length; i < len; i++) {
    if (!map.has(arr[i])) {
      map.set(arr[i], true);
      res.push(arr[i]);
    }
  }
  return res;
}

示例说明

示例一：排序算法

我们定义一个数组arr，里面存放着10个无序的整数，现在我们想要将它们进行排序。我们可以使用快速排序这种算法来实现。下面是代码示例：

let arr = [4, 9, 2, 10, 1, 5, 3, 6, 8, 7];
console.log(quickSort(arr));

通过执行这段代码，我们就可以得到一个有序的数组。

示例二：数组去重算法

我们定义一个数组arr，里面存放着一些重复的元素，现在我们想要将它们去重。我们可以使用利用Set来实现数组去重的方法。下面是代码示例：

let arr = [1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9];
console.log(unique(arr));

通过执行这段代码，我们就可以得到一个去重后的数组。