从零开始学数据结构系列之第六章《排序简介》
文章目录
- 排序
- 什么是排序
- 排序的稳定性
- 稳定性
- 稳定性得好处
- 往期回顾
排序
什么是排序
所谓排序，就是使一串数据，按照其中的某个或某些关键字的大小，递增或递减排列起来的操作。
简单来说，就是一组混乱的数，将他从小到大排/或者从大到小排序
排序前：
排序后：
排序的稳定性
稳定性
排序前后两个相等的数相对位置不变，则算法稳定。
例如我下面这个例子（黑色字体指的是待排序的数据，褐色字体指的是下标）
我们可以看到有两个4，下标不同
我们可以理解为下标为3的这个4是第一次出现，下标为5的这个4是第二次出现的
那如果排序算法稳定的话（从小到大排序）
那如果排序算法不稳定的话（从小到大排序）
就是他们两个相对位置变了，所以排序不稳定
稳定性得好处
从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。
意义：排序算法稳定性的意义在于，在对复杂的元素（拥有多个属性）的排序中，稳定的算法可以保留【原先相同元素之间的关系】。
举个例子
一个班的学生已经按照学号大小排好序了，我现在要求按照年龄从小到大再排个序，如果年龄相同的，必须按照学号从小到大的顺序排列。
那么问题来了，你选择的年龄排序方法如果是不稳定的，是不是排序完了后年龄相同的一组学生学号就乱了，你就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法，我就只需要按照年龄排一遍就好了。
这样看来稳定的排序算法是不是节省了时间。稳定性的优点就体会出来了
或者：
比如一组商品原来按照价格从高到低排序，现在对其按销量从高到低排序。如果使用稳定的排序算法，可以保证在按销量排序后，相同销量的商品价格保持从高到低的排序。
☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！
往期回顾
1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》
60【第四章】《迪杰斯特拉算法了解》
61【第四章】《Dijkstra 迪杰斯特拉算法图解》
62【第四章】《Dijkstra 迪杰斯特拉算法总代码》
63【第四章】《弗洛伊德(floyd)算法简介》
64【第四章】《弗洛伊德算法详解》
65【第四章】《弗洛伊德代码详解》
66【第四章】《拓扑排序之AOV网》
67【第四章】《拓扑排序介绍及其方法》
68【第四章】《拓扑排序代码详解》
69【第四章】《什么是关键路径》
70【第四章】《什么是关键路径二》
71【第四章】《关键活动与最早路径实现思想》
72【第四章】《关键活动与最早路径实现思想写法二》
73【第四章】《关键路径总代码讲解写法一》
74【第四章】《关键路径总代码讲解写法二》
75【第五章】《顺序查找》
76【第五章】《顺序查找-带哨兵》
77【第五章】《二分查找》
78【第五章】《B树了解以及定义》
79【第五章】《B树的插入例子1》
80【第五章】《B树的插入例子2》
81【第五章】《B树的删除》
82【第五章】《B树的删除2》
83【第五章】《B树的代码部分》
84【第五章】《B树的总体代码》