排序
有n个记录的序列${R_1,R_2,...,R_n}$,其相应的关键字的序列是${K_1,K_2,...,K_n}$,相应的下标序列1,2,...,n。通过排序，找出当前的下标序列1,2,...,n的一种排列$p_1,p_2,...，p_n$，使得相应的关键字满足如下的非递减（或者非递增）关系：$K_{p1} <= K_{p2} <= ... <=K_{pn}$,这样就得到一个按关键字乐有序的记录序列。
内部排序与外部排序
根据排序时数据所占用的存储器的不同，可以将排序分为两大类。一类是整个排序过程完全在内存中进行，称为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。
主关键字与次关键字
上面所说的关键字$K_i$可以是记录$R_i$的主关键字，也可以是此关键字，甚至可以时记录中若干数据項的组合。若$K_i$是主关键字，则任何一个无序的序列经排序后得到的有序序列是唯一3的；若$K_i$是次关键字或是记录中若干数据項的组合，得到的排序结果可能是不唯一的。
排序的稳定性
若在排序前的的队列中$R_i$领先于$R_j$其中$i<j$,经过排序后得到的序列中$R_i$仍然领先于$R_j$，则称排序方法是稳定的。反之领先关系在排序时发生变化，则称排序方法是不稳定的。
无论是稳定的还是不稳定的算法，都可以很好的排序，只不过在某些时候我们需要让他的顺序保持不变。
常用排序的基本类型
1.插入类排序
-直接插入排序
-折半插入排序
-希尔排序
| 排序算法 | 稳定性 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|---|
| 直接插入 | 稳定 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ |
| 折半插入 | 稳定 | $O(n^2)$ | $O(nlogn)$ | $O(n^2)$ | $O(1)$ |
| 希尔排序 | 不稳定 | $O(n^{1.5})$ | $O(1)$ |
2.交换类排序
-冒泡排序
-快速排序
| 排序算法 | 稳定性 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|---|
| 冒泡排序 | 稳定 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ |
| 快速排序 | 不稳定 | $O(nlog_{2^n})$ | $O(nlog_{2^n})$ | $O(n^2)$ | $O(log_{2^n})$ |
3.选择类排序
-简单选择排序
-树形选择排序
-堆排序
| 排序算法 | 稳定性 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|---|
| 简单选择排序 | 不稳定 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| 树形选择排序 | 稳定 | $O(nlog_{2^n})$ | $O(nlog_{2^n})$ | $O(nlog_{2^n})$ | $O(n)$ |
| 堆排序 | 不稳定 | $O(nlog_{2^n})$ | $O(nlog_{2^n})$ | $O(nlog_{2^n})$ | $O(1)$ |
4.归并排序
-归并排序
| 排序算法 | 稳定性 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|---|
| 归并排序 | 稳定 | $O(nlog_{2^n})$ | $O(nlog_{2^n})$ | $O(n)$ |
5.分配类排序
-多关键字排序
-链式基数排序
总结
数据结构在计算机世界里承担很重要的角色。就例如十万个数排序快速排序的时间在0.5s左右（Python编写），而有的排序则需要十几分钟，可想而知，在现在大数据时代，没有一个好的数据结构，没有一个好的算法，对生产来说，十分不利。其次数据结构也大大的提升了自己的逻辑判断水平。对提升自己的编码水平，有很大的帮助，对自己以后研究算法，也会打下坚实的基础。或许这些算法以后用不到，但是我知道，其他复杂的算法都是在基础的算法之上建立的，也应当对这些基础算法进行了解。
此篇文章参考
【1】耿国华，张德同，周全名等.数据结构用c语言描述【M】.第二版.北京：高等教育出版社.2016.
有什么问题请联系我
QQ：3116316431 (请附上信息）
E-mail：wongyinlong@yeah.net