之前我们介绍过了在平常经常会遇到的 查找算法,今天我们就在来看看另一类比较常见而且非常重要的算法,那就是『排序算法』,排序算法在所有的算法当中应该算是应用最为广泛的一类算法
基本概念
我们先来看官方定义
假设含有
n
个记录的序列为{ r1, r2 ... rn }
,其相应的关键字分别为{ k1, k2 ... kn }
,需确定1, 2 ... n
的一种排列p1, p2 ... pn
,使其相应的关键字满足kp1 <= kp2 <= ... <= kpn
非递减(或非递增)关系,即使得序列成为一个按关键字有序的序列{ rp1, rp2 ... rpn }
,这样的操作就称为排序
其实简单来说,在排序问题中,通常将数据元素称为记录,显然我们输入的是一个记录集合,排序后输出的也是一个记录集合,所以我们可以将排序看成是线性表的一种操作,排序的依据是关键字之间的大小关系,那么对同一记录集合,针对不同的关键字进行排序,可以得到不同序列
排序的稳定性
假设 ki = kj(1 <= i <= n, 1 <= j <= n, i != j)
,且在排序前的序列中 ri
领先于 rj
(即 i < j
)
- 如果排序后
ri
仍领先于rj
,则称所用的排序方法是稳定的 - 反之,若可能使得排序后的序列中
rj
领先ri
,则称所用的排序方法是不稳定的
排序算法性能
下面我们来看看影响排序算法性能的几个要素,主要有下面三个
- 时间性能,其实内排序主要进行的就是比较和移动,而高效率的内排序算法,应该具有尽可能少的关键字比较次数和尽可能少的记录移动次数
- 辅助空间,优秀的排序算法是不需要太多的辅助空间的
- 算法的复杂性,这里不是指算法的时间复杂度,而是算法本身是否复杂
根据排序过程中涉及的存储器不同,可以将排序方法分为两大类,一类是内部排序,指的是待排序的几率存放在计算机随机存储器中进行的排序过程,另一类的外部排序,指的是排序中要对外存储器进行访问的排序过程(比如与硬盘进行数据交换等)
常见的『快速排序』、『归并排序』、『堆排序』、『冒泡排序』等属于『比较排序』,在排序的最终结果里,元素之间的次序依赖于它们之间的比较,每个数都必须和其他数进行比较,才能确定自己的位置
- 在冒泡排序之类的排序中,问题规模为
n
,又因为需要比较n
次,所以平均时间复杂度为O(n²)
,在归并排序、快速排序 之类的排序中,问题规模通过分治法消减为logn
次,所以时间复杂度平均O(nlogn)
- 比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序,可以说,比较排序适用于一切需要排序的情况
- 计数排序、基数排序、桶排序 则属于非比较排序,非比较排序是通过确定每个元素之前,应该有多少个元素来排序,针对数组
arr
,计算arr[i]
之前有多少个元素,则唯一确定了arr[i]
在排序后数组中的位置
非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决,算法时间复杂度 O(n)
,非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置,所以对数据规模和数据分布有一定的要求,本章我们将会介绍十大经典排序算法,它们之间的区别如下图
其实总结来说,应该根据场合来进行选择使用,因为没有最好的算法,只有最适合的算法,下面我们就一个一个慢慢来进行了解
冒泡排序
冒泡排序算法的原理如下
- 比较相邻的元素,如果第一个比第二个大,就交换它们两个
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,在这一点,最后的元素应该会是最大的数
- 针对所有的元素重复以上的步骤,除了最后一个
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
一句话总结就是,『在未排序列中,选出最值放入已排序列』
我们下面就可以对照着原理来尝试进行实现,如下
1 | // 从当前元素起,向后依次比较每一对相邻元素,若逆序则交换 |
这里需要注意的一点就是在于内层循环,第 i
趟只需要比较 len - i
次即可,但是针对于上面这种算法,如果我们细心观察的话可以发现,是还存在可以优化的空间,因为当数据的顺序排好之后,冒泡算法仍然会继续进行下一轮的比较,直到 arr.length - 1
次,因而后面的比较没有意义的
所以我们可以设置一个标志位,flag
,如果发生了交换 flag
设置为 true
,如果没有交换就设置为 false
,这样当一轮比较结束后如果 flag
仍为 false
,那么我们就可以知道这一轮是没有发生交换的,说明数据的顺序已经排好,没有必要继续进行下去
1 | function sort(arr) { |
对于这种使用 flag
的方式,比较适用于序列当中有部分是已经是排序完成的,比如 arr = [1, 0, 2, 3, 4, 5, 6, 7]
这样的序列
选择排序
选择排序可以算是表现最稳定的排序算法之一,因为无论什么数据进去都是 O(n^2)
的时间复杂度,所以用到它的时候,数据规模越小越好,唯一的好处可能就是不占用额外的内存空间了吧,下面我们来看看它的具体实现原理
- 简单来说就是,对比数组中前一个元素跟后一个元素的大小,如果后面的元素比前面的元素小则用一个变量
k
来记住它的位置,以此类推,等到循环结束的时候,我们就可以找到了最小的那个数的下标了 - 然后进行判断,如果这个元素的下标不是第一个元素的下标,就让第一个元素跟它交换一下值,这样就找到整个数组中最小的数了
- 然后找到数组中第二小的数,让它跟数组中第二个元素交换一下值,以此类推
一句话总结就是,『在未排序列中,选出最值放入已排序列』,也就是下图这样
下面我们来看代码如何实现
1 | function sort(arr) { |
插入排序
插入排序(Insertion sort
)是一种简单直观且稳定的排序算法,如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法插入排序法,插入排序的基本思想是,每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止
如果用现实当中的例子来看的话,就类似与我们的斗地主,在摸排阶段手里的牌都按照从小到大排序,如果每摸一张牌,我们就把它插入合适的位置,使得它比后面位置的牌小,比前面位置的牌大或者相等,这样的一种排序方法就是插入排序,下面我们来看一下插入排序的实现原理
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤
3
,直到找到已排序的元素小于或者等于新元素的位置 - 将新元素插入到该位置后
- 重复执行步骤二到五
一句话总结就是『将未排序列和已排序列做比较』,所以我们可以考虑使用双层循环,外循环控制未排序的元素,内循环控制已排序的元素,将未排序元素设为标杆,与已排序的元素进行比较,小于则交换位置,大于则位置不动,也就是下图这样
下面我们来看代码如何实现
1 | function sort(arr) { |
希尔排序
希尔排序是『插入排序』的一种,又称『缩小增量排序』(Diminishing Increment Sort
),是『直接插入排序』算法的一种更高效的改进版本,希尔排序的原理是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1
时,整个文件恰被分成一组,算法便终止,希尔排序是基于『插入排序』的以下两点性质而提出改进方法的
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
可以如下图所示,假设我们的初始化关键字如下
然后我们将其先分为两组,然后分别对当前数组进行『插入排序』,如下所示
我们以 49
和 13
为起始,对比它们两者直接的大小,小的放左边,大的放右边,然后在比较 38
和 27
,以此类推
在第一趟结束以后,结果是下面这样的
然后我们再将之前的数组再次分割,也就是下面这样
这次我们就以 13,55,38,76
为起始,依次比对,接下来就是 27,04,65
,往后在以此类推
第二趟结束以后,结果是下面这样的
以此类推
最终结果如下
下面我们来看看如何用代码进行实现,其实我们的代码就是在『插入排序』的基础上来进行调整就可以来
1 | function sort(arr) { |
可以发现,我们的主体逻辑没有改变,而是仅仅只添加来一个 gap
变量来进行分组,最主要的变化就是之前的外层循环的判断条件由 i = 1
变成了 i = gap
,内层循环的判断条件由 var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--
变成了 var j = i - gap; j >= 0 && arr [j] > arr[gap + j]; j -= gap
归并排序
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn)
的时间复杂度,代价是需要额外的内存空间,简单来说就是将两个或者两个以上有序表组成一个新的有序表,这个操作就称之为归并,也就是『先递归来分解数列,再合并数列』(分治思想的典型应用)
归并排序(Merge Sort
)就是利用归并的思想实现的排序方法,它的原理是假设初始序列有 n
个记录,则可以看成是 n
个有序的子序列,每个子序列的长度为 1
,然后两两归并,得到 ⌈n / 2⌉
个长度为 2
或 1
的有序子序列,再两两归并,如此重复,直至得到一个长度为 n
的有序序列为止,这种排序方法称为二路归并排序,也就是下图这样的逻辑
简单来说就是分为三个步骤
- 将一个数组拆成
A、B
两个小组,两个小组继续拆,直到每个小组只有一个元素为止 - 按照拆分过程逐步合并小组,由于各小组初始只有一个元素,可以看做小组内部是有序的,合并小组可以被看做是合并两个有序数组的过程
- 对左右两个小数列重复第二步,直至各区间只有一个数
我们以数组 [42, 20, 17, 13, 28, 14, 23, 15]
为例,进行归并排序,模拟排序过程如下
第一步,拆分数组,一共需要拆分三次(logN
)
- 第一次拆成
[42, 20, 17, 13]
和[28, 14, 23, 15]
- 第二次拆成
[42, 20],[17, 13],[28, 14],[23, 15]
- 第三次拆成
[42],[20],[17],[13],[28],[14],[23],[15]
第二步,逐步归并数组,采用合并两个有序数组的方法,每一步其算法复杂度基本接近于 O(n)
- 第一次归并为
[20, 42],[13, 17],[14, 28],[15, 23]
- 第二次归并为
[13, 17, 20, 42]
和[14, 15, 23, 28]
- 第三次归并为
[13, 14, 15, 17, 20, 23, 28, 42]
如下图演示
下面我们来看代码如何实现
1 | function mergeSort(arr) { |
快速排序
关于这个算法的实现方式,网上有很多争议,让我们先抛开争议,先从最为基本的实现方式开始看起,看看这些争议具体体现在什么地方,它的具体实现思路为
- 数列中挑出一个元素,称为基准(基准选择开头,结尾或者中间数都可以)
- 准备两个数组容器,遍历数组,逐个与基数比对,较小的放左边容器,较大的放右边容器
- 递归处理两个容器的元素,并将处理后的数据与基数按大小合并成一个数组,返回
快速排序本质是通过分治策略通过基准值数组拆分成两部分,一部分永远比基准值小,另外一部分永远比基准值大,这时候在继续在拆分的部分中取基准值继续将已经拆分的部分再次拆分成两部分,直到不可在继续拆分下去,这个时候数组的顺序就已经完成了排序操作,所以我们可以得出我们的第一版代码,如下
1 | function sort(arr) { |
运行以后可以发现,是可以达到排序的目的的,我们选择基数为参照,划分数组,分而治之,结果很美好,但是仔细观察后可以发现,它其实是存在着一定问题的,我们慢慢来看
我们发现在函数内定义了额外的两个数组用于存放临时数据,随着递归的次数增多,会定义并存放越来越多的临时数据从而占用了更多的存储空间(增加了空间复杂度),而且如果是比较极端的情况,比如序列是一个从大到小反向排列的序列,而我们选择的基准点又刚好是序列的第一位,那么它的性能就可想而知了,所以这里我们就可以采用一种名为『原地分区』的算法来进行优化,那么什么是原地分区呢?
正如其名,原地分区的算法是借由移动小于等于 pivot
的所有元素到子序列的开头,留下所有大于或等于的元素接在他们后面,在这个过程它也为基准元素找寻最后摆放的位置,也就是它回传的值,它暂时地把基准元素移到子序列的结尾,而不会被前述方式影响到,由于算法只使用交换,因此最后的数列与原先的数列拥有一样的元素,也不会产生临时数组,从而增加空间复杂度
我们用一个示例来说明它的具体操作流程,比如我们要排序的序列是 [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
,这里我们选取的基准值为 6
(基准值是左侧的话则右边先行,如果选取的是最后一位,则左边先行),在定义对两个循环当中的 i
和 j
分别指向 6
和 8
- 分别从序列的两端开始进行查找,先从右往左找一个小于
6
的数,再从左往右找一个大于6
的数,然后交换他们(这里注意,是j
先开始行动) - 开始执行查找,
j
找到5
,而i
找到7
,此时i < j
,进行交换,序列变成了[6, 1, 2, 5, 9, 3, 4, 7, 10, 8]
,第一次交换结束 - 接下来
j
继续开始行动,它找到了4
,而i
找到了9
,此时i < j
,继续执行互换,变成了[6, 1, 2, 5, 4, 3, 9, 7, 10, 8]
,此时交换结束 j
继续行动,发现了3
,而i
在寻找的过程中和j
相遇了,此时i
不小于j
了,这也说明我们此次的查找过程已经结束了,所以我们将基准值6
和3
进行互换,这时就变成了[3, 1, 2, 5, 4, 6, 9, 7, 10, 8]
此时,以基准数 6
为分界点,此时我们已经将原来的序列,以 6
为分界点拆分成了两个序列,6
左边的数都小于等于 6
,而 6
右边的数都大于等于 6
,接下来,我们只需要继续按照刚才的方法分别对这两个序列来进行处理,也就是我们的 [3, 1, 2, 5, 4]
和 [9, 7, 10, 8]
,以此类推,就可以得到我们最终的结果,也就是下面这样的
其实简单来说就是,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了,下面我们来看看具体的代码是如何实现的
1 | function sort(arr, left, right) { |
堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法,堆是一个近似完全二叉树的结构,并同时满足堆积的性质,即在堆的数据结构中,堆中的最大值(或者最小值)总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)
堆排序是对『选择排序』算法的改进版本,堆当中的每个结点的值,都大于或者等于其左右孩子结点的值,称之为『大顶堆』,反正称之为『小顶堆』,每个结点的值都小于或者等于其左右孩子的结点,所以我们可以简单的总结一下堆的要点
根结点一定是堆中所有结点最大或者最小者,如果按照层序遍历的方式给结点从 1
开始编号(这里需要注意,『堆的排序下标是从 1 开始的』),则结点之间满足如下关系
- 满足
ki >= k2i && ki >= k2i + 1
就是大顶堆的情况 - 满足
ki <= k2i && ki <= k2i + 1
就是小顶堆的情况 - 以上满足条件
1 <= i <= ⌊n / 2⌋
(向下取整) - 下标
i
与2i
和2i + 1
是双亲和子女关系 - 如果我们想把大顶堆和小顶堆用层序遍历存入数组,则一定满足上面的表达式
堆排序算法的实现原理如下图所示
我们可以以上图当中的二叉树为例,来简单梳理一下其中的步骤,总共分为三步
- 将待排序的序列构造成一个大顶堆,此时整个二叉树的最大值就是堆顶的根结点,将其与堆数组的末尾元素交换,此时末尾元素就是最大值了
- 然后将剩余的
n - 1
个序列重新构造成一个新的大顶堆,这样就会得到n
个元素中的此大值 - 重复步骤二,直到堆中元素个数为
1
(或其对应数组的长度为1
),排序完成
下面我们来看代码是如何实现的
1 | // 交换两个节点 |
计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中,作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数,计数排序是一种稳定的排序算法,计数排序使用一个额外的数组 C
,其中第 i
个元素是待排序数组 A
中值等于 i
的元素的个数,然后根据数组 C
来将 A
中的元素排到正确的位置,它只能对整数进行排序,它的原理是这样的
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为
i
的元素出现的次数,存入数组C
的第i
项 - 对所有的计数累加(即从
C
中的第一个元素开始,每一项和前一项相加) - 反向填充目标数组,将每个元素
i
放在新数组的第C(i)
项,每放一个元素就将C(i)
减去1
也就是下图所示
下面是代码实现
1 | function sort(arr, maxValue) { |
桶排序
桶排序是『计数排序』的升级版,它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定,它的工作原理是将数据分到有限数量的桶子里,然后每个桶再分别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序),主要分为以下几个步骤
- 设置固定数量的空桶
- 把数据放到对应的桶中
- 对每个不为空的桶中数据进行排序
- 拼接不为空的桶中数据,得到结果
也就是下图所示
下面我们来看代码如何实现
1 | // 这里使用之前的插入排序 |
基数排序
基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,它的原理是按照低位先排序,然后收集,再按照高位排序,然后再收集,依次类推,直到最高位,有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前,具体流程如下
- 取得数组中的最大数,并取得位数
arr
为原始数组,从最低位开始取每个位组成radix
数组- 对
radix
进行计数排序(利用计数排序适用于小范围数的特点)
如下图所示
看上去可能不太好理解,所以我们用一个示例来进行了解,比如说现在有一个这样的无序数组和一个桶(buckets
)
1 | const arr = [10, 200, 13, 12, 7, 88, 91, 24] |
我们第一步就是取原数组的每个元素的个位,也就是下面这样
1 | // const arr = [10, 200, 13, 12, 7, 88, 91, 24] |
然后根据个位值的大小放到对应的桶中,其实这一步也可以理解为根据『个位值的大小』进行第一次排序,把个位数组的每个元素对应到桶的索引(也就是『计数排序』的思路),通过此步骤,目前桶就变成了
1 | buckets = [[10, 200], [91], [12], [13], [24], [], [], [7], [88]] |
在按照桶的索引进行取值,通过此步 就已经完成了原数组的个位排序
1 | arr = [10, 200, 91, 12, 13, 24, 7, 88] |
那接下来就是按照十位进行排序,取原数组的每个元素的十位
1 | // arr = [10, 200, 91, 12, 13, 24, 7, 88],如果某个元素没有该位就默认为 0 |
和上面一样,根据十位值的大小放到对应的桶中,这时桶就变成了
1 | buckets = [[200, 7], [10, 12, 13], [24], [], [], [], [], [], [88], [91]] |
跟之前一样,按照桶的索引进行取值,通过此步就已经完成了原数组的十位排序
1 | arr = [200, 7, 10, 12, 13, 24, 88, 91] |
重复以上通过同样步骤来处理百位,按照百位进行排序,并取原数组的每个元素的百位,最后就完成了基数排序
1 | // 按照百位进行排序 |
以上就是整个流程,其实简单来说,就是在计数排序的基础之上进行的的步骤分解,下面我们来看看如何用代码进行实现
1 | function radixSort(arr) { |
关于 digit
的获取这里多说一句,这里指的是计算出某个数字的某位数的值,比如说一个数字 521
,那么我们如何分别拿到 1,2,5
呢?首先 ~~
表示的是向下取整(也可以使用 Math.floor()
),m
首次是 1
以后每次乘等 10
- 所以取个位
1
,首先取模,521 % 10 = 1
,然后除以m
,也就得到了1 / 1 = 1
,最后向下取整为1
- 所以取十位
2
,首先取模,521 % 100 = 21
,然后除以m
,也就得到了21 / 10 = 2.1
,最后向下取整为2
- 所以取百位
5
,首先取模,521 % 1000 = 521
,然后除以m
,也就得到了521 / 100 = 5.21
,最后向下取整为5