常见排序算法简单实现

About Sort

排序算法可以分为两类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

对于当前的我来讲，非比较类算法算是盲区。还好，比较类算法的确是高频考点。

• 比较类排序算法有：

  • O(n^2): 冒泡、选择、插入、shell(希尔)
  • O(nlogN): 归并、快速、堆排序

• 非比较类排序有：

基数、桶、计数排序

bubble（冒泡）

冒泡 时间复杂度O(n^2)，属于最简单的排序方法之一了。
基本原理：
每一趟外侧循环的目的就是通过比较相邻元素，然后得到当次循环的最值。就像气泡似的，最值会向上冒出。

function sort(arr) {
  for (let i = 0; i < arr.length; i += 1) {
    for (let j = 0; j < arr.length - i - 1; j += 1) {
      if (arr[j] > arr[j + 1]) {
        swapArrItem(arr, j, j + 1);
      }
    }
  }
}
// 交换
function swapArrItem(arr, i1, i2) {
  let temp = arr[i1];
  arr[i1] = arr[i2];
  arr[i2] = temp;
}

selection（选择）

时间复杂度O(n^2)，属于最简单的排序方法之一了。
选择排序其实和冒泡还挺像，但是它没有那么多交换的过程。
核心原理就是：外侧循环表示当前位置，未来会填入剩下元素的最值。那么内层循环要做的事情就是找到这个最值的下标，然后把当前位置的元素和最值下标的元素互换位置。

function sort(arr) {
  for (let i = 0; i < arr.length; i += 1) {
    let min = arr[i];
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j += 1) {
      if (arr[j] < min) {
        minIndex = j;
        min = arr[j];
      }
    }
    if (i !== minIndex) {
      swapArrItem(arr, i, minIndex)
    }
  }
}

insert（插入）

时间复杂度O(n^2)。
插入排序的思路在于，外侧循环相当要决定一个分界点，在这个分界点的一边是已经有序的集合，另一半是待排序的集合。
那么接下来要做的事情就是分界点无序的一边取元素，安置到有序的一端。
外侧循环做的事情就是一次决定分界点的位置，内层循环要做的事情就是用分界点毗邻的无序元素，一个个对比分界点毗邻的有序元素，从而找到自己合适的位置。

function sort(arr) {
  for (let i = 1; i < arr.length; i += 1) {
    const curValue = arr[i];
    let j = i - 1;
    let goIndex = i;
    while (j >= 0) {
      if (curValue < arr[j]) {
        arr[j + 1] = arr[j]
        goIndex = j;
        j -= 1;
      } else {
        break;
      }
    }
    arr[goIndex] = curValue;
  }
}

merge（归并）

时间复杂度是O(logN)。
这个排序算法的思想是，对数组进行分割，当分割成最小单位的时候重新合并成有序数组，然后有序数组之间再重新生成新的有序数组。这个排序算法体现的思想其实是分治。
是一个拆封再拆封，直到拆分成最小单元，然后从最小单元开始合并，直到全部元素合并的一个递归过程。
时间复杂度nlogN，是因为拆分的过程类似二分，这种对半的过程很显然，都是logN。但是在其内部的合并过程的复杂度是n。
下面是最简单的实现了。

function sort(arr) {
  function sliceMerge(array) {
    console.log(array);
    if (array.length === 1) {
      return array;
    }
    // 先分割 分割的逻辑对半砍，这就决定了时间复杂度中肯定有logN
    const midIndex = Math.floor(array.length / 2);
    const leftArr = array.slice(0, midIndex);
    const rightArr = array.slice(midIndex, array.length);
    // 递归调用
    const leftRes = sliceMerge(leftArr);
    const rightRes = sliceMerge(rightArr);
    const merged = [];
    // while的个数决定了时间复杂度中有n
    while (leftRes.length > 0 || rightRes.length > 0) {
      if (leftRes[0] && rightRes[0]) {
        if (leftRes[0] <= rightRes[0]) {
          merged.push(leftRes.shift());
        } else {
          merged.push(rightRes.shift());
        }
      } else if (leftRes[0] && !rightRes[0]) {
        merged.push(leftRes.shift());
      } else {
        merged.push(rightRes.shift());
      }
    }
    return merged;
  }
  const res = sliceMerge(arr);
  // 改变原来数组
  res.forEach((item, index) => {
    arr[index] = item;
  });
}

quick（快速）

快速排序的时间复杂度也是nlogN。
基本思想是，随便在数组中找一个下标，遍历其余元素，将比下标对应的元素大的放在一起，比下标小的放在一起，然后再对两个集合再递归做这样的操作。最终return出[…leftSortRes, tagValue, …rightSortRes] 确定位置的数组。
下面是一个比较简单，但是容易看懂的实现：

function sort(arr) {
  function departSort(array) {
    if (array.length <= 1) {
      return array;
    }
    // 随机找一个位置，为了简单期间就第一个位置了
    const tagIndex = 0;
    const tagValue = array[tagIndex];
    const lessThanArr = []; // 比tag小的集合
    const moreThanArr = []; // 比tag大的集合
    for (let i = 1; i < array.length; i += 1) {
      if (array[i] <= tagValue) {
        lessThanArr.push(array[i]);
      } else {
        moreThanArr.push(array[i]);
      }
    }
    const leftSortRes = departSort(lessThanArr);
    const rightSortRes = departSort(moreThanArr);
    return [...leftSortRes, tagValue, ...rightSortRes];
  }
  const res = departSort(arr);
  // 改变原来数组
  res.forEach((item, index) => {
    arr[index] = item;
  });
}