深入理解JS实现快速排序和去重

1.快速排序

快速排序是一种快速并且高效的排序算法。下面是快速排序的步骤：

1. 选择数组中的中心元素作为基准点（pivot）
2. 将所有小于基准点的元素移到基准点的左侧，所有大于基准点的元素移到基准点的右侧
3. 对左右两个子数组递归执行步骤1和步骤2，直到子数组长度为1或0

快速排序可以用以下的JavaScript代码来实现：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [], right = [];

  for (let i = 0; i < arr.length; i++) {
    if (i === Math.floor(arr.length / 2)) {
      continue;
    }
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat(pivot, quickSort(right));
}

这个算法的时间复杂度为O(n log n)，其中n是数组的长度。

快速排序的另一种实现方式是in-place sort。这种方法使用交换而不是新建数组来移动元素。下面是in-place sort的JavaScript代码：

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) {
    return;
  }

  const pivot = arr[Math.floor((left + right) / 2)];
  const index = partition(arr, left, right, pivot);

  quickSortInPlace(arr, left, index - 1);
  quickSortInPlace(arr, index, right);
}

function partition(arr, left, right, pivot) {
  while (left <= right) {
    while (arr[left] < pivot) {
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }
    if (left <= right) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
      left++;
      right--;
    }
  }
  return left;
}

这个算法同样是O(n log n)的时间复杂度。但是由于使用了交换操作，它比第一个算法更快，尤其是在处理大型数组时。

2.去重

在JavaScript中，可以使用Set对象来进行去重操作。下面是Set的JavaScript代码示例：

const arr = [1, 2, 3, 2, 1, 4, 5];
const set = new Set(arr);
const deduplicatedArr = Array.from(set);

这个算法的时间复杂度为O(n)，其中n是数组的长度。它比其他去重算法更快。别忘了，如果您需要支持IE11及以下版本，Set对象是不支持的，需要使用其他的去重方法。