数组排序

十大经典排序算法

冒泡排序

1. 从零开始依次比较相邻的两个元素，如果顺序错误就调换顺序，这样没一轮循环都可以使最大的元素上升到数组的末尾，像冒泡一样。
2. 经过数组长度次数的循环就可以完成全部元素的冒泡。
3. 注意：每一次冒泡完成最大的元素都会上升到数组的末尾，所以下一次冒泡可以缩减一次冒泡。

时间复杂度为：O(n^2)

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

选择排序

1. 从头开始循环数组找出最小元素
2. 将最小元素和起始元素调换位置
3. 从下一个位置继续重复 1 和 2

时间复杂度为：O(n^2)

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

插入排序

1. 从第一个元素开始，认为第一个元素是已经排序过的了
2. 取出下一个元素，在已排序的元素中从后向前扫描逐个比较
3. 如果被比较元素大于选取元素，则将被比较元素后移
4. 重复步骤三，直到被比较元素小于选取元素或扫描到边界
5. 将选取元素插入当前位置
6. 重复步骤 2-5

时间复杂度为：O(n^2)

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let insertionIndex = i - 1;
    while (insertionIndex >= 0 && current < arr[insertionIndex]) {
      arr[insertionIndex + 1] = arr[insertionIndex];
      insertionIndex--;
    }
    arr[insertionIndex + 1] = current;
  }
  return arr;
}

快速排序

快排是一种分治（Divide and Conquer）算法

1. 选取一个元素作为 pivot（基准点）作为基准数，基准点可以是任何位置，通常选择首尾元素。
2. 遍历数组，将小于基准数的元素放到左侧，大于基准数的元素放到右侧，将数组切分为两个子数组。
3. 对分隔的数组递归执行步骤 2，直至子数组长度小于等于 1 为止。

平均时间复杂度为：O(n*logN)

function quickSort(arr, start, end) {
  start = typeof start === "number" ? start : 0;
  end = typeof end === "number" ? end : arr.length - 1;

  if (start < end) {
    const politIndex = partition(arr, start, end);
    quickSort(arr, start, politIndex - 1);
    quickSort(arr, politIndex + 1, end);
  }
  return arr;
}

// 分隔元素并返回分割点位置
function partition(arr, start, end) {
  // 基准元素位置
  const pivotIndex = start;
  // 基准元素值
  const pivotValue = arr[pivotIndex];

  let index = pivotIndex + 1;
  // 已验证元素位置，默认认为基准元素为已验证元素
  for (var i = index; i <= end; i++) {
    if (arr[i] < pivotValue) {
      // 满足条件后将当前元素和基准元素互换位置
      swap(arr, i, index);
      index++;
    }
  }
  // 将最后一个已验证元素和基准元素互换位置
  swap(arr, pivotIndex, index - 1);
  return index - 1;
}

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

归并排序

1. 首先将一个数组分为两数组，然后对拆分的数组进行递归拆分，直到只剩一个元素为止
2. 然后将每个子数组中的元素排序然后合并，递归直至完成

时间复杂度为：O(n*logN)

function mergeSort(arr) {
  const size = arr.length;
  if (size < 2) {
    return arr;
  }
  const middle = Math.floor(size / 2);
  const  left = arr.slice(0, middle);
  const  right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];

  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  while (left.length) {
    result.push(left.shift());
  }

  while (right.length) {
    result.push(right.shift());
  }

  return result;
}