“从根到叶：深入理解排序数据结构“
一.排序的概念及引用
1.1排序的概念
排序是指将一组数据按照一定的规则重新排列的过程。排序的目的是为了使数据具有有序性，便于查找、插入、删除等操作，提高数据的组织和管理效率。
稳定性是指如果序列中存在相等元素，在排序完成后，相等元素之间的相对顺序是否被保持不变。
以下是一些常见的内部排序算法：
-
冒泡排序（Bubble Sort）：比较相邻的两个元素，如果顺序错误就交换它们，依次比较直到整个序列排序完成。
-
选择排序（Selection Sort）：每次从未排序的部分选择最小（或最大）的元素，并将其放在已排序部分的末尾。
-
插入排序（Insertion Sort）：从未排序的部分逐个取出元素，将其插入已排序部分的适当位置。
-
快速排序（Quick Sort）：选择一个基准元素，将比基准元素小的元素放在它的左边，比基准元素大的元素放在它的右边，然后递归地对左右两个部分进行快速排序。
-
归并排序（Merge Sort）：将序列递归地分成两个子序列，分别对子序列进行排序，然后将已排序的子序列合并成一个有序序列。
-
堆排序（Heap Sort）：将待排序的序列构建成一个最大堆（或最小堆），然后依次从堆顶取出最大（或最小）元素，再调整堆。
外部排序：一种用于排序大规模数据集合的算法，其中数据无法一次性全部加载到内存中进行操作，而需要借助外部存储设备（如硬盘）进行排序。外部排序的目标是将数据划分为适当大小的块，然后在内存中对这些块进行排序，最后将排序好的块写回到外部存储设备中，并进行合并以得到最终有序的结果。
常见的外部排序算法：
- 多路归并排序（Multiway Merge Sort）：该算法将大规模数据集合划分成多个较小的块，并将这些块分别加载到内存中进行排序。然后，使用多路归并的方式将排序好的块逐个合并成一个有序序列。多路归并排序可以通过多次迭代进行，直到得到最终的有序结果。
1.2排序的运用
排序在计算机科学和日常生活中有广泛的运用。以下是一些常见的排序的运用场景：
- 数据库系统：数据库中的查询操作通常需要对结果进行排序，以便按照特定的排序条件返回有序的数据集合。排序可以提高查询效率和结果的可读性。
- 搜索引擎：搜索引擎需要对搜索结果进行排序，以根据相关性或其他指标将最相关的结果排在前面，提供更好的搜索体验。
- 数据分析：在数据分析领域，对大规模数据集进行排序可以帮助发现数据的模式、趋势和异常。排序可以用于排序算法的性能分析，以及处理大数据集合的前N个元素或者Top K问题。
- 赛程排名：在体育比赛、竞赛或其他排名制度中，通过对参与者的成绩进行排序，可以确定他们在排名中的位置。例如，排行榜、积分榜、奖牌榜等。
- 财务报表：在财务领域，对公司的财务报表进行排序可以帮助进行财务分析和比较，例如按照收入、利润、市值等进行排序。
- 文件列表：在文件系统中，对文件列表按照名称、大小、修改日期等进行排序，可以方便用户查找和管理文件。
- 排座位：在活动、会议或教室中，对参与者进行排序可以确定他们的座位位置，以便组织和管理。
这只是一小部分排序的运用场景，实际上排序在计算机科学和日常生活中有着广泛的应用。排序算法的性能和效率对于处理大规模数据集合和提供良好的用户体验至关重要。根据具体的应用场景和需求，选择适当的排序算法和优化策略可以提高排序的效果和性能。
二.插入排序
基本思想: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列 。 实际中我们玩扑克牌时，就用了插入排序的思想。想象一下，你手里拿着一副乱序的扑克牌，想要将它们按照从小到大的顺序排列。你会从左边开始，一张一张地拿起牌，然后将它们插入到已经有序的牌堆中的正确位置。
开始的时候，你只有一张牌，所以它已经是有序的。接着，你拿起第二张牌，将它与第一张牌进行比较。如果第二张牌比第一张牌小，你就将第二张牌插入到第一张牌的左边；否则，你将第二张牌放在第一张牌的右边。
然后，你拿起第三张牌，将它与前面的已排序牌进行比较。如果第三张牌比前面的牌都小，你就将第三张牌插入到已排序牌的最左边；否则，你从右向左依次比较，找到第三张牌应该插入的位置。
你会一直重复这个过程，每次拿起一张新的牌，找到它应该插入的位置，并将它插入到正确的位置。最终，当你拿起最后一张牌并插入到适当的位置后，所有的牌就都排好序了。
插入排序的基本思想就是通过不断地将未排序的元素插入到已排序的序列中，逐步构建有序序列。这个过程类似于整理扑克牌时的插入动作，因此称之为插入排序。
插入排序的适用场景：
插入排序在以下情况下适用：
-
小规模数据集：插入排序对于小规模的数据集合表现良好。当待排序的数据量较小时，插入排序的时间复杂度较低，并且实现简单，适合用于排序少量元素的情况。
-
部分有序的数据集合：如果待排序的数据集合已经部分有序，插入排序的效率会比较高。在这种情况下，插入排序的比较次数和移动次数会减少，因为只需要将较小的元素插入到已排序的部分中。
-
数据集合基本有序，但有少量逆序对：如果待排序的数据集合基本有序，但有少量逆序对（相邻元素大小顺序相反），插入排序的效率还是较高的。因为每次插入操作只需要将一个元素移动到正确的位置，逆序对的数量较少，整体比较和移动的次数相对较少。
-
需要稳定排序算法：插入排序是一种稳定的排序算法，即相等元素的相对顺序不会改变。在某些应用场景中，需要保持相等元素的相对顺序，这时插入排序是一个合适的选择。
注意：对于大规模无序的数据集合，插入排序的效率相对较低，性能不如快速排序、归并排序等具有较好平均时间复杂度的算法。在这种情况下，可以选择其他更高效的排序算法来处理大规模数据集合。
2.1直接插入排序
它的基本思想是将待排序的序列分为已排序部分和未排序部分，每次从未排序部分选择一个元素，插入到已排序部分的适当位置，直到所有元素都被插入到已排序部分并完成排序。
以下是直接插入排序的具体步骤：
- 假设待排序序列为arr，长度为n。
- 从索引为1的位置开始，将arr[1]作为已排序部分。
- 从索引为2的位置开始迭代，将arr[i]与已排序部分中的元素比较。
- 如果arr[i]小于已排序部分的某个元素arr[j]，则将arr[i]插入到arr[j]之前，并将arr[j]及其后面的元素后移一位。
- 重复步骤4，直到找到arr[i]的正确位置或者已经比较完已排序部分的所有元素。
- 重复步骤2~5，直到所有元素都被插入到已排序部分并完成排序。
该图来源：1.3 插入排序 | 菜鸟教程 (runoob.com)
举例子如下:
假设现在你有一组待排序的arr数组
第一次插入
第二次插入:
第三次插入:
第四次插入:
完成排序
相关代码如下:
private static void insertSort(int[] array){ for(int i = 1;i= 0; j--) { if (tmp运行截图如下:
直接插入排序的优点:
直接插入排序虽然在大规模无序数据集合上的效率相对较低，但它也有一些优点，特别适用于特定的场景和数据集合，包括：
- 简单易实现：直接插入排序是一种非常简单直观的排序算法，易于理解和实现。它的算法思想直接反映在代码中，不需要复杂的逻辑或额外的数据结构。
- 原地排序：直接插入排序是一种原地排序算法，即它只需要使用原始数据集合所占用的内存空间，不需要额外的存储空间。
- 稳定性：直接插入排序是一种稳定的排序算法，即相等元素的相对顺序不会改变。这在某些应用场景中很重要，需要保持相等元素的相对位置关系。
- 部分有序数据集合：对于部分有序的数据集合，直接插入排序的效率较高。它的比较次数和移动次数较少，适合处理已经接近有序的数据。
- 小规模数据集合：对于小规模的数据集合，直接插入排序表现良好。它的时间复杂度为O(n^2)，但在数据量较小的情况下，这个复杂度仍然是可接受的。
直接插入的时间和空间复杂度
-
时间复杂度：直接插入排序的平均时间复杂度为O(n^2)，其中n是待排序序列的长度。在最坏情况下，即待排序序列完全逆序时，时间复杂度为O(n^2)。在最好情况下，即待排序序列已经有序时，时间复杂度可以降低到O(n)。平均情况下，直接插入排序的比较次数和移动次数都是n(n-1)/4，因此时间复杂度为O(n^2)。
-
空间复杂度：直接插入排序是一种原地排序算法，它只需要使用原始数据集合所占用的内存空间，不需要额外的存储空间。因此，它的空间复杂度为O(1)，即常数级别的空间复杂度。
- 元素集合越接近有序，直接插入排序
- 算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2.2希尔排序
基本思想:希尔排序法又称缩小增量法,希尔排序（Shell Sort）是一种排序算法，它是插入排序的一种改进版本。希尔排序的基本思想是将待排序的数组元素按照一定的间隔进行分组，对每组进行插入排序，随着间隔的逐渐缩小，每组包含的元素越来越多，当间隔缩小到1时，整个数组就被分成一组，此时进行最后一次插入排序后，排序完成.
希尔排序的步骤如下：
- 选择一个间隔序列（通常是按照一定规则确定的），将待排序的数组按照间隔分成多个子序列。
- 对每个子序列进行插入排序，即从第二个元素开始，与前面的元素进行比较并插入到正确的位置。
- 逐步缩小间隔，重复进行第2步操作，直到间隔缩小到1。
- 进行最后一次插入排序，此时整个数组已经基本有序，只需进行少量的比较和移动操作即可完成排序。
该图从网上搜寻,如有侵权,请联系作者调整!
举例子解释:
假设有一组未排序的数组:
其中gap 作为元素间隔的个数
相关代码如下:public static void shellSort(int[] arr){ int gap = arr.length; // 初始化间隔为数组长度 while (gap > 1){ // 当间隔大于1时继续循环 gap = gap/2; // 缩小间隔 shell(arr, gap); // 调用shell方法进行分组插入排序 } } public static void shell(int[] array, int gap){ for (int i = gap; i = 0; j -= gap){ // 从后往前，比较当前元素与前一个间隔位置的元素 if (array[j] > tmp){ // 如果前一个间隔位置的元素大于当前元素 array[j + gap] = array[j]; // 将前一个元素后移 } else { break; // 如果前一个元素小于等于当前元素，则结束循环 } } array[j + gap] = tmp; // 插入当前元素到正确的位置 } } //主函数测试 public static void main(String[] args) { int[] array = {9,1,2,5,7,4,8,6,3,5}; System.out.println("原数组 "+Arrays.toString(array)); sort.shellSort(array);//调用希尔排序方法 System.out.println("希尔排序后 "+Arrays.toString(array)); }运行截图如下:
希尔排序的优点:
-
改进的插入排序：希尔排序是插入排序的改进版本。通过分组插入排序的方式，可以在每一轮排序中将较远距离的元素移动到正确的位置，从而减少了元素的比较和交换次数。
-
不稳定排序：希尔排序是一种不稳定的排序算法，即相同值的元素在排序后的相对位置可能发生变化。这是因为希尔排序是通过间隔分组进行排序，相同值的元素可能被分到不同的组中，导致它们之间的相对顺序发生改变。
-
适用于大规模数据：希尔排序相对于简单的插入排序在大规模数据排序方面具有一定的优势。由于它可以通过缩小间隔的方式进行预排序，可以减少后续排序所需的比较和交换次数，从而提高排序效率。
-
不需要额外的存储空间：希尔排序是一种原地排序算法，不需要额外的存储空间来存储临时数据。它通过在原始数组上进行元素的比较和交换来实现排序。
希尔排序的时间复杂度和空间复杂度
-
时间复杂度：希尔排序的时间复杂度取决于间隔序列的选择。在最坏的情况下，希尔排序的时间复杂度为O(n^2)，其中n是待排序数组的长度。这种情况发生在间隔序列不好的情况下，例如使用常规的希尔序列（例如，gap = n/2, gap = gap/2）。。
-
空间复杂度：希尔排序是一种原地排序算法，因此它的空间复杂度是O(1)，即不需要额外的存储空间来存储临时数据。希尔排序通过在原始数组上进行元素的比较和交换来实现排序，不会使用额外的内存空间。
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定.
- 稳定性：不稳定
三.选择排序
选择排序的基本思想:每次从未排序区中选择最小（或最大）的元素，放入已排序区的末尾。通过不断缩小未排序区的范围，逐步将元素放置在正确的位置上，最终完成排序。选择排序是一种不稳定的排序算法，因为交换元素的操作可能改变相同元素的相对顺序。常见的选择排序有直接选择排序和堆排序
3.1直接选择排序
选择排序的具体步骤如下：
-
遍历待排序数组，将第一个元素标记为当前最小值。
-
从第二个元素开始，依次与当前最小值进行比较，找到更小的元素，更新最小值的索引。
-
在遍历过程中，如果找到比当前最小值更小的元素，则更新最小值的索引。
-
遍历完成后，将最小值与待排序数组的第一个元素交换位置，将最小值放到已排序区的末尾。
-
已排序区的长度增加1，未排序区的长度减少1。
-
重复步骤2到步骤5，直到所有元素都被放入已排序区为止。
举例子如下:
你有一组未排序的数组:84,83,88,87,61
整体逻辑:
- min存放最小值下标,
- j 下标走完后,min存放的下标就和 i 下标进行交换(用循环进行)
- 然后i++ j--,,min更新为当前 i 位置的下标
- 继续往后寻找最小值元素的下标.
如下图所示:
第一次排序:
第二次排序:
第三次排序:
第四次排序完成:
参考动图入下:
参考代码如下:
public static void swap(int[] array, int i, int j) { // 交换数组中索引为i和j的两个元素的位置 int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void selectSort(int[] array) { for (int i = 0; i运行截图如下:
3.2直接选择排序优化
基本思路如下：
-
初始化左指针 left 为数组的起始位置，右指针 right 为数组的末尾位置。
-
在每一轮循环中，首先找到当前未排序区的最小值和最大值的索引，分别用 minIndex 和 maxIndex 记录。
-
将最小值与未排序区的第一个元素进行交换，将最小值放到已排序区的末尾。
-
检查最大值的索引是否等于 left，如果是，则更新 maxIndex 为 minIndex，以防止最大值被交换到已排序区的末尾。
-
将最大值与未排序区的最后一个元素进行交换，将最大值放到已排序区的起始位置。
-
左指针 left 向右移动一位，右指针 right 向左移动一位，缩小未排序区的范围。
-
重复步骤2到步骤6，直到未排序区为空，所有元素都被放入已排序区。
举例子解释:
你有一组未排序的数组:84,83,88,87,61
第一次排序:
第二次排序:
完成排序参考代码如下:
public static void selectSort2(int[] array) { int left = 0; int right = array.length - 1; while (left运行如下:
z注意:
优化后的选择排序算法在时间复杂度上与常规的选择排序算法相同，都是O(n^2)，其中n是待排序数组的长度。
无论是常规选择排序还是优化后的选择排序，都包含两层嵌套循环。外层循环用于遍历未排序区域，内层循环用于找到未排序区域的最小值和最大值。在每一次循环中，需要进行一次比较和可能的一次交换操作。
因此，选择排序的时间复杂度始终为O(n^2)，无论是否进行了优化。优化后的选择排序算法只是通过减少交换次数来提高了实际执行的时间，但并没有改变其基本的时间复杂度。
3.3堆排序
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。 具体例子如下 :
该小节部分可以参考:
“从根到叶：深入理解堆数据结构“-CSDN博客
堆排序特性总结:
-
不稳定性：堆排序是一种不稳定的排序算法。在构建最大堆和进行堆调整的过程中，元素的相对顺序可能会发生变化。例如，对于具有相同值的元素，它们在最大堆中的相对顺序可能会被调整，导致排序后的结果不稳定。
-
时间复杂度：堆排序的时间复杂度为O(n log n)，其中n是待排序数组的长度。构建最大堆的过程需要O(n)的时间复杂度，而进行堆调整的过程需要进行n-1次下沉操作，每次下沉的时间复杂度为O(log n)。因此，总体时间复杂度为O(n log n)。
-
空间复杂度:堆排序算法只需要常数级别的额外空间来存储一些临时变量和指针，如循环索引和临时交换变量。这些额外空间的使用量不随输入规模的增长而增加，因此堆排序的空间复杂度为O(1)。
四.交换排序
基本思想 ：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。4.1冒泡排序
基本思想:通过比较相邻元素的大小并交换它们的位置，使得较大的元素逐渐“冒泡”到数组的末尾。
该图来源:1.1 冒泡排序 | 菜鸟教程 (runoob.com)
举例子解释:
假设你现在有未排序的代码:5, 3, 8, 2, 1
首先,我们进行第一次排序:
第二次排序:
同理,由此类推可排序完成
参考代码:
public static void bubbleSort(int[] array) { for (int i = 0; i array[j + 1]) { swap(array, j, j + 1); // 交换相邻元素的位置 flag = true; // 标记本趟排序有交换操作 } } if (!flag) { // 如果本趟排序没有交换操作，说明数组已经有序，提前结束排序 break; } } } public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { int[] array = {5, 3, 8, 2, 1}; System.out.println("原数组 "+Arrays.toString(array)); bubbleSort(array); System.out.println("冒泡排序后 "+Arrays.toString(array)); }运行如下:
冒泡排序特点:
冒泡排序具有以下特点：
-
时间复杂度：冒泡排序的平均和最坏情况下的时间复杂度都为 O(n^2)，其中 n 是待排序数组的长度。这是因为每一趟排序需要比较 n-1 个相邻元素，并且需要进行 n-1-i 次遍历，共需要进行 (n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2 次比较和交换操作。
-
空间复杂度: 冒泡排序的空间复杂度为 O(1)，即不需要额外的空间来存储数据。因为只需要使用常数级别的额外空间来存储一些临时变量，例如用于交换元素的临时变量。无论待排序数组的规模如何增大，所需的额外空间都保持不变。
-
稳定性：冒泡排序是一种稳定的排序算法，即相同的元素在排序后的相对顺序保持不变。只有相邻元素的比较和交换操作，不会改变相同元素的相对位置。
-
最好情况下的时间复杂度：当待排序数组已经有序时，冒泡排序只需进行一趟遍历，没有发生元素交换，时间复杂度为 O(n)，这是冒泡排序的最好情况。
4.2快速排序
4.2.1快递排序Hoare
基本思想:
-
选择一个基准元素：从待排序的数组中选择一个基准元素。通常情况下，可以选择数组的第一个元素、最后一个元素或者中间元素作为基准。
-
分区操作：将数组中的其他元素按照与基准元素的大小关系，划分为两个子数组，一个小于基准元素的子数组，一个大于基准元素的子数组。这个过程称为分区操作。
-
递归排序：对划分得到的两个子数组，分别进行递归调用快速排序算法。即对小于基准元素的子数组和大于基准元素的子数组进行快速排序。
-
合并结果：将经过排序的子数组合并，得到最终的有序数组。
具体步骤如下:
- 选择基准元素。
- 将数组中小于基准元素的元素移到基准元素的左边，大于基准元素的元素移到基准元素的右边。
- 对基准元素左边的子数组和右边的子数组分别递归调用快速排序算法。
- 合并排序后的左子数组、基准元素和右子数组。
参考动图:
图片来源:1.6 快速排序 | 菜鸟教程 (runoob.com)
举例子解释:
初始数组：[5, 2, 9, 1, 7, 6, 3]
第一步：选择基准元素5
第二步：进行分区操作，将小于基准元素的数放在左边，大于基准元素的数放在右边。
第三步,交换基准元素下标后,基准元素左边和右边分别进行递归操作,重新选择基准元素
第四步:合并排序后的子数组以及基准元素即可
参考代码如下:
public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } private static void quick(int[] array, int start, int end) { if (start >= end) { return; // 基准条件，如果起始索引大于等于结束索引，则表示数组已经有序，直接返回 } int pivot = partitionHoare(array, start, end); // 获取基准元素的位置 quick(array, start, pivot - 1); // 对基准元素左边的子数组进行快速排序 quick(array, pivot + 1, end); // 对基准元素右边的子数组进行快速排序 } public static int partitionHoare(int[] array, int left, int right) { int tmp = array[left]; // 将左边第一个元素作为基准元素 int i = left; while (left = tmp) { right--; } // 从左边开始找到第一个大于基准元素的元素 while (left =tmp){ right--; } // 将找到的小于基准值的元素放到左指针所在位置 array[left] = array[right]; // 移动左指针，找到第一个大于基准值的元素 while (left -
-
接着，对基准值左边和右边的子数组分别递归执行上述步骤，直到完成整个数组的排序。
参考动图如下:
代码如下:
import java.util.Arrays; public class QuickSort { public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } private static void quick(int[] array, int start, int end) { // 终止条件：子数组长度为0或1时直接返回 if (start >= end) { return; } // 使用前后指针法进行划分，获取基准元素的位置 int pivot = partition(array, start, end); // 递归地对基准元素左边的子数组进行排序 quick(array, start, pivot - 1); // 递归地对基准元素右边的子数组进行排序 quick(array, pivot + 1, end); } // 前后指针法进行划分 public static int partition(int[] array, int left, int right) { int prev = left; int cur = left + 1; while (cur = end) { return; } //----------------------------------------------------------- //优化二 //经过几趟排序后，后面的数据越来越趋于有序，后面的数据可以使用插入法，加快速度,省下递归的次数 //对于一颗二叉树而言，往往最后面两层的结点数是最多的，所以能省下下很多的递归次数 if(end - start+1 三数选中法 int index = middleNum(array,start,end);//获得中位数下标 swap(array,index,start);//和基数值交换 //----------------------------------------------------------- int pivot = partition(array,start,end);//该方法使用前后指针法 quick(array,start,pivot-1); quick(array,pivot+1,end); } //直接插入法: public static void quickInsertSort(int[] array,int left,int right){ for(int i = left+1;i= left; j--) { if (tmp array[right]){ return right; }else{ return mid; } } else{//比如 array[left] = 9, array[right] = 3 if(array[mid] array[left]){ return left; }else { return mid; } } } //前后指针法 public static int partition(int[] array,int left,int right){ int prev = left ; int cur = left+1; while (cur start + 1) { stack.push(start); stack.push(pivot - 1); } if (pivot + 1 start + 1) { stack.push(start); stack.push(pivot - 1); } if (pivot + 1 = tmp) { right--; } array[left] = array[right]; // 将找到的元素填入左侧的坑位 // 从左侧开始，找到第一个大于基准的元素 while (left -
还没有评论，来说两句吧...