排序——数据结构

### 数据结构之排序知识点详解 #### 10.1 排序概述 - **10.1.1 排序的定义** - **数据表（Data List）**：待排序的数据对象组成的有限集合。 - **主关键字（Key）**：数据对象中的一个属性域，用于区分不同对象，作为排序的依据。 - 示例：对于记录序列`{R1, R2, ..., Rn}`，其关键字序列为`{K1, K2, ..., Kn}`，排序后的新记录序列为`{Rp1, Rp2, ..., Rpn}`，满足`Kp1 ≤ Kp2 ≤ ... ≤ Kpn`。 - **排序算法的稳定性** - **稳定性定义**：若两个对象`r[i]`和`r[j]`具有相同的排序码`k[i] = k[j]`，且在排序前`r[i]`位于`r[j]`之前，则排序后`r[i]`仍然位于`r[j]`之前，这样的排序方法被称为稳定排序；反之，则称为不稳定排序。 - **稳定性的重要性**：对于某些应用场景而言，维持相等元素间的相对顺序是非常重要的，因此稳定排序方法更受青睐。 - **排序的时间开销** - 排序的时间开销通常用算法执行中的数据比较次数和数据移动次数来衡量，这直接反映了算法的效率。 #### 10.1.2 内部排序和外部排序 - **内部排序**：所有待排序的记录均存放在计算机的内存中进行排序的过程。 - **外部排序**：由于待排序记录数量巨大，无法完全放入内存中处理，需要频繁地访问外存进行排序的过程。 #### 10.1.3 内部排序方法的分类 - **插入类排序**：从无序子序列中取出一个或多个记录，将其插入到已排序好的序列中的合适位置，以增加有序子序列的长度。 - **交换类排序**：通过交换无序序列中的记录，找出关键字最小或最大的记录，将其放到已排序好的序列末尾，以此方式增加有序子序列的长度。 - **选择类排序**：从无序子序列中选出关键字最小或最大的记录，将其放到已排序好的序列末尾，以此方式增加有序子序列的长度。 - **归并类排序**：通过合并两个或多个有序子序列，逐步构建更大的有序序列。 - **基数排序**：适用于非负整数排序，根据数值的各个位上的数字进行排序。 #### 10.2 插入排序 - **基本思想**：每一步将一个待排序的对象按照其关键字的大小，插入到前面已经排好序的对象序列中的适当位置，直到所有对象都插入完毕。 - **示例**：对于序列`52, 49, 80, 36, 14, 58, 61, 23, 97, 75`，首先假定第一个元素是已排序的部分，然后将剩余的每个元素依次插入到已排序部分的正确位置。 - **时间复杂度**： - 最佳情况：O(n)，当输入序列已经是有序的情况下。 - 最坏情况：O(n^2)，当输入序列是逆序时。 - 平均情况：O(n^2)，在随机输入序列下的表现。 - **空间复杂度**：O(1)，因为是原地排序算法。 - **稳定性**：插入排序是稳定的排序算法。 #### 10.3 快速排序 - **基本思想**：采用分治策略，选择一个基准元素，将数组分为两部分，使得一部分的所有元素都小于等于基准，另一部分的所有元素都大于等于基准，然后递归地对这两部分进行同样的操作。 - **时间复杂度**： - 最佳情况：O(n log n)，当每次都能均匀分割数组时。 - 最坏情况：O(n^2)，当每次选择的基准都是最大或最小值时。 - 平均情况：O(n log n)。 - **空间复杂度**：O(log n)，递归栈的空间需求。 - **稳定性**：快速排序是不稳定的排序算法。 #### 10.4 堆排序 - **基本思想**：利用堆这种数据结构所设计的一种排序算法，包括建立初始堆、调整堆和输出堆顶元素三个步骤。 - **时间复杂度**：O(n log n)。 - **空间复杂度**：O(1)，是原地排序算法。 - **稳定性**：堆排序是不稳定的排序算法。 #### 10.5 归并排序 - **基本思想**：采用分治策略，将数组分成两半，分别对每一半进行排序，然后再将两个有序数组合并成一个有序数组。 - **时间复杂度**：O(n log n)。 - **空间复杂度**：O(n)，需要额外的存储空间用于合并操作。 - **稳定性**：归并排序是稳定的排序算法。 #### 10.6 基数排序 - **基本思想**：适用于非负整数排序，按照数值的个位、十位、百位等从低到高逐位排序。 - **时间复杂度**：O(dn)，其中d表示整数的最大位数，n表示待排序的整数个数。 - **空间复杂度**：O(n + k)，k表示基数。 - **稳定性**：基数排序是稳定的排序算法。 #### 10.7 各种排序方法的综合比较 - **时间复杂度**： - 插入排序、选择排序和冒泡排序的时间复杂度为O(n^2)。 - 快速排序、堆排序和归并排序的时间复杂度为O(n log n)。 - 基数排序的时间复杂度为O(dn)，适用于特定类型的数据排序。 - **空间复杂度**： - 插入排序、选择排序和堆排序为O(1)，是原地排序算法。 - 快速排序和归并排序需要额外的空间，分别为O(log n)和O(n)。 - 基数排序需要O(n + k)的额外空间。 - **稳定性**： - 插入排序、归并排序和基数排序是稳定的排序算法。 - 快速排序和堆排序是不稳定的排序算法。 #### 10.8 外部排序 - **基本概念**：当数据量非常大以至于无法一次性装入内存时，需要使用外部排序技术。 - **常用方法**：多路归并排序、置换选择排序等。 - **关键问题**：如何有效地管理磁盘读写操作，减少I/O次数。 通过以上对排序方法的详细介绍，我们可以看出不同的排序算法各有特点，适用于不同的场景。了解这些算法的原理和特性有助于在实际开发中做出合理的选择。