重拾十大经典“排序算法”-上篇

最近在工作中偶然间涉及到数据库的存储和访问，数据库里存放着员工的指纹、年龄以及姓名等信息，当然指纹是通过加密存储的。目前需要对员工的年龄、学历、工作年限等进行排序，如果只有几十个上百个样本，应该不会那么麻烦；关键这是几万名员工的数据，这个量很大，马虎不得。悄悄的告诉你，别惹我，我懂得删库跑路哦。

脑海中对排序的记忆有点模糊，只对「归并排序」印较为深刻，为了加深理解，重拾「数据结构与算法」，并总结了一下常用的十大经典排序算法，由于平台为，因此代码全部用实现，全部源码均编译测试成功。

排序算法在程序猿的编程生涯中虽然用的不多，但是作为基本功，还是需要好好掌握一下。排序算法是「数据结构与算法」中最基本的算法，它分为「内部排序」和「外部排序」；「内部排序」一般在内存中实现；当数据量很大时，内存有限，不能将所有的数据都放到内存中来，这个时候必须使用「外部排序」。

先看一张图，对常用算法的时间复杂度做个比较：

这里的「稳定」是指当排序后两个相等键值的顺序和排序之前的顺序相同；

n:代表数据规模及数据量大小

k:桶的个数

In-place:不占用额外内存，只占用常数内存

Out-place:占用额外内存

本篇作为「重拾十大经典排序算法」的上篇，先深入的讲解五种排序算法，其中包括「冒泡排序」「选择排序」「插入排序」「希尔排序」「归并排序」。

1

冒泡排序

冒泡排序是排序算法中较为简单的一种，英文称为它遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序。

如果有n个数据，那么需要的比较次数，所以当数据量很大时，冒泡算法的效率并不高。

当输入的数据是反序时，花的时间最长，当输入的数据是正序时，时间最短。

平均时间复杂度：

空间复杂度：O(1)

动态演示：

代码：

新建代码文件将以上代码写入，下编译：

测试：

输出结果：

以下的编译方法和测试方法和这里一样，所以下面不在重复编译和测试的说明。

2

选择排序

选择排序简单直观，英文称为先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。很显然，选择排序也是一个费时的排序算法，无论什么数据，都需要的时间复杂度，不适宜大量数据的排序。

平均时间复杂度：

空间复杂度：O(1)

动态演示：

代码：

3

插入排序

插入排序英文称为它通过构建有序序列，对于未排序的数据序列，在已排序序列中从后向前扫描，找到相应的位置并插入，类似打扑克牌时的码牌。插入排序有一种优化的算法，可以进行拆半插入。

基本思路是先将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；然后从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，直到所有数据都完成排序；如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

平均时间复杂度：

空间复杂度：O(1)

动态演示：

代码：

4

希尔排序

希尔排序也称递减增量排序，是插入排序的一种改进版本，英文称为，效率虽高，但它是一种不稳定的排序算法。

插入排序在对几乎已经排好序的数据操作时，效果是非常好的；但是插入排序每次只能移动一位数据，因此插入排序效率比较低。

希尔排序在插入排序的基础上进行了改进，它的基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部数据进行依次直接插入排序。

平均时间复杂度：

空间复杂度：O(1)

假如有这样一组数据，[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果以步长5进行分割，每一列为一组，那么这组数据应该首先分成这样：

之后对每列进行插入排序：

将上述四行数据依序拼接在一起，得到[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]，此时10已经移到正确的顺序了，之后以步长3进行插入排序：

排序之后变为：

最后以步长1进行排序。

步长的选择是希尔排序的关键，只要最终步长为1，任何步长序列都可以。建议最初步长选择为数据长度的一半，直到最终的步长为1。

图解：

代码：

5

归并排序

归并排序英文称为，归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。它首先将数据样本拆分为两个子数据样本, 并分别对它们排序, 最后再将两个子数据样本合并在一起; 拆分后的两个子数据样本序列, 再继续递归的拆分为更小的子数据样本序列, 再分别进行排序, 直到最后数据序列为1，而不再拆分，此时即完成对数据样本的最终排序。

归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种稳定的排序算法.

作为一种典型的分而治之思想的算法应用，归并排序的实现分为两种方法：

自上而下的递归；

自下而上的迭代；

平均时间复杂度：

空间复杂度：O(n)

动态演示：

代码：

参考

wiki

https://github.com/hustcc/JS-Sorting-Algorithm