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

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

直接插入排序

一种简单的排序方法

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

案例：

<3，1，4，1，5，9，6，5> 
原元素序列：监视哨（3）1,4,1,5,9,6,5
一、3 (1,3),4,1,5,9,6,5		插入时与1进行比较一次
二、4（1，3，4)1,5,9,6,5		插入时与3进行比较一次
三、1（1，1，3，4）5,9,6,5		插入时与1，3，4进行比较三次
四、5（1，1，3，4，5）9,6,5		插入时与4进行比较一次
五、9（1，1，3，4，5，9）6,5		插入时与5进行比较一次
六、6（1，1，3，4，5，6，9）5		插入时与5，9进行比较两次
七、5（1，1，3，4，5，5，6，9）		插入时与5，6，9进行比较三次
	共比较12次
           

希尔排序

又称“缩小增量排序”，是直接插入排序的改进

做法：

将记录序列分割成若干子列，然后分别进行直接插入排序。

< 3，1，4，1，5，9，6，5>  从小到大
k增量设为：4，2，1（自定，一般为n/2）即移动要比较的位置 例如：k=2，i = 1，则比较位置为 3.
一、 3，1，4，1，5，9，6，5 均 a<b无需移动 k =4
二、3，1，4，1，5，5，6，9 移动5和9 k = 2
三、1，1，3，4，5，5，6，9 插入排序 k = 1
           

冒泡排序

做法：

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（a>b）,则交换这两个记录的值，然后比较第二个和第三个记录的关键字，直至n-1个记录与n个记录比较过为止。

冒泡排序可以从前往后（1-2，2-3），也可以从后往前（n-（n-1），（（n-1）-（n-2）））

<3，1，4，1，5，9，6，5> 从小到大
第一遍排序结果
1，3，4，1，5，9，6，5
1，3，4，1，5，9，6，5
1，3，1，4，5，9，6，5
1，3，1，4，5，9，6，5
1，3，1，4，5，9，6，5
1，3，1，4，5，6，9，5
1，3，1，4，5，6，5，9
第一遍结束的标志为关键字最大记录交换到第n的位置
随即开始第二趟冒泡排序，最大关键字交换到n-1的位置
           

归并排序

做法：

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

< 3，1，4，1，5，9，6，5> 
一、[1,3],[1,4],[5,9],[5,6] 	比较四次
二、[1,1,3,4],[5,5,6,9]		前半部分比较三次，后半部分比较三次
三、[1,1,3,4,5,5,6,9]		5 分别与前半部分比较一次
共比较12次
           

简单选择排序

做法：

通过n-i（1<=i<=n）在次关键字之间比较，从n-i+1个记录中选出最小的记录，并和第i个记录交换，当i等于n时所有记录有序排序。

即 3 和[1，4，1，5，9，6，5]中最小的进行交换 -1.

< 3，1，4，1，5，9，6，5>  从小到大
一、1，3，4，1，5，9，6，5  	1-3交换
二、1，1，4，3，5，9，6，5	1-3交换
三、1，1，3，4，5，9，6，5	3-4交换
四、1，1，3，4，5，5，6，9	5-9交换
	中间省略不交换循环
           

快速排序

做法：

通过一趟排序将待排序的记录划分为两部分，称为前半区和后半区，前半区中的记录均不大于后半区的关键字，然后分别继续进行快速排序，从而有序。

当i，j相等时结束排序。i，j 初始为第一个和最后一个记录。枢轴记录一般为第一个关键字的值。

< 3，1，4，1，2，9，6，5>  从小到大，选定3为枢轴即pivot
一、从右往左找到小于pivot的值
二、从左往右找到大于pviot的值
三、当都停止移动时，交换i，j的值
四、随即按照以上步骤继续移动，直至i=j，停止检索，将pivot的值和i=j的位置的值交换。
第一轮结束：pivot的左边均比pivot小，右边均比pivot大。
随后递归进行。
 3，1，4，1，2，9，6，5
 一、 3，1，2，1，4，9，6，5		i=2，j=4
 二、i=j=3，交换位置得 1，1，2，3，4，9，6，5	第一轮结束。
 三、重复以上步骤直至完成排序。
           

堆排序

什么是堆：

1.必须是完全二叉树

2.父节点的值必须大于子节点

堆的相关知识：https://www.bilibili.com/video/av47196993?from=search&seid=16388479098851201312

具体堆排序在24分钟，但是建议看完所有视频，讲的不错

堆排序实现：

首先满足堆的条件，则将根节点和最后一个节点数据交换并将最后一个节点剔除，单独保存到数组。

接着进行堆化，让其满足根节点为最大值，在将根节点与最后一个节点的值进行交换，剔除最后一个节点，将其加入到之前的数组，重复以上步骤，直至排序完成。

基数排序

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

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

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