目录
一. 前言
二. 排序的概念及运用
2.1 排序的概念
2.2 排序的运用
2.3 常见的排序算法
三. 冒泡and选择排序
3.1 冒泡排序
3.2 选择排序
四. 各大排序算法的复杂度和稳定性
一. 前言
从本期开始,我们的数据结构将迎来一个新的篇章:排序篇,啪叽啪叽
排序是数据结构中非常重要的内容,在后续的内容中,我们会对各种各样的排序算法进行剖析和实现,敬请期待哦
本期要点
- 对排序进行一个整体的认识
- 介绍一下两种最简单的排序
- 笼统地介绍一下各大排序算法的复杂度和稳定性
二. 排序的概念及运用
2.1 排序的概念
排序:所谓排序就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
2.2 排序的运用
在日常生活中,我们可以找到许多和排序有关的场景。例如我们进入电脑磁盘右键就可以看到一个排序方式的选项,这是对我们电脑的磁盘文件进行排序,你可以根据需求选择不同排序方式进行排序
又或者,随便打开一个网购网站/软件,例如京东,我们可以看到左上角就可以对商品的某一维度进行排序
再或者,世界500强榜单也是经过排序后产生的
总之,无论是在计算机的学习上还是现实生活中,排序都是非常重要的主题,其运用十分广泛,它无处不在
2.3 常见的排序算法
排序算法分为比较类排序和非比较类排序,如下图所示:
三. 冒泡and选择排序
本期我们先介绍一下我们的两个老朋友:冒泡排序和选择排序
3.1 冒泡排序
- 思想 : 在一个序列中,每次对序列中的相邻记录的键值大小进行比较,将较大(升序)或较小(降序)的记录向后移动。如此循环,大/小的记录会慢慢“浮”到序列的后端,整个过程就像是冒泡一样,顾称之为冒泡排序。
- 冒泡过程:以下是对某个序列进行冒泡排序的过程
可以看出,对于上面具有5个元素的无序数组,我们通过4趟的冒泡后就将其变为有序数组,每一趟冒泡后都可以使最大的数沉底。
- 动图演示:我们可以通过一下动图感受一下冒泡两两比较的过程:
- 循环控制:很明显,我们需要两层循环来控制冒泡排序的过程。内层循环控制当前趟的数据交换,外层循环控制冒泡排序的趟数。
-
外层循环结束条件:由于每一趟结束后都有一个数冒到序列后端,因此对于N个数的序列来说,一共需要N-1趟(只剩一个数不需要冒泡)。
for (int i = 0; i < n - 1; i++) //外层循环,N-1趟 { ; }
-
内层循环结束条件:内层循环用于数据的比较。已知N个数据共需比较N-1次,由于每一趟结束后就有数据到正确的位置,下一趟需要比较的数据个数就会少1,因此每趟的比较次数随着趟数的增加呈递减趋势,初始为N-1次。
for (int i = 0; i < n - 1; i++) //外层循环,N-1趟 { for (int j = 0; j < n - 1 - i; j++) //内层循环,次数随趟数增加而递减,初始为N-1 { ; } }
-
完整代码:
void swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void BubblingSort(int* a, int n) { for (int i = 0; i < n - 1; i++) //外层循环,N-1趟 { for (int j = 0; j < n - 1 - i; j++) //内层循环,次数随趟数增加而递减,初始为N-1 { if (a[j] > a[j + 1]) //升序排列,较大的往后移 { swap(&a[j], &a[j + 1]); //交换 } } } }
- 改进优化:上面的代码还存在着改进空间,我们来看下面两个情景:
对于情境1,我们只需一趟冒泡即可让数组有序,而如果按照上面的代码,我们依旧要进行4趟的冒泡,即有三趟是无效的。
而情境1就更夸张了,数组已经有序,我们却傻乎乎的做了4趟无效冒泡。无疑是非常浪费时间的。
考虑到这些情况,我们提出了优化方案:在每趟结束后判断一下当前趟是否发生了元素交换,如果没有,则说明序列已经有序了,及时止损,反之继续。优化后的代码如下:
void swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void BubblingSort(int* a, int n) { for (int i = 0; i < n - 1; i++) //外层循环,N-1趟 { int flag=0; //标识每一趟是否发生交换 0:没有 1:有 for (int j = 0; j < n - 1 - i; j++) //内层循环,次数随趟数增加而递减,初始为N-1 { if (a[j] > a[j + 1]) //升序排列,较大的往后移 { swap(&a[j], &a[j + 1]); //交换 flag = 1; } } //判断是否已经有序 if(flag == 0) { break; //有序则退出循环 } } }
- 时间/空间复杂度:结合上面的图片和代码我们可以看出,总共N-1趟,每趟N-1,N-2...次比较,共比较 (N-1) + (N-2) + (N-3) + (N-4) + (N-5) + ...... + 1次,时间复杂度为;而由于没有额外的辅助空间,空间复杂度为。
- 稳定性分析:由于我们是将较大的或较小的进行交换,当两个数相等时并不会进行交换,因而不会改变相同元素的先后次序,所以冒泡排序是稳定的排序。
3.2 选择排序
- 思想 : 每一次从待排序的数据元素中选出最小(升序)或最大(降序)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
- 选择过程:以下是对某个序列进行选择排序的过程:
动图演示:我们一样通过动图感受一下选择排序的过程:
- 循环控制:类似的,我们需要两层循环来控制选择排序的过程。内层循环遍历序列找出最大/最小值,外层循环控制选择的次数。
-
外层循环结束条件:每一次遍历完都可以选出一个数换到起始位置,一共N个数,故要选N-1次(最后一个数不需要选择)
for (int i = 0; i < n-1; i++) //外层循环,共要选择n-1次 { ; }
-
内层循环结束条件:内层循环通过比较进行选数,一开始N个数需要比较N-1次,然后每趟结束后下一次选择的起始位置就往后移动一位,比较次数减1
for (int i = 0; i < n-1; i++) //外层循环,共选择n-1次 { for (int j = i + 1; j < n; j++) //内层循环,起始位置开始向后进行比较,选最小值 { ; } }
-
完整代码:
void swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void SelectSort(int* a, int n) { for (int i = 0; i < n-1; i++) //外层循环,共选择n-1次 { int mini = i; //记录最小值的下标,初始为第一个数下标 for (int j = i + 1; j < n; j++) //内层循环,起始位置开始向后进行比较,选最小值 { if (a[mini] > a[j]) //比最小值小,交换下标 { mini = j; } } swap(&a[mini], &a[i]); //将最小值与起始位置的数据互换 } }
- 时间/空间复杂度:一共选了N-1次,每次选择需要比较N-1,N-2,N-3...次,加起来和冒泡一样时间复杂度为;没有用到辅助空间,空间复杂度为
-
稳定性分析:由于是选数交换,在交换的过程中很可能会打乱相同元素的顺序,例如下面这个例子:
我们发现,在第一趟交换中,黑5被交换到了红5后面,在整个排序结束后,黑5依然在红5的后方,与最开始的顺序不一致。由此我们可以得出,选择排序是不稳定的排序。
四. 各大排序算法的复杂度和稳定性
废话不多说,直接上表:
排序算法 | 时间复杂度(最好) | 时间复杂度(平均) | 时间复杂度(最坏) | 空间复杂度 | 稳定性 | 数据敏感度 |
---|---|---|---|---|---|---|
比较类排序 | ||||||
冒泡排序 | 稳定 | 强 | ||||
选择排序 | 不稳定 | 弱 | ||||
直接插入排序 | 稳定 | 强 | ||||
希尔排序 | 不稳定 | 强 | ||||
堆排序 | 不稳定 | 弱 | ||||
快速排序 | 不稳定 | 强 | ||||
归并排序 | 稳定 | 弱 | ||||
非比较类排序 | ||||||
基数排序 | 稳定 | 弱 | ||||
桶排序 | 稳定 | 强 | ||||
计数排序 | 稳定 | 弱 |
以上,就是本期的全部内容啦🌸文章来源:https://www.toymoban.com/news/detail-586064.html
制作不易,能否点个赞再走呢🙏文章来源地址https://www.toymoban.com/news/detail-586064.html
到了这里,关于【数据结构】手撕排序NO.1----排序初识的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!