排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序的方法，通俗点来讲，就是如何使得一组数据按照要求重新排列的方法。

算法分类

排序算法可以分为内部排序和外部排序。

内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，内存不能一次性容纳全部的排序记录，在排序过程中需要访问外存(如：磁盘)。

常见的内部排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。 排序算法入门 - 图1

算法复杂度

关于时间和空间复杂度的更多了解请戳这里

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

时间复杂度是指一个算法执行所耗费的时间。常见的时间复杂度有：

  • 常数阶：O(1)
  • 对数阶：O(log2n) (以2为底n的对数，下同)
  • 线性阶：O(n)
  • 线性对数阶：O(nlog2n)
  • 平方阶：O(n^2)
  • 立方阶：O(n^3)
  • k次方阶：O(n^k)
  • 指数阶：O(2^n)

由小到大依次为：Ο(1) ＜ Ο(logn) ＜ Ο(n) ＜ Ο(nlogn) ＜ Ο(n) ＜ Ο(n) ＜ … ＜ Ο(2) ＜ Ο(n!)

空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间的度量。
记作：S(n)=O(f(n))

算法执行期间所需要的存储空间包括3个部分：

  • 算法程序所占的空间；
  • 输入的初始数据所占的存储空间；
  • 算法执行过程中所需要的额外空间。

算法稳定性

排序算法的稳定性，通俗的讲就是能保证在排序前，两个相等的数在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。简单的理解就是，如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。

冒泡排序、插入排序、归并排序 和 基数排序是稳定的排序算法，而 选择排序、快速排序、希尔排序、堆排序是不稳定的算法。

简要比较

image.png
名词解释：

  • n：数据规模
  • k：”桶”的个数
  • In-place：占用常数内存，不占用额外内存
  • Out-place：占用额外内存
  • 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

本系列算法整理参考：
https://github.com/damonare/Sorts
https://github.com/hustcc/JS-Sorting-Algorithm
https://www.cnblogs.com/onepixel/articles/7674659.html