数据结构-排序(1)

一，排序的基本概念

1.排序的定义

• 核心概念： 给定一个包含 n 个元素的序列 (R1, R2, ..., Rn) 和一个关键码 Ki（通常是记录 Ri 的一个属性），排序的目标是找到一个排列 (p1, p2, ..., pn)，使得关键码序列 (Kp1, Kp2, ..., Kpn) 满足一个特定的非递减（升序）或非递增（降序）关系。

• 通俗理解： 就是把一堆杂乱无章的数据，按照某种规则（比如数字大小、字母顺序、日期先后）排列整齐的过程。

2.排序的目的与重要性

1. 提高查找效率： 在有序数据上进行查找（尤其是二分查找）的速度远快于无序数据（顺序查找）。例如，在电话簿中找名字、在字典中查单词。

2. 数据组织与呈现： 用户通常期望看到有序的数据，如按价格从低到高显示商品、按分数从高到低排名学生成绩、按时间顺序显示邮件。

3. 数据分析和统计的基础： 许多统计计算（如中位数、百分位数）和数据分析操作（如合并、分组、去重）都依赖于或受益于数据的有序性。

4. 作为其他算法的子程序： 很多高效的算法（如归并排序用于外部排序、二叉搜索树构建）都需要先对数据进行排序。

5. 优化资源使用： 有序数据有时可以减少存储空间（如通过游程编码压缩）或提高某些处理过程（如合并有序文件）的效率。

3.排序的分类（关键维度）

排序算法可以从多个维度进行分类，以下是主要分类方式：

1.按存储位置：

• 内部排序： 整个排序过程完全在内存中进行。适用于数据量较小，可以一次性加载到内存的情况。这是最常见的研究对象。例如：冒泡排序、插入排序、选择排序、快速排序、堆排序、归并排序。
• 外部排序： 待排序的数据量非常大，无法一次性装入内存。排序过程需要在内存和外存（如磁盘）之间进行多次数据交换。通常基于归并排序的思想进行优化。例如：多路归并排序

2.按稳定性：

• 稳定排序： 如果待排序序列中存在关键码相等的记录 Ri 和 Rj（即 Ki = Kj），且在排序前的序列中 Ri 领先于 Rj（即 i < j）。如果排序后 Ri 仍然领先于 Rj，则称该排序算法是稳定的。
• 重要性： 当需要按多个关键码进行排序时（例如，先按分数降序排，分数相同的再按学号升序排），稳定性至关重要。第一次排序（按分数）的稳定性保证了分数相同的记录在第二次排序（按学号）时，其原始相对顺序（学号顺序）得以保留。
• 常见稳定排序： 冒泡排序、插入排序、归并排序、基数排序、计数排序。
• 不稳定排序： 不能保证关键码相等的记录的相对位置在排序前后保持一致。
• 常见不稳定排序： 选择排序、快速排序、堆排序、希尔排序。

3.按时间复杂度： (最常用和最重要的分类维度)

• 简单排序 / O(n²) 排序： 平均和最坏情况时间复杂度为 O(n²)。通常实现简单，代码量小，适用于小规模数据或基本有序的数据，但性能在大数据量下较差。

  • 冒泡排序、插入排序、选择排序。

• 高效排序 / O(n log n) 排序： 平均时间复杂度为 O(n log n)。性能优异，适用于大规模数据。

  • 快速排序、归并排序、堆排序。

• 线性时间排序 / O(n) 排序： 在特定条件下（如关键码是某个较小范围内的整数）可以达到线性时间复杂度 O(n)。它们通常不是基于比较的排序。

  • 计数排序、桶排序、基数排序。

• 其他： 希尔排序（时间复杂度介于 O(n log n) 和 O(n²) 之间，具体取决于增量序列）。

4.按是否比较：

• 比较排序： 通过比较元素之间的大小关系来决定它们的相对顺序。排序算法的下界（即任何比较排序算法在最坏情况下所需的比较次数）是 Ω(n log n)。

  • 冒泡、插入、选择、快速、归并、堆、希尔排序。

• 非比较排序： 不通过直接比较元素大小来确定顺序，而是利用数据的特定属性（如整数范围、位数）进行排序。它们可以突破 Ω(n log n) 的下界，达到 O(n) 的时间复杂度，但应用场景有特定限制。

  • 计数排序、桶排序、基数排序。

5.按原地性：

• 原地排序： 排序过程中只需要常数级别的额外辅助存储空间（O(1)）。主要通过在原始数组内部交换元素来完成排序。

  • 冒泡排序、插入排序、选择排序、快速排序、堆排序、希尔排序。

• 非原地排序： 排序过程中需要额外的、与数据规模 n 成比例的存储空间（O(n) 或更多）。通常需要额外的数组来存放中间结果或最终结果。

  • 归并排序、计数排序、桶排序、基数排序。

五、常见排序算法简述 (按时间复杂度)

1.O(n²) 算法：

• 冒泡排序： 反复遍历列表，比较相邻元素，如果顺序错误就交换它们。每一轮遍历将最大的元素“冒泡”到末尾。实现简单，效率低。

• 插入排序： 将列表视为“已排序区”和“未排序区”。每次从未排序区取出第一个元素，在已排序区中从后向前扫描找到合适的位置插入。对部分有序数据和小规模数据高效。

• 选择排序： 反复从未排序部分中选择最小（或最大）元素，将其与未排序部分的第一个元素交换位置。交换次数少，但比较次数固定为 O(n²)，不稳定。

2.O(n log n) 算法：

• 快速排序： 采用分治法。选择一个基准元素，将列表划分为两部分：小于基准的部分和大于基准的部分。然后递归地对这两部分进行排序。平均性能极佳，是最常用的通用排序算法之一。原地，不稳定。

• 归并排序： 采用分治法。将列表递归地分成两半，直到每部分只有一个元素（天然有序）。然后反复合并两个已排序的子列表，最终得到完整有序列表。性能稳定 (O(n log n))，稳定，但需要额外 O(n) 空间。是外部排序的基础。

• 堆排序： 利用堆（一种特殊的完全二叉树）这种数据结构。将列表构建成最大堆（或最小堆），堆顶元素就是最大（最小）值。将堆顶元素与末尾元素交换，堆大小减一，然后重新调整堆使其满足堆性质。重复此过程直到堆为空。原地，不稳定，O(n log n) 时间复杂度稳定。

3.O(n) 算法 (非比较，特定条件下)：

• 计数排序： 要求输入数据是确定范围（如 0 到 k）内的整数。创建一个计数数组统计每个整数出现的次数，然后根据计数数组重构有序序列。稳定，需要额外 O(k+n) 空间。

• 桶排序： 假设输入数据均匀分布在某个范围内。将数据分到有限数量的有序桶中（例如，范围 [0,1) 分成 10 个桶 [0,0.1), [0.1,0.2), ..., [0.9,1)）。对每个桶内进行排序（可用其他算法），然后按桶顺序依次输出。性能依赖于数据分布和桶内排序算法。

• 基数排序： 从最低有效位（LSD）或最高有效位（MSD）开始，对关键码进行逐位排序。通常使用稳定排序（如计数排序）作为其子过程。适用于整数、字符串等有固定位/字符长度的数据。稳定，需要额外空间。

六、如何选择合适的排序算法？

选择排序算法需要考虑多个因素，没有绝对最好的，只有最适合特定场景的：

1.数据规模 (n)：

• 很小 (n < 100)： 简单排序（插入、冒泡、选择）效率差别不大，选择实现简单或稳定的（如插入）。
• 中等 (100 < n < 1000)： 希尔排序、快速排序、归并排序、堆排序表现良好。插入排序对部分有序数据仍有竞争力。
• 很大 (n > 1000)： 必须选择 O(n log n) 算法（快排、归并、堆排）或线性排序（如果条件满足）。快排通常是首选（平均性能好）。

2.数据初始状态：

• 基本有序： 插入排序、冒泡排序效率接近 O(n)。
• 完全随机： 快排、堆排、归并排序表现好。
• 部分有序： 适应性算法（如插入、希尔）可能更快。

3.稳定性要求：

• 需要稳定排序：归并排序、插入排序、冒泡排序、计数排序、基数排序。
• 不需要稳定排序：快排、堆排、选择排序、希尔排序。

4.空间限制：

• 内存紧张：选择原地排序（快排、堆排、插入、希尔、冒泡、选择）。
• 内存充足：归并排序、计数排序、桶排序、基数排序可以考虑。

5.关键码类型和范围：

• 如果是小范围整数：计数排序效率极高 (O(n+k))。
• 如果是整数、字符串且有固定长度：基数排序非常高效 (O(d*(n+k)))。
• 如果是浮点数且均匀分布：桶排序可能表现好。
• 通用类型：只能使用比较排序。

6.实现复杂度和维护性：

• 简单排序（冒泡、插入、选择）易于理解和实现。
• 快排、堆排、归并排序实现相对复杂，但标准库通常已优化实现。

七，排序用到的结构与函数

define MAXSIZE 10
typedef struct
{
int r[MAXSIZE+1];
int length;
}SqList;void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}