冒泡排序,插入排序,选择排序三种算法的优劣

秒速五厘米 2022-02-02 16:25 286阅读 0赞

[https://www.jianshu.com/p/9f724c880124][https_www.jianshu.com_p_9f724c880124]

最近听了王争老师的数据结构与算法之美,大有获益,特写此博客与大家分享.

排序算法太多了，但大体可以归结于三类,冒泡排序,插入排序,选择排序,那么如果分析一个算法呢,评价一个算法的优劣呢,可以从三方面入手,1.排序算法的执行效率,2,排序算法的内存消耗 3,排序算法的稳定性,下面咱们先从这三方面来学会如何分析算法.

一:**排序算法的执行效率**

针对执行效率可以从以下几点来分析:

1,最好情况,最坏情况,平均情况时间复杂度

为什么要区分这三种时间复杂度呢?第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分.第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

2,时间复杂度的系数,常数,低阶

我们知道，时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶.但是实际的软件开发中，我们排序的可能是 10 个、100 个.1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来.

3,比较次数和交换(或移动次数)

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小,另一种是元素交换或移动.所以我们在分析排序算法的执行效率的时候,比较次数和交换(或移动次数)也要考虑进

二:**排序算法的内存消耗**

算法的内存消耗可以通过空间复杂度来衡量,排序算法也是一样.不过针对排序算法的空间复杂度,我们还引入一个新的概念,**原地排序***.*原地排序算法，就是特指空间复杂度是 O(1) 的排序算法,今天我们讲的三种算法,都是原地排序算法.

*三:**排序算法的稳定性***

这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后,相等元素之间的前后顺序不变.

这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后就是 2，3，3，4，8，9。

这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3的前后顺序没有改变,我们就把这种排序算法叫稳定的排序算法.如果前后顺序发生改变,这种算法就是不稳定排序算法.

但是这种稳定性对排序有什么影响呢?举个例子,比如说我们现在要给电商交易系统中的订单进行排序,要按照下单时间,和交易金额两个维度进行排序.我们希望按照金额从小到大排序,时间从早到晚排序,对于相同金额,按照从早到晚排序.

最先想到的办法是:先按照订单金额进行排序,然后遍历排序好的数据,对于金额相同的小区间,按照时间从早到晚再排序.这种排序思路不难,但实行起来却不简单.

借助稳定排序算法，这个问题可以非常简洁地解决.我们可以先按照订单时间 进行排序,排序完成后我们按照稳定排序算法再按照订单金额进行排序,两遍排序之后,我们的订单金额是按照从小到大进行排序,金额相同的是按照时间从早到晚进行排序.为什么呢?稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变.

![Image 1][]

下面开始学习这三种算法,先从冒泡算法开始吧!

**冒泡算法(Bubble sort)**

冒泡算法只会操作相邻的两个数据.冒泡算法每次都会对相邻的两个元素进行比较,看是否满足大小关系.如果不满足大小大小,就把他们的位置互换.一次冒泡,至少会让一个元素移动到他应该在的问题.重复了n次,就完成了 n个数据排序工作.举个例子,我们要对一组元素4,5,6,3,2,1按照从小到大进行排序.第一次冒泡操作的详细过程:

![Image 1][]

可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置,我们要完成所有数据的排序,就要经过6次这样的操作.

![Image 1][]

当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用进行后续操作,举个例子,这里有6个元素,只需要四个冒泡操作就可以.

![Image 1][]

冒泡算法原理比较简单,下面我把代码贴出来:我用的oc语言

![Image 1][]

现在咱们可以结合之前讲的分析排序算法来思考三个问题:

**1,冒泡算法是原地排序算法吗?**

冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以他的空间复杂度为O(1),是一个原地排序算法.

**2,冒泡算法是稳定的排序算法吗?**

为了保证冒泡算法的稳定系,当有相邻两个元素大小相等的时候,我们不做交换,所以冒泡算法是稳定的排序算法.

**3,冒泡排序的时间复杂度是多少?**

最好的情况,要排序的数据已经有序了,我们只进行一次冒泡操作,所以时间复杂度是O(n),最坏的情况是要排序的数据是倒序的,我们要进行n次冒泡操作,所以时间复杂度是O(n^2)

![Image 1][]

那么平均复杂度怎样计算呢?平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论.

对于包含n个元素的数组,这n个元素就有n!(n的阶乘1\*2\*(n-2)\*(n-1)\*n)种排列方式 ,不同的排列方式,冒泡算法排序的时间也是不同的.比如我们前面举过的例子,其中一个要进行6次冒泡,另一个要4次,如果用概率论方法定量分析平均时间复杂度,涉及的数学推理和计算比较复杂,我们可以通过另一种思路,通过**有序度**和**逆序度**来分析.

有序度是数组中具有有序 关系的元素对的个数,有序元素对用数学表达式表示就是这样,

有序元素对：a\[i\] <= a\[j\], 如果 i < j。

![Image 1][]

对于一个倒序排列的数组的有序度是0, 如:6,5,4,3,2,1,对于一个正序排列数组1,2,3,4,5,6 有序度是n\*(n-1)/2,也就是15,我们把这种完全有序的数组的有序度称为**满有序度.**

逆序度的定位和有序度正好相反,逆序元素对：a\[i\] > a\[j\], 如果 i < j。

这三个概念可以得到一个公式,**逆序度=满有序度-有序度.**

比如前面那个冒泡算法的有序度对应关系就是:

![Image 1][]

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n\*(n-1)/2–初始有序度。此例中就是 15–3=12，要进行 12 次交换操作。

![Image 1][]

**插入排序（Insertion Sort）**

一个有序的数组,我们往里面插入一个元素,怎么保证数据有序呢?我们只需要遍历数组,找到数据应该插入的地方将其插入.

![Image 1][]

具体怎么去做呢,首先我们把数组中的数据分为两个区间,**已排序区间**和**未排序区间**.初始已排序区间只有一个元素，就是数组的第一个元素.插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间,右侧为未排序区间.

![Image 1][]

插入排序也包含两种操作，一种是**元素的比较**，一种是**元素的移动.**当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

为什么说移动次数就等于逆序度呢？我拿刚才的例子画了一个图表，你一看就明白了。满有序度是 n\*(n-1)/2=15，初始序列的有序度是 5,所以逆序度是 10。插入排序中，数据移动的个数总和也等于 10=3+3+4。

![Image 1][]

代码展示:oc代码

![Image 1][]

大家也可以思考下那三个问题,1,插入排序是否是原地排序2,插入排序是否是稳定的排序,插入排序的时间复杂度.

**选择排序（Selection Sort）**

![Image 1][]

照例也是有三种算法需要你思考:前面已经有分析,这里直接公布结果: