一、常见排序算法及分类

二、排序算法衡量标准

• 执行效率，即时间复杂度。
• 内存消耗，即空间复杂度。
• 稳定性，即如果数据在排序前，存在比较值相同的数据时，在排序过后它们的相对位置不发生改变。

三、排序算法JS实现

冒泡排序

原理：

• 需要排序的数据，两两对比大小，交换位置，大的会被换到后方。
• 执行第一遍冒泡后，最大的元素会被放置在最后面。
• 反复执行n遍，所有的数据就排好了。

优势：

• 是稳定的排序算法，因为值相等时不会进行交换操作。
• 原地排序不用开辟额外空间，空间复杂度低，仅为O(1)

劣势：

• 时间复杂度高，最坏情况下需要进行O(n2)的比对，不适用于大型数据集
• 交换位置的操作太频繁，会影响cpu执行效率。

实现：

快速排序

原理：快速排序是使用分而治之的方法，将原始数组分为较小的数组。它从数组中取一个值（n）出来，接着遍历剔除了n的剩下的数组，将小于和大于n的数分别存入数组left和right，然后分别合并left、n、right，递归重复此过程最终排列出来。

优势：

• 速度快
• 原地排序，只需要占用O(logn)的栈空间。

劣势：

• 不是稳定的排序算法。
• 分区点的选择有讲究，选择不当时最坏情况会退化为O(n2)。
• 需要把待排序的数组一次性读入到内存里。

实现：

插入排序

原理：将数组分成有序和无序两个部分，排序的时候，我们不断将无序部分的第一个元素插入有序部分。插入时，按照从后往前的顺序，逐一跟有序部分的元素比较，如果比有序元素的数值更小，就进行交换；如果比有序元素的数值更大，就停止比较。

优势：

• 有提前终止循环的情况，如果是面对近似有序的数组，效率奇高。
• 原地排序不用开辟额外空间，空间复杂度低，仅为O(1)
• 没有交换位置的操作执行效率高。
• 是一种稳定的排序算法。

劣势：

• 时间复杂度高，最坏情况下需要进行O(n2)的比对，不适用于大型数据集

实现：

选择排序

原理：

依次选出最小的值，然后将其放在数组中。

优势：

是一种原地排序算法，与冒泡排序相比，交换位置的操作改为了赋值操作，执行效率会提高。

劣势：

• 时间复杂度高，最坏和最好情况都是O(n2)的复杂度。
• 不是稳定的排序算法，因为每次找到最小的值后会进行交换位置的操作。

实现：

归并排序

原理：归并排序是建立在归并操作上的一种有效、稳定的排序算法。是使用分治法的一个典型应用。

优势：

不是原地排序，需要开辟额外的O(n)空间。

劣势：

• 没有最好最坏时间复杂度，任何情况下都是O(nlogn)
• 是一种稳定的排序算法。

实现：

原文链接：https://juejin.cn/post/7407271112995160090