企业官网建设流程全解析

排序的基本概念是指将一个包含 $ n $ 个记录的文件{R1,R2,…,Rn}\{R_1, R_2, \ldots, R_n\}{R1​,R2​,…,Rn​}，其对应的关键字为{k1,k2,…,kn}\{k_1, k_2, \ldots, k_n\}{k1​,k2​,…,kn​}，通过某种算法重新排列成一个新的序列{Rj1,Rj2,…,Rjn}\{R_{j_1}, R_{j_2}, \ldots, R_{j_n}\}{Rj1​​,Rj2​​,…,Rjn​​}，使得关键字满足非递减（或非递增）顺序：kj1≤kj2≤⋯≤kjnk_{j_1} \leq k_{j_2} \leq \cdots \leq k_{j_n}kj1​​≤kj2​​≤⋯≤kjn​​。这一过程称为排序。

若在原始序列中，关键字相同的两个记录RiR_iRi​和RjR_jRj​满足RiR_iRi​在RjR_jRj​之前，且排序后RiR_iRi​依然位于RjR_jRj​之前，则称该排序算法是稳定的；否则为不稳定的。稳定性对于多关键字排序或保持数据原有顺序具有重要意义。

根据数据是否全部存入内存，排序可分为：

• 内部排序：所有待排序记录均可一次性载入内存进行处理。
• 外部排序：当数据量过大无法全部装入内存时，需借助外存（如硬盘）配合完成排序。

排序过程中主要涉及两种基本操作：

1. 比较关键字大小：判断两个元素的相对顺序。
2. 移动记录位置：调整元素在存储结构中的物理或逻辑位置（可通过指针、索引等方式优化以减少实际移动开销）。

直接插入排序是一种典型的内部排序方法，其核心思想是：
每次将第iii个记录RiR_iRi​插入到前面已排好序的子序列R1∼Ri−1R_1 \sim R_{i-1}R1​∼Ri−1​中，使其仍保持有序。具体做法是：

• 从后向前扫描已排序部分；
• 将当前关键字kik_iki​与前面的关键字逐个比较；
• 找到合适的插入位置后，将该位置之后的所有元素向后移动一位；
• 最后将RiR_iRi​插入空出的位置。

该算法的特点包括：

• 时间复杂度：平均和最坏情况下为O(n2)O(n^2)O(n2)，最好情况（原序列基本有序）下接近O(n)O(n)O(n)；
• 空间复杂度：O(1)O(1)O(1)，仅需一个临时变量用于交换；
• 稳定性：稳定，因为相等元素的相对位置不会因插入而改变；
• 适用场景：适合小规模或基本有序的数据集。

definsertion_sort(arr):foriinrange(1,len(arr)):key=arr[i]# 当前要插入的元素j=i-1# 向后移动大于key的元素whilej>=0andarr[j]>key:arr[j+1]=arr[j]j-=1arr[j+1]=key# 插入正确位置returnarr

常见的稳定排序算法包括：

1. 直接插入排序：相等元素在比较时不会发生前移，后出现的相同元素总是在前面相同元素之后插入，因此保持相对顺序。
2. 冒泡排序：仅在arr[j] > arr[j+1]时才交换，相等时不交换，故相同关键字的记录不会改变相对位置。
3. 归并排序：合并两个有序子数组时，若左右两部分的关键字相等，默认取左边先放入结果中，从而保持稳定性。
4. 基数排序（基于稳定子排序）：通常借助计数排序或桶排序作为子过程，这些方法本身是稳定的。
5. 计数排序：通过统计频次再按原序列顺序填充，能保持相同元素的输入顺序。

不稳定的常见排序算法有：

• 快速排序
• 堆排序
• 希尔排序
• 简单选择排序

注：某些算法可通过特殊设计变为稳定，但标准实现通常是不稳定的。

如何判断一个排序算法是否稳定？

可以从以下两个角度分析：

1.理论判断法（观察算法逻辑）

检查算法中是否存在可能导致相同关键字记录相对位置颠倒的操作：

• 是否存在跨越式的交换？如快排中的首尾交换可能打乱相同元素顺序。
• 在相等元素之间是否仍进行交换？例如选择排序中即使相等也会交换最小值位置，导致不稳定。
• 插入或合并过程中是否优先保留先出现的元素？

✅ 若算法保证：当两个元素关键字相等时，不改变它们原始输入顺序→ 是稳定的。

2.实例验证法（构造测试用例）

使用一组含有重复关键字但可区分来源的数据进行排序测试。
例如给每个元素附加一个序号标识其原始位置：

data=[(4,1),(2,1),(3,1),(2,2),(1,1),(4,2)]# 排序后检查所有关键字为2的元素：(2,1) 是否仍在 (2,2) 之前？

如果排序后所有相同关键字的元素仍保持附加信息的递增顺序，则算法稳定。

总结

# 示例：验证插入排序的稳定性definsertion_sort_stable(arr):# arr 是元组列表 (value, origin_index)foriinrange(1,len(arr)):key=arr[i]j=i-1whilej>=0andarr[j][0]>key[0]:# 注意只在大于时移动arr[j+1]=arr[j]j-=1arr[j+1]=keyreturnarr

该实现中，只有当前者“大于”后者时才移动，相等时不移动 → 保持了相同值之间的原始顺序 → 稳定。