1、冒泡排序

算法描述：

每轮循环把最重（取决于你对重的定义）的元素下沉到有序片段的前一位，无序数据片段规模递减 1，有序数据片段规模递增 1，直到所有的元素都有序则完成排序。

排序过程：

算法实现：

/**
 * 对数组进行冒泡排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function bubbleSort(arr) {
  let temp = null;
  // 外层循环变量i 用于控制参与排序数据的规模
  for (let i = arr.length - 1; i >= 0; i--) {
    // 定义标记，用于判断本轮是否参与交换
    let flag = true;
    // 内层循环用于把最“重”的元素下沉至非有序片段的最后一位
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        // 如果交换了元素，还需要设置标记，若数组已经有序，可以提前终止排序，便于提升性能
        flag = false;
      }
    }
    // 如果说没有参与交换，则认为数组已经有序，则可以完成排序
    if (flag) {
      break;
    }
  }
}
复制代码

平均算法时间复杂度：O(N²)，最好: O(N),已经符合预期有序的片段，无需进行交换。最坏: O(N²)

2、选择排序

算法描述：

从无序片段中找到最值所在的位置，将无序片段的第一个元素与最值元素进行交换（若第一个元素就是最值元素则不交换），有序片段规模递增 1，无序片段规模递减 1，直到所有元素有序则完成排序。

排序过程：

算法实现：

/**
 * 对数组进行选择排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function selectionSort(arr) {
  let temp = null;
  for (let i = 0; i < arr.length; i++) {
    // 假设无序片段的第一个元素是最值，从后面的序列中找一个最值与其交换
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[i]) {
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
      }
    }
  }
}
复制代码

平均算法时间复杂度：O(N²)，最好: O(N)，已经符合预期有序的片段，无需进行交换（和冒泡排序一致），最坏: O(N²)。

3、插入排序

算法描述：

取出从无序序列中的第一个元素，有序片段的规模加 1，在有序片段中找到该元素合适的插入位置进行插入，无序片段的规模减 1，直到无序片段长度为 0 则完成排序。

排序过程：

算法实现：

/**
 * 对数组进行插入排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function insertionSort(arr) {
  // 默认认为第一个元素已经有序
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    let cur = arr[i];
    //向前找合适的插入位置，退出条件有两种可能，1、找到了合适的插入位置；2、找到了头了
    while (j > 0 && arr[j - 1] > cur) {
      // 在每次查找插入位置的时候，都将当前元素向后挪一位。
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = cur;
  }
}
复制代码

平均算法时间复杂度：O(N²)，最好: O(N),已经符合预期有序的片段，直接插入。最坏: O(N²) 如：已按降序排序序列需要变成升序，每次都要移动到最前面。

4、希尔排序

算法描述：

希尔排序的思路是消除数组中的逆序对，根据一定的规则选取增量序列D(k)·D(k-1)·D(k-2)···1，增量序列的最后一项必须是 1,分别以对 D(k)至 1 为间距对数组进行插入排序(因为采取了对 D(k-1)为间距的插入排序之后并不会使得 D(k)为间距进行插入排序之后的结果变坏这是希尔排序的理论基础)，此刻数组会变得大致有序，最后再进行一次（间距 D 为 1）插入排序，从而使得数组有序。

排序过程：

算法实现：

/**
 * 对数组进行希尔排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function shellSort(arr) {
  // 选取 N/2->N/4->N/8->···->1的增量序列
  for (let D = Math.floor(arr.length / 2); D >= 1; D = Math.floor(D / 2)) {
    // 以间距D对数组进行插入排序
    for (let i = D; i < arr.length; i++) {
      let cur = arr[i];
      let j = i;
      while (j >= D && arr[j - D] > cur) {
        arr[j] = arr[j - D];
        j -= D;
      }
      arr[j] = cur;
    }
  }
}
复制代码

可以看出，希尔排序是对插入排序的改进，希尔排序的算法复杂度取决于你选择的增量序列的好坏，有兴趣的同学可以自己查阅关于增量序列的知识点。

平均算法复杂度: O(N\*logN)，最坏： O(N²)

5、快速排序

算法描述：

若数组片段的长度大于 1，则随机从数组片段中取出一个元素作为主元(pivot)，将数组分为两份 A,B，这个位置之前的为一份(A)，这个位置之后的为一份(B)，将 A 中所有比 pivot 大的元素全部放到 B 中，将 B 中比 pivot 小的元素全部放大 A 中，然后分别对数组片段 A 和 B 分别重复这个过程，直到所有的元素都有序即完成排序。

排序过程：

算法实现：

/**
 * 对数组片段进行快速排序
 * @param {Array<number>} arr 需要进行排序的数组
 * @param {number} left 待排序数组片段的开始索引
 * @param {number} right 待排序数组片段的结束索引
 */
function _quickSort(arr, left, right) {
  // 如果数组片段的长度小于或者等于1，无需进行排序
  if (left >= right) {
    return;
  }
  // 随机取一个元素作为主元
  let pivot = arr[left];
  let i = left;
  let j = right;
  while (i < j) {
    // 从数组片段右侧找比主元小的元素
    while (i < j && arr[j] > pivot) {
      j--;
    }
    // 说明此刻已经找到了比主元小的元素
    if (i < j) {
      arr[i] = arr[j];
      // 缩小规模
      i++;
    }
    // 从数组片段左侧找比主元大的元素
    while (i < j && arr[i] < pivot) {
      i++;
    }
    // 说明找到了比主元大的元素
    if (i < j) {
      arr[j] = arr[i];
      j--;
    }
  }
  // 当退出循环的时候，i == j, 此刻这个位置之前所有的元素都比主元小，这个位置之后的所有元素都比主元大，这个位置就是我们存放主元的位置
  arr[i] = pivot;
  // 递归的对左半部分元素进行快速排序
  _quickSort(arr, left, i - 1);
  // 递归的对右半部分元素进行快速排序
  _quickSort(arr, i + 1, right);
}

/**
 * 对数组进行快速排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function quickSort(arr) {
  Array.isArray(arr) && _quickSort(arr, 0, arr.length - 1);
}
复制代码

快速排序是不稳定的排序算法

平均算法时间复杂度：O(N\*logN),最坏：O(N²)

6、归并排序

算法描述：首先将数组划分为若干个片段，然后不断的合并两个有序片段，直到这些片段最终合并成整个数组。

排序过程：

算法实现：

/**
 * 对数组片段进行合并
 * @param {Array<number>} arr 需要进行合并的数组片段
 * @param {number} leftStart 待合并数组片段1的开始索引
 * @param {number} rightStart 待合并数组片段2的开始索引
 * @param {number} rightEnd 待合并数组片段2的结束索引
 * @param {Array<number>} tempArr 临时数组，用于记录合并有序序列
 */
function _merge(arr, leftStart, rightStart, rightEnd, tempArr) {
  // 计算出序列的总长度，用于日后将临时数组中的数据导入到数组中
  let length = rightEnd - leftStart + 1;
  // 计算出序列1结束的位置
  let leftEnd = rightStart - 1;
  // 记录序列的开始位置
  let pos = leftStart;
  while (leftStart <= leftEnd && rightStart <= rightEnd) {
    // 将数组中的元素按特定的规则复制到临时数组里面去
    if (arr[leftStart] >= arr[rightStart]) {
      tempArr[pos++] = arr[rightStart++];
    } else {
      tempArr[pos++] = arr[leftStart++];
    }
  }

  // 两个while不可能同时成立，只拷贝较长的部分
  while (leftStart <= leftEnd) {
    tempArr[pos++] = arr[leftStart++];
  }

  while (rightStart <= rightEnd) {
    tempArr[pos++] = arr[rightStart++];
  }

  // 因为最后合并完成之后pos指向的是最后一个元素的下一位，因此，需要将其减1
  for (let i = pos - 1, k = 0; k < length; k++, i--) {
    // 将临时数组的数据导入到真实数组里面去
    arr[i] = tempArr[i];
  }
}

/**
 * 对数组片段进行归并排序
 * @param {Array<number>} arr 需要进行排序的数组
 * @param {number} left 待排序数组片段的开始索引
 * @param {number} right 待排序数组片段的结束索引
 */
function _mergeSort(arr, left, right) {
  if (left >= right) {
    return;
  }
  let center = Math.floor((left + right) / 2);
  let tempArr = [];
  // 递归的对左半部分进行归并排序
  _mergeSort(arr, left, center);
  // 递归的对右半部分进行归并排序
  _mergeSort(arr, center + 1, right);
  // 合并两个有序数组
  _merge(arr, left, center + 1, right, tempArr);
}

/**
 * 对数组进行归并排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function mergeSort(arr) {
  Array.isArray(arr) && _mergeSort(arr, 0, arr.length - 1);
}
复制代码

归并排序是稳定的排序算法，⭐️需要注意的一点就是，我们在实现归并排序的过程中，对于merge方法，由外界传入临时数组比在merge方法内部申明数组要好，因为如果是外界传入数组的话，我们申请和销毁数组只有一次，而如果在merge函数内部处理的话，会变成很多次的申请和销毁数组，降低算法的效率。

平均算法时间复杂度: O(N\*logN)，空间复杂度: O(N)

归并排序的缺点就是因为有额外的空间复杂度.

7、堆排序

算法描述：将数组片段在线性的时间内调整成最大（小）堆，取出堆顶的元素和数组片段的最后一个元素进行交换，再将剩余的元素调整成最大（小）堆，重复这个操作，直到数组片段为空则完成排序。

排序过程：

算法实现：

/**
 * 将长度为length的数组片段以p为根节点构建最大堆
 * @param {Array<number>} arr 需要进行排序的数组
 * @param {number} p 根节点
 * @param {number} 数组片段的长度
 */
function percDown(arr, p, length) {
  let temp = arr[p];
  let child, parent;
  // 从p节点开始，如果parent*2等于length的话，说明堆已经越界，无需进行循环
  for (parent = p; parent * 2 < length; parent = child) {
    // 找到左儿子节点所在的索引
    child = parent * 2;
    // 右儿子存在,并且右儿子比左儿子大，则取右儿子
    if (child + 1 < length && arr[child] < arr[child + 1]) {
      child++;
    }
    // 如果待插入的值比当前这个位置大或者相等，则说明这个位置就是可以插入的位置,不能再继续下滤了，因此退出循环
    if (temp >= arr[child]) {
      break;
    } else {
      // 把大的值向上提
      arr[parent] = arr[child];
    }
    // 节点下滤
  }
  // 把元素放在合适的位置
  arr[parent] = temp;
}

/**
 * 对数组进行堆排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function heapSort(arr) {
  // 因为在没有哨兵时，对于父节点为i的节点，其左右儿子分别是 2i+1, 2i+2，那我们可以根据最后一个元素算出，最后一个元素的父节点是 Math.floor(arr.length / 2)

  // 从最后一个元素的父元素开始，在线性的时间内将数组调整成最大堆,
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
    percDown(arr, i, arr.length);
  }
  for (let i = arr.length - 1; i >= 0; i--) {
    // 取出堆顶的第一个元素
    let temp = arr[0];
    // 将无序片段最后一个元素交换到堆顶
    arr[0] = arr[i];
    arr[i] = temp;
    // 继续将长度为i的元素片段，以0为根节点，调整成最大堆
    percDown(arr, 0, i);
    // 最后无序片段的规模递减
  }
}
复制代码

定理: 堆排序处理 N 个不同元素的随机排列的平均比较次数是 2N*logN-O(N*log(logN))

堆排序的复杂度可以写成 O(N\*logN)，而且比这个复杂度要比 O(N\*logN)略好一些。

平均算法复杂度：O(N\*logN)

总结

另外，排序算法在实现上有一些要求：

1、接口统一，均只接受一个数组作为参数；

2、不改变数组的引用地址，也就是说函数的执行结果仅体现在对数组管理的内存空间的修改，不返回任何内容。

3、原地排序，一般情况下不会有新的内存空间的占用或者内存空间的开辟（归并排序除外）。

本文中所有的动图来源于本文，若侵权请联系作者删除。

本文重点不对堆进行介绍，对于堆的相关知识点有疑惑的同学可以参考笔者之前的文章

由于笔者水平有限，写作过程中难免出现错误，若有纰漏，请各位读者指正，请联系作者本人，邮箱404189928@qq.com，你们的意见将会帮助我更好的进步。本文乃作者原创，若转载请联系作者本人。