当前位置：首页 > news >正文

数据结构【排序】

news 2025/7/22 23:49:37

第七章排序

在这里插入图片描述

一、排序
1.定义：将无序的数排好序；
2.稳定性： Kᵢ和Kⱼ中，Kᵢ优先于Kⱼ那么在排序后的记录中仍然保持Kᵢ优先；
3.评价标准：执行时间和所需的辅助空间，其次是算法的稳定性；空间复杂度是O(1)，代表其算法所需的辅助空间不依赖问题规模，则该排序方法为就地排序，否则就是非就地排序；
4.排序的分类：待排序的记录数不太多时为内部排序，反之为外部排序
二、插入排序
1.定义：按关键字大小插入到前面已经排好序的子序列中；
2.直接插入排序：稳定的排序；

性能分析：空间复杂度是O(1)；最好的情况时间复杂度为O(n)，最坏的时间复杂度为O(n²)；

3.折半插入排序：是一种稳定的排序算法；有些类似折半查找；时间复杂度为O(n²)；但对于数据量比较小排序表，折半插入排序往往能表现出较好的性能；
在这里插入图片描述

4.希尔排序

特点：分组后n值不断减小，关键字较小的记录跳跃式前移；
增量序列取法：无除1外的公因子；最后一个增量值必须为1；不稳定；

三、交换排序
1.定义：系统的交换反序的记录的偶对，直到不再有这样的偶对为止；
2.冒泡排序：时间复杂度T(n)=O(n²)；空间复杂度S(n)=O(1)；
在这里插入图片描述

3.快速排序：两指针，选中的指针不动与另一个指针比较，若被比较的数小于选中的指针，就往选中指针的方向移动（也就是不做改变）；否则就交换；当两指针相遇时才完成第一次排序。
在这里插入图片描述

性能分析：时间复杂度是T(n)=O(nlog₂n)，最坏情况是O(n²)；栈最大深度为[log2n]+1；空间复杂度最坏是O(n)；不稳定的算法；

四、选择排序
1.基本思想：每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。

2.简单选择排序：时间复杂度是T(n)=O(n²)，空间复杂度是S(n)=O(1)；是不稳定的；
在这里插入图片描述

3.排序

定义：基于完全二叉树，分大根堆和小根堆；
结论：排序过程中，若采用的是小根堆，排序后得到的是非递减序列；若采用的是大根堆，则排序后得到的是非递增序列；
堆的调整和筛选：根结点必须小于左右子树，否则要交换；直到第一次全部交换完成输出对顶元素，也就是最小那个，然后将堆底元素送到堆顶，再进行排序交换；一直反复循环，直到堆只剩一个元素为止；
性能分析：时间复杂度是T(n)=O(nlog₂n)，空间复杂度是S(n)=O(1)；堆排序是不稳定的；

五、归并与基数排序
1.归并排序：时间复杂度为O(m+n);