软件设计师–数据结构复习（排序）案例及相关知识

• 直接插入排序
• 希尔排序
• 冒泡排序
• 归并排序
• 简单选择排序
• 快速排序
• 堆排序
• 基数排序

直接插入排序

一种简单的排序方法
具体做法是：再插入第i个记录时，R1,R2…Ri-1已经排好序，这时将关键字ki与关键字ki-1，ki-2进行比较从而找到位置插入
案例：

希尔排序

又称“缩小增量排序”，是直接插入排序的改进
做法：
将记录序列分割成若干子列，然后分别进行直接插入排序。

冒泡排序

做法：
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（a>b）,则交换这两个记录的值，然后比较第二个和第三个记录的关键字，直至n-1个记录与n个记录比较过为止。
冒泡排序可以从前往后（1-2，2-3），也可以从后往前（n-（n-1），（（n-1）-（n-2）））

归并排序

做法：
是将两个或两个以上的有序文件合并为一个新的有序文件。

简单选择排序

做法：
通过n-i（1 即 3 和[1，4，1，5，9，6，5]中最小的进行交换 -1.

快速排序

做法：
通过一趟排序将待排序的记录划分为两部分，称为前半区和后半区，前半区中的记录均不大于后半区的关键字，然后分别继续进行快速排序，从而有序。
当i，j相等时结束排序。i，j 初始为第一个和最后一个记录。枢轴记录一般为第一个关键字的值。

堆排序

什么是堆：
1.必须是完全二叉树
2.父节点的值必须大于子节点

堆的相关知识：https://www.bilibili.com/video/av47196993om=search&seid=16388479098851201312
具体堆排序在24分钟，但是建议看完所有视频，讲的不错

堆排序实现：
首先满足堆的条件，则将根节点和最后一个节点数据交换并将最后一个节点剔除，单独保存到数组。
接着进行堆化，让其满足根节点为最大值，在将根节点与最后一个节点的值进行交换，剔除最后一个节点，将其加入到之前的数组，重复以上步骤，直至排序完成。

基数排序

类似于队列，从个位，往上，将个位数值相同的放到一个队列里，先进先出，比较的位数按照最大的进行比较即1441，512，12则需从个十百千依次比较，入队，出队，其余位补零即0012，0512.

可视化展示：https://www.bilibili.com/video/av33889058om=search&seid=7331912349404153369

相关数据算法看：https://blog.csdn.net/qq_25233621/article/details/80993174

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34639 人正在系统学习中