数据结构--排序

标签：25 排序 -- 复杂度 元素 数组 序列 数据结构

排序是计算机科学与技术领域中的一项基本操作，旨在将一组数据按某种顺序排列。以下是几种常见排序算法的具体解释：

一、冒泡排序（Bubble Sort）

• 工作原理

  冒泡排序算法的工作原理如下：

1. 比较相邻的元素。如果第一个比第二个大（对于升序排序，如果是降序则相反），就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大数（或最小数）。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

初始数组：[64, 34, 25, 12, 22, 11, 90]

1. 第一次遍历：[34, 25, 12, 22, 11, 64, 90]（64和34交换，64和后面的元素不再比较，因为64已经是最大的了）
2. 第二次遍历：[25, 12, 22, 11, 34, 64, 90]（34和25交换）
3. 第三次遍历：[12, 22, 11, 25, 34, 64, 90]（25和12交换）
4. ...（继续遍历，直到没有需要交换的元素）
5. 最终数组：[11, 12, 22, 25, 34, 64, 90]

• 标记法：设置一个标志位，用于判断在一趟排序过程中是否发生了交换。如果没有发生交换，说明数组已经有序，可以提前结束排序。
• 鸡尾酒排序（双向冒泡排序）：这是冒泡排序的一种改进版本。它先进行从左到右的冒泡排序，然后进行从右到左的冒泡排序。这个过程可以重复多次，直到数组有序。
• 最优时间复杂度：O(n)（当输入数组已经有序时，通过标记法可以避免不必要的比较和交换）
• 最坏时间复杂度：O(n^2)
• 平均时间复杂度：O(n^2)

二、选择排序（Selection Sort）

• 工作原理

选择排序算法的工作原理如下：

1. 从未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

• 示例

假设有一个数组 arr = [64, 25, 12, 22, 11]，使用选择排序进行升序排序的过程如下：

1. 初始数组：[64, 25, 12, 22, 11]
2. 第一次遍历：找到最小元素11，与第一个元素64交换，得到[11, 25, 12, 22, 64]
3. 第二次遍历：在剩余元素[25, 12, 22, 64]中找到最小元素12，与第二个元素25交换，得到[11, 12, 25, 22, 64]
4. 第三次遍历：在剩余元素[25, 22, 64]中找到最小元素22，与第三个元素25交换，得到[11, 12, 22, 25, 64]
5. 第四次遍历：剩余元素[25, 64]中最小元素是25，已经处于正确位置，无需交换
6. 最终数组：[11, 12, 22, 25, 64]

• 特点

• 稳定性：选择排序是不稳定的排序算法。例如，对于数组[5, 5, 3]，选择排序可能会先选出第一个5作为最小值，然后与3交换，得到[3, 5, 5]，改变了两个5的相对位置。
• 时间复杂度：选择排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。因为每次都需要遍历剩余未排序元素来找到最小（或最大）元素，所以需要进行n-1次遍历，每次遍历都需要O(n)的时间。
• 空间复杂度：选择排序的空间复杂度为O(1)，因为它只需要常数级别的额外空间来存储临时变量。

三、插入排序（Insertion Sort）

• 工作原理

1. 初始状态：将数组的第一个元素视为已排序部分，其余元素视为未排序部分。
2. 遍历过程：从数组的第二个元素开始，逐个将未排序部分的元素插入到已排序部分的适当位置。
3. 插入操作：对于每个待插入的元素，从已排序部分的末尾开始向前扫描，找到其应该插入的位置，并将该位置及其后的元素向后移动一位，然后将待插入元素放入正确位置。

• 算法步骤

1. 将数组分为已排序部分和未排序部分。
2. 从未排序部分的第一个元素开始，逐个取出元素进行插入操作。
3. 在已排序部分中找到待插入元素的正确位置，并进行插入。
4. 重复步骤2和3，直到所有元素都被插入到已排序部分中。

• 示例

假设有一个数组 arr = [5, 2, 4, 6, 1, 3]，使用插入排序进行升序排序的过程如下：

1. 初始状态：[5 | 2, 4, 6, 1, 3]（5为已排序部分，其余为未排序部分）
2. 第一次插入：将2插入到已排序部分的适当位置，得到[2, 5 | 4, 6, 1, 3]
3. 第二次插入：将4插入到已排序部分的适当位置，得到[2, 4, 5 | 6, 1, 3]
4. 第三次插入：将6插入到已排序部分的末尾（因为6大于所有已排序元素），得到[2, 4, 5, 6 | 1, 3]
5. 第四次插入：将1插入到已排序部分的适当位置，得到[1, 2, 4, 5, 6 | 3]
6. 第五次插入：将3插入到已排序部分的适当位置，得到最终排序结果[1, 2, 3, 4, 5, 6]

• 性能分析

1. 时间复杂度：
   1. 最好情况：当输入数组已经有序时，时间复杂度为O(n)，因为每次插入操作都只需要比较一次。
   2. 最坏情况：当输入数组是逆序时，时间复杂度为O(n^2)，因为每次插入操作都需要比较n次（在已排序部分的末尾找到插入位置）。
   3. 平均情况：时间复杂度为O(n^2)。
2. 空间复杂度：插入排序只需要一个额外空间用于临时存储要插入的元素，所以空间复杂度是O(1)。

• 优点与缺点

1. 优点：
   1. 实现简单，易于理解和编写。
   2. 对于小规模序列或基本有序的序列排序效果较好。
2. 缺点：
   1. 对于大规模乱序序列的排序效率较低，时间复杂度较高。
   2. 算法的性能与输入数据的初始顺序有关，如果待排序序列接近有序，则算法性能较好；反之，性能较差。

四、快速排序（Quicksort）

• 算法原理

快速排序的核心原理是选择一个基准元素（pivot），将待排序数组划分为两个子数组，一个子数组包含所有小于基准的元素，另一个子数组包含所有大于基准的元素（注意，基准元素在其最后的排序数组中的位置就已经被确定），然后递归地对两个子数组进行快速排序，以此达到整个数组有序的目的。

• 实现步骤

1. 选择基准：从数组中选择一个元素作为基准元素。基准元素的选择有多种策略，如选择第一个元素、最后一个元素、中间元素或随机选择一个元素等。
2. 划分操作：通过一系列的比较和交换操作，使得小于基准的元素都在基准的左边，大于基准的元素都在基准的右边。这个过程称为划分（partition）。
3. 递归排序：递归地对划分出来的左右两个子数组进行快速排序。
4. 合并：由于快速排序是就地排序（in-place sort），在划分过程中已经实现了子数组的排序，因此不需要额外的合并步骤。

• 算法特性

1. 高效性：快速排序在平均情况下具有O(n log n)的时间复杂度，其中n是待排序数组的长度。这使得快速排序在处理大规模数据时非常高效。
2. 原地排序：快速排序不需要额外的存储空间来存放排序结果，因此空间复杂度为O(log n)（在递归调用栈中的空间开销）。然而，在最坏情况下，快速排序的空间复杂度可能会上升到O(n)，但这通常不会发生。
3. 不稳定性：快速排序不是稳定的排序算法。即，如果数组中有两个相等的元素，它们在排序后的相对位置可能会改变。
4. 分治策略：快速排序采用了分治策略，这使得算法在理解和实现上相对简单。

• 性能优化

1. 三向切分：在处理包含大量重复元素的数组时，可以采用三向切分（three-way partitioning）来优化快速排序的性能。三向切分将数组划分为三个部分：小于基准的元素、等于基准的元素和大于基准的元素。
2. 尾递归优化：在递归调用中，可以优化尾递归以减少递归调用栈的深度。例如，在每次递归调用时，可以先处理规模较小的子数组，然后递归处理规模较大的子数组。
3. 随机化基准选择：为了避免最坏情况的发生（如已经有序的数组），可以随机选择基准元素。这可以显著提高快速排序在平均情况下的性能。

• 应用场景

快速排序是一种通用的排序算法，适用于各种类型的数据，包括整数、浮点数、字符串等。它的应用场景非常广泛，如数据库索引构建、文件系统排序、编译器优化、财务交易排序、搜索引擎结果排序以及大数据处理等。特别是在大规模数据场景下，快速排序的性能优势非常明显。

假设一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。

此时，ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。

此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。

此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

此时，i=3，j=7，从第3位往后找，第一个比5大的数是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。

此时，i=4，j=7，从第7位往前找，第一个比5小的数是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。

此时，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序。

五、归并排序（Merge Sort）

• 算法原理

归并排序的主要思路是：将待排序序列分成若干个子序列，每个子序列是有序的（初始时，每个子序列只包含一个元素，因此可以认为它们是有序的）；然后再将这些有序子序列逐步合并，得到更大的有序序列，直到最后合并成一个完全有序的序列。

• 实现步骤

1. 分解：将待排序的n个元素的序列分成两个子序列，每个子序列包含n/2个元素（当n为偶数时）或接近n/2个元素（当n为奇数时）。
2. 解决：使用归并排序递归地排序两个子序列。
3. 合并：将两个已排序的子序列合并成一个最终的排序序列。

• 算法特性

1. 稳定性：归并排序是稳定的排序算法，即相同元素的相对顺序在排序后不会改变。
2. 时间复杂度：归并排序的最坏、平均和最佳时间复杂度均为O(n log n)，其中n是待排序序列的长度。这意味着归并排序能够提供一致的快速排序性能，不受输入数据初始顺序的影响。
3. 空间复杂度：归并排序需要额外的存储空间来存放合并过程中的临时数组，因此其空间复杂度为O(n)。

• 应用场景

1. 大数据集排序：归并排序非常适合处理大量数据的排序问题，尤其是当数据集无法一次性加载到内存中时，可以使用外部归并排序。
2. 并发编程：在多线程或分布式系统中，归并排序可以很容易地并行化。每个线程或进程可以独立地排序数据的一部分，然后合并结果。
3. 数据库系统：数据库管理系统中的排序操作经常使用归并排序，因为它可以提供稳定的排序结果，这对于数据库的完整性非常重要。
4. 文件排序：在需要对大量文件进行排序时，归并排序是一个很好的选择。文件可以分块读取到内存中，排序后再合并。

设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11；

逆序数为14；

六、堆排序（Heapsort）

堆排序的基本概念

堆排序的实现步骤

• 堆：堆是一种特殊的完全二叉树结构，分为大根堆和小根堆。大根堆要求每个节点的值都不小于其父节点的值，即堆顶元素为最大值；小根堆则要求每个节点的值都不大于其父节点的值，即堆顶元素为最小值。
• 堆排序：堆排序是利用堆这种数据结构所设计的一种排序算法。它首先将要排序的数列构造成一个堆，然后反复将堆顶元素（最大值或最小值）与末尾元素交换，并重新调整堆结构，直到整个数列有序。
• 建堆：将无序数组整理为堆。具体步骤为找到无序数组最后一个非叶子节点（也是最后一个父节点），随后对每一个非叶子节点都进行一次堆整理（下移操作），直到所有节点以下的子堆都已符合最小堆/最大堆的要求。
• 交换与调整：将堆的尾节点与堆的根节点交换，并将堆的大小往前挪一个单位（等同于移除原来的堆根节点）。然后从根节点开始，对新的堆进行堆调整，使其重新满足堆的性质。
• 重复步骤：重复上述交换与调整步骤，直到堆的大小为1，此时数组已完全排序。

堆排序的性质与特点

堆排序的应用场景

• 原地排序：堆排序不需要额外的存储空间来存储待排序的元素，它只需要一个与待排序元素数量相等的数组空间。
• 时间复杂度：堆排序的时间复杂度为O(n log n)，其中n是待排序元素的数量。这个复杂度在最好、最坏和平均情况下都是一致的，因此它的性能是稳定的。
• 不稳定性：堆排序是一种不稳定的排序算法，因为相同元素的相对位置可能会因为堆的调整而发生变化。
• 适用性：堆排序在处理大规模数据集时具有显著的优势，因为它在构建堆和调整堆的过程中是逐步进行的，不需要像快速排序那样递归地划分数据。
• 构建优先队列：堆排序是构建优先队列的一种常用方法。优先队列是一种特殊的队列，它可以按照元素的优先级对其进行排序，使得优先级最高的元素能够首先被取出。
• 处理大规模数据集：堆排序在处理大规模数据集时具有显著优势，因为它只需要维护部分数据的堆结构，而不需要将所有数据都加载到内存中进行排序。
• 查找最大（或最小）的K个元素：通过维护一个大小为K的最小堆（或最大堆），可以在O(n log K)的时间复杂度内找到最大（或最小）的K个元素。
• 图算法：堆排序在图算法中也有广泛的应用，例如最短路径算法Dijkstra和Prim的实现中就使用了最小堆来维护待选节点的集合，并选择优先级最高的节点进行处理。

七、希尔排序（Shell Sort）

基本思想

希尔排序的基本思想是将待排序的一组元素按一定间隔分成若干个子序列，分别进行插入排序。开始时设置的“间隔”较大，在每轮排序中将间隔逐步减小，直到“间隔”为1，此时进行最后一次插入排序，整个排序过程结束。

增量序列

在希尔排序中，选择的间隔序列称为增量序列。增量序列的选取对希尔排序的性能有较大影响。常用的增量序列有：

1. 希尔增量：最初由希尔提出，通常选择gap=n/2作为初始间隔，然后每次将间隔减半，直到间隔为1。即增量序列为{n/2, (n/2)/2, ..., 1}。
2. Hibbard增量：形如{1, 3, ..., 2^k-1}的增量序列。
3. Sedgewick增量：这是由Robert Sedgewick提出的一组增量序列，如{929, 505, 255, 127, ... , 9, 5, 1}等。

在实际应用中，可以根据待排序数据的规模和特点选择合适的增量序列。

排序过程

希尔排序的具体步骤如下：

1. 选择一个增量序列t1, t2, ..., tk，满足tk=1且tk-1>tk（k为增量序列的项数）。
2. 按照增量序列的个数k，对待排序序列进行k趟排序。
3. 每趟排序根据对应的增量ti（i=1, 2, ..., k），将待排序序列分割成若干个子序列，每个子序列包含下标间隔为ti的元素。
4. 对每个子序列分别进行插入排序。
5. 重复步骤3和4，直到增量为1时，对整个序列进行一次插入排序，此时排序完成。

性能分析

1. 时间复杂度：希尔排序的时间复杂度与增量序列的选择密切相关。对于常用的希尔增量，时间复杂度约为O(n2)之间，具体取决于数据的分布和规模。当数据规模较大时，希尔排序通常比直接插入排序要快得多。
2. 空间复杂度：希尔排序是原地排序算法，只需要O(1)的额外空间。
3. 稳定性：希尔排序是不稳定的排序算法。对于相同的两个数，可能由于分在不同的组中而导致它们的顺序发生变化。

应用场景

希尔排序适用于中等规模数据的排序，特别是当数据规模较大且部分有序时，希尔排序能够利用这种部分有序性进一步优化排序过程。此外，希尔排序在实时系统或需要较小内存占用的场景中也是一个合适的选择。

标签：25,排序,--,复杂度,元素,数组,序列,数据结构
From： https://blog.csdn.net/weixin_51933701/article/details/144338055