数据结构排序

🏡作者主页：点击！
🤖数据结构专栏：点击！
⏰️创作时间：2025年1月3日15点01分

排序

将各元素按关键字递增或递减顺序重新排列

评价指标：

• 稳定性：关键字相同的元素经过排序后相对顺序是否会改变
• 时间复杂度、空间复杂度

排序算法分类：

• 内部排序：数据都在内存中
• 外部排序：数据太多，无法全部放入内存

插入排序

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成

空间复杂度是O(1)

时间复杂度主要来自对比关键字、移动元素，若有n个元素，则需要 n-1 趟处理

最好时间复杂度（全部有序）：On

最坏时间复杂度（全部逆序）：On^2

平均时间复杂度：On^2

算法稳定性：稳定

折半插入排序

先使用折半查找找到应该插入的位置，再移动元素

比起直接插入排序，比较关键字的次数减少了，但是移动元素的次数没有变，整体来看时间复杂度依然是Ｏ(n^2)

希尔排序

最好情况：原本就有序

比较好的情况：基本有序

希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序。设置增量，之后缩小增量的值

第一趟为 4 第二趟就为 2 第三趟为 1，每次乘以二分之一

一般只会让弄第一次排序的结果

时间复杂度：O(1)

稳定性：不稳定

适用性：仅适用于顺序表，不适用于链表

冒泡排序

冒泡排序和快速排序同属于交换排序

基于交换的排序，根据序列中两个元素关键字的比较结果来对这两个记录在序列中的位置

从后往前两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。称这样的过程为一趟冒泡排序

第一趟排序使关键字值最小的一个元素冒到最前面

之后重复操作，第二趟第三趟 第四趟等等（每次排序都会有一个最小的关键字到前面）

前边已经确定最终位置的元素不用再进行对比

空间复杂度：O(1)

最好时间复杂度为：O(n)

最坏时间复杂度为：O(n^2)

平均时间复杂度为：O(n^2)

稳定性：稳定

适用性：顺序表、链表都可以

快速排序

冒泡排序和快速排序同属于交换排序

基于交换的排序：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

更小的元素都交换到左边

更大的元素都交换到右边

用第一个元素把待排序序列划分为两个部分，左边更小，右边更大。该元素的最终位置已确定

时间复杂度=O(n*递归层数)

最好时间复杂度=O(nlog2n)----每次选的枢纽元素都能将序列划分成均匀的两部分

最坏时间复杂度=O(n^2)----若序列原本就有序或逆序，则时、空复杂度最高

空间复杂度=O(递归层数)

最好空间复杂度=O(log2n)

最坏空间复杂度=O(n)

快速排序是所有内部排序算法中平均性能最优的排序算法

简单选择排序

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

n个元素的简单选择排序需要 n-1 趟处理

空间复杂度：O(1)

时间复杂度：O(n^2)

稳定性：不稳定

适用性：既可以用于顺序表，也可以用于链表

堆排序

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

大根堆：完全二叉树中，根>=左、右

小根堆：完全二叉树中，根=<左、右

思路：把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整

堆排序：每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换）

并将待排序元素序列再次调整为大根堆（小元素不断下坠）

基于大根堆的堆排序得到递增序列

堆排序的时间复杂度：O(n)+O(nlog2n)=O(nlog2n)

堆排序的空间复杂度：O(1)

堆排序是不稳定的

Author：DC