wordpress首页布局插件,巩义做网站优化,绵阳的网站建设公司哪家好,ui设计是怎么实现的一.排序的概念及引用
1.1排序的概念
排序是指将一组数据按照一定的规则重新排列的过程。排序的目的是为了使数据具有有序性#xff0c;便于查找、插入、删除等操作#xff0c;提高数据的组织和管理效率。
稳定性是指如果序列中存在相等元素#xff0c;在排序完成后#…一.排序的概念及引用
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;iarray.length;i) {int tmp array[i];int j i - 1;for (; j 0; j--) {if (tmp array[j]) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}public static void main(String[] args) {int[] array {27,15,9,18,28};System.out.println(原数组 Arrays.toString(array));sort.countSort(array);System.out.println(直接插入排序后 Arrays.toString(array));}
运行截图如下: 直接插入排序的优点:
直接插入排序虽然在大规模无序数据集合上的效率相对较低但它也有一些优点特别适用于特定的场景和数据集合包括
简单易实现直接插入排序是一种非常简单直观的排序算法易于理解和实现。它的算法思想直接反映在代码中不需要复杂的逻辑或额外的数据结构。原地排序直接插入排序是一种原地排序算法即它只需要使用原始数据集合所占用的内存空间不需要额外的存储空间。 稳定性直接插入排序是一种稳定的排序算法即相等元素的相对顺序不会改变。这在某些应用场景中很重要需要保持相等元素的相对位置关系。部分有序数据集合对于部分有序的数据集合直接插入排序的效率较高。它的比较次数和移动次数较少适合处理已经接近有序的数据。小规模数据集合对于小规模的数据集合直接插入排序表现良好。它的时间复杂度为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 array.length; i){ // 遍历数组从第一个间隔位置开始int tmp array[i]; // 当前元素int j i - gap; // 前一个间隔位置的索引for (; j 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 array.length; i) {int min i; // 当前最小值的索引for (int j i 1; j array.length; j) {// 在未排序区中找到比当前最小值更小的元素更新最小值的索引if (array[j] array[min]) {min j;}}swap(array, i, min); // 将最小值与待排序数组的第一个元素交换位置将最小值放到已排序区的末尾}
}public static void main(String[] args) {int[] array {84,83,88,87,61};System.out.println(原数组 Arrays.toString(array));selectSort(array);//调用直接选择排序方法System.out.println(直接选择排序后 Arrays.toString(array));}
运行截图如下: 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 right) {int minIndex left; // 当前未排序区的最小值索引int maxIndex left; // 当前未排序区的最大值索引for (int i left 1; i right; i) {// 在未排序区中找到最大值和最小值的索引if (array[i] array[maxIndex]) {maxIndex i;}if (array[i] array[minIndex]) {minIndex i;}}swap(array, minIndex, left); // 将最小值与未排序区的第一个元素交换位置if (maxIndex left) {maxIndex minIndex;}swap(array, maxIndex, right); // 将最大值与未排序区的最后一个元素交换位置left;right--;}
}public static void main(String[] args) {int[] array {84,83,88,87,61};System.out.println(原数组 Arrays.toString(array));selectSort2(array);//调用方法System.out.println(直接选择排序后 Arrays.toString(array));}
运行如下:
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.length; i) {boolean flag false; // 进行优化每一趟判断上一趟是否交换// 比如给的 1 2 3 4 5走了一遍发现有序最好的情况下为时间复杂度O(N)// 因为在每一趟排序中最大的元素都会冒泡到末尾所以下一趟排序可以减少一次遍历for (int j 0; j array.length - 1 - i; j) {if (array[j] 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 right) {// 从右边开始找到第一个小于基准元素的元素while (left right array[right] tmp) {right--;}// 从左边开始找到第一个大于基准元素的元素while (left right array[left] tmp) {left;}swap(array, left, right); // 交换找到的两个元素的位置// 交换之后又符合上面循环的条件了就又继续执行上面的while循环直到左右指针相遇}swap(array, i, left); // 将基准元素放到相遇位置即左指针所在位置return left; // 返回基准元素的位置
}private 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));quickSort(array);//调用快速排序方法System.out.println(快速排序后 Arrays.toString(array));}运行截图如下:
- 4.2.2快速排序挖坑法
基本思路:通过分治法Divide and Conquer来进行排序。其中挖坑法Partition是快速排序的一种常见实现方式。
快速排序挖坑法的步骤 选择一个基准元素pivot。通常情况下可以选择数组的第一个元素作为基准元素。 定义两个指针一个指向数组的起始位置一般为左指针记为left一个指向数组的末尾位置一般为右指针记为right。 通过移动指针将数组中小于基准元素的值放在左侧大于基准元素的值放在右侧形成一个“坑”。 交换左指针和右指针所指向的元素直到左指针和右指针相遇。 将基准元素放入最后一个形成的“坑”中。 通过递归的方式对左右两个子数组基准元素左侧和右侧的子数组进行快速排序。 重复以上步骤直到所有子数组都有序。
注意:实际上被 挖 走的元素不是真的没了,只是把原来的值给覆盖了
第一趟排序: 第二趟排序: 往下同理,就不一一展开了
参考代码:
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 partitionHole(array,start,end);// 对基准值左边的子数组进行快速排序quick(array,start,pivot-1);// 对基准值右边的子数组进行快速排序quick(array,pivot1,end);
}public static int partitionHole(int[] array,int left,int right){// 将最左边的元素作为基准值int tmp array[left];int i left;// 循环直到左指针和右指针相遇while (left right){// 移动右指针找到第一个小于基准值的元素while (left right array[right]tmp){right--;}// 将找到的小于基准值的元素放到左指针所在位置array[left] array[right];// 移动左指针找到第一个大于基准值的元素while (left right array[left]tmp){left;}// 将找到的大于基准值的元素放到右指针所在位置array[right] array[left];}// 将基准值放到最终的位置array[left] tmp;return left;
}public static void main(String[] args) {int[] array {7,32,1,6,8,5,3,14,4,21};System.out.println(原数组 Arrays.toString(array));quickSort(array);调用方法System.out.println(快速(挖坑法)排序后 Arrays.toString(array));}
运行截图: 4.2.3前后指针法
实现步骤如下: 首先选择数组的左边第一个元素作为基准值key并设定两个指针prev指向左边第一个元素的位置cur指向prev的后一个位置。 从cur位置开始逐个将当前元素与基准值key进行比较。如果当前元素arr[cur]小于key就将prev向后移动一位prev然后交换arr[cur]和arr[prev]的值确保小于基准值的元素都位于prev的左侧。 当cur指针遍历完整个数组cur right时结束一趟快速排序。此时将基准值key与arr[prev]进行交换将基准值放置到最终位置上。 接着对基准值左边和右边的子数组分别递归执行上述步骤直到完成整个数组的排序。
参考动图如下: 代码如下:
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 right) {// 如果当前元素小于基准值并且prev指针后移后的元素不等于当前元素则交换prev指针和cur指针的元素if (array[cur] array[left] array[prev] ! array[cur]) {swap(array, cur, prev);}cur;}// 将基准值放置到最终位置上swap(array, prev, left);return prev;}// 交换数组中两个元素的位置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 {7, 32, 1, 6, 8, 5, 3, 14, 4, 21};System.out.println(原数组 Arrays.toString(array));quickSort(array);System.out.println(快速(前后指针法)排序后 Arrays.toString(array));}
}
运行截图如下: 4.2.4快速排序的两个优化
优化一:三数取中法选key
三数取中法Median of Three是快速排序算法中一种用于选择基准元素的方法。在快速排序中选择合适的基准元素对算法的性能起着重要的作用。
三数取中法的思想是从待排序数组的开始、中间和末尾位置选择三个元素然后取这三个元素的中间值作为基准元素。通过选择中间值作为基准元素可以尽量保证基准元素接近数组的中间值从而更好地平衡划分,能够解有效决树的高度的问题但是无法解决栈溢出的问题。
使用三数取中法的步骤如下
找到待排序数组的开始、中间和末尾位置的索引start、mid、end。比较数组中这三个位置的元素大小并将它们排序确保 array[start] array[mid] array[end]。返回中间位置的元素作为基准元素。
参考代码如下:
public static int middleNum(int[] array,int left,int right){int mid (left right) / 2;if(array[left] array[right]){//比如 array[left] 3, array[right] 9if(array[mid] array[left]){//已知两数的大小关系中位数有三种情况return left;}else if(array[mid] array[right]){return right;}else{return mid;}}else{//比如 array[left] 9, array[right] 3if(array[mid] array[right]){return right;}else if(array[mid] array[left]){return left;}else {return mid;}}}
优化二:递归到小的子区间时可以考虑使用插入排序 当一组数组经过几趟排序后后面的数据越来越趋于有序后面的数据可以使用插入法加快速度,省下递归的次数。 而对于一颗二叉树而言往往最后面两层的结点数是最多的所以能省下下很多的递归次数。
参考代码:2.1直接插入排序 运用两个以上优化的代码 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;}//-----------------------------------------------------------//优化二//经过几趟排序后后面的数据越来越趋于有序后面的数据可以使用插入法加快速度,省下递归的次数//对于一颗二叉树而言往往最后面两层的结点数是最多的所以能省下下很多的递归次数if(end - start115){quickInsertSort(array,start,end);//后面直接使用插入return;//返回后面的不用在执行了}//-----------------------------------------------------------//-----------------------------------------------------------//优化一 - 三数选中法int index middleNum(array,start,end);//获得中位数下标swap(array,index,start);//和基数值交换//-----------------------------------------------------------int pivot partition(array,start,end);//该方法使用前后指针法quick(array,start,pivot-1);quick(array,pivot1,end);}//直接插入法:public static void quickInsertSort(int[] array,int left,int right){for(int i left1;iright;i) {int tmp array[i];int j i - 1;for (; j left; j--) {if (tmp array[j]) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}//三数取中法:
public static int middleNum(int[] array,int left,int right){int mid (left right) / 2;if(array[left] array[right]){//比如 array[left] 3, array[right] 9if(array[mid] array[left]){//已知两数的大小关系中位数有三种情况return left;}else if(array[mid] array[right]){return right;}else{return mid;}}else{//比如 array[left] 9, array[right] 3if(array[mid] array[right]){return right;}else 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 left1;while (cur right) {if(array[cur] array[left] array[prev] ! array[cur]) {swap(array,cur,prev);}cur;}swap(array,prev,left);return prev;}public static void main(String[] args) {int[] array {7,32,1,6,8,5,3,14,4,21};System.out.println(原数组 Arrays.toString(array));quickSort(array);//调用方法System.out.println(快速(前后指针法)优化排序后 Arrays.toString(array));}
运行截图如下: 4.2.5快速排序非递归
基本原理:使用栈模拟快速排序时我们可以把栈看作是一个待处理的任务列表。每个任务表示一个待排序的子数组范围。 1. 我们首先将整个数组的起始索引和结束索引作为第一个任务入栈。
2.进入循环直到栈为空为止 从栈中弹出一个任务表示要处理的子数组范围。 在这个范围内选择一个基准元素并将数组进行分区将小于等于基准的元素放在左边大于基准的元素放在右边。 如果基准的左侧还有未排序的元素我们将左侧子数组的起始索引和结束索引作为一个新任务入栈。 如果基准的右侧还有未排序的元素我们将右侧子数组的起始索引和结束索引作为一个新任务入栈。
3.循环结束后整个数组就完成了排序。
通过使用栈来存储待处理的任务我们可以模拟递归的过程但是避免了函数调用的开销。这样我们就能以非递归的方式实现快速排序算法。
下面举出视频解释
start作为数组首位置,end作为数组末位置按照使用快速排序挖坑法,先去left下标的元素作为privot的基准值left寻找比privot的较大值,right寻找比privot的较小值,找到后交换,直至相遇.相遇之后,分别左子组和右子组的首尾元素的下标放到栈上判断栈是否为空,不为空,出栈两个下标,第一个的出栈作为right的新下标,第二个出栈的作为left的新下标之后按如上步骤进行
注意:子组的长度要大于1,否则索引不用放入到栈中
1. 非递归排序第一步(加速) 2. 非递归排序最终步(加速版) 参考代码如下:
public static void quickSortNor(int[] array){int start 0;int end array.length - 1;StackInteger stack new Stack();int pivot partitionHole(array, start, end); // 使用挖坑法进行分区得到基准位置// 将初始任务入栈即整个数组的起始索引和结束索引if (pivot start 1) {stack.push(start);stack.push(pivot - 1);}if (pivot 1 end) {stack.push(pivot 1);stack.push(end);}// 循环处理栈中的任务直到栈为空while (!stack.isEmpty()) {end stack.pop();start stack.pop();pivot partitionHole(array, start, end); // 使用挖坑法进行分区得到基准位置// 将子数组的起始索引和结束索引入栈以便后续处理if (pivot start 1) {stack.push(start);stack.push(pivot - 1);}if (pivot 1 end) {stack.push(pivot 1);stack.push(end);}}
}/*** 使用挖坑法进行分区*/
public static int partitionHole(int[] array, int left, int right) {int tmp array[left];int i left;while (left right) {// 从右侧开始找到第一个小于基准的元素while (left right array[right] tmp) {right--;}array[left] array[right]; // 将找到的元素填入左侧的坑位// 从左侧开始找到第一个大于基准的元素while (left right array[left] tmp) {left;}array[right] array[left]; // 将找到的元素填入右侧的坑位}array[left] tmp; // 将基准元素放入最终的坑位return left; // 返回基准位置
}public static void main(String[] args) {int[] array {6,1,2,7,9,3,4,5,10,8}};System.out.println(原数组 Arrays.toString(array));quickSortNor(array);System.out.println(快速(非递归)优化排序后 Arrays.toString(array));
}运行截图如下: 快速排序是一种常用的排序算法具有以下特性
时间复杂度平均情况下快速排序的时间复杂度为O(nlogn)其中n是待排序数组的长度。最坏情况下当选择的基准元素不平衡时例如已有序数组作为输入时间复杂度可达到O(n^2)。但通过优化算法和随机选择基准元素可以大大降低最坏情况出现的概率。不稳定排序快速排序是一种不稳定的排序算法意味着相等元素的相对顺序在排序后可能会发生改变。 分治算法快速排序使用分治算法的思想将原始数组分割为较小的子数组然后分别对子数组进行排序最后将排序好的子数组进行合并以达到整个数组有序的目的。 递归实现通常情况下快速排序使用递归来实现通过不断地递归调用自身来处理子数组。每次递归调用将数组分为两部分直到子数组的长度为1或0时停止递归。优化方法为了提高快速排序的性能可以采取一些优化方法如随机选择基准元素、三数取中法选择基准元素、使用插入排序优化小规模子数组等。
快速排序的空间复杂度主要取决于递归调用的栈空间和额外的辅助空间
栈空间在递归实现的快速排序中每次递归调用都会将一部分数组分割为子数组并将子数组的起始索引和结束索引入栈。这些递归调用需要使用栈来保存函数调用的上下文信息包括参数、局部变量和返回地址等。因此快速排序的空间复杂度取决于递归调用的深度即递归树的高度。在最坏情况下递归树的高度可以达到O(n)因此快速排序的最坏空间复杂度为O(n)。辅助空间快速排序通常需要一些额外的辅助空间来进行分区操作。常见的方法是选择一个基准元素并将小于等于基准的元素放在左侧大于基准的元素放在右侧。这个过程需要使用额外的空间来存储临时变量、交换元素等操作。因此快速排序的辅助空间复杂度为O(logn)取决于递归调用的深度。
总结起来快速排序是一种高效的排序算法具有原地排序、分治算法、平均时间复杂度为O(nlogn)等特性。然而最坏情况下的时间复杂度为O(n^2)且为不稳定排序算法。通过优化方法可以提高快速排序的效率和稳定性。
4.3归并排序
归并排序Merge Sort是一种常用的排序算法它基于分治Divide and Conquer的思想将一个大问题分解为若干个小问题然后将小问题的解合并起来得到整体的解。归并排序的主要步骤包括分解、合并和排序。
以下是归并排序的一般实现步骤 分解将待排序的数组递归地分解为两个子数组直到子数组的长度为1或0时停止递归。 合并将两个有序的子数组合并成一个有序的数组。合并过程中需要创建一个临时数组来存储合并结果。 排序通过不断地递归调用分解和合并步骤将子数组排序并合并直到最终得到完整的有序数组。
参考动图:1.5 归并排序 | 菜鸟教程 (runoob.com) 参考图: 参考代码:
public static void mergeSort(int[] array) {mergeSortFun(array, 0, array.length - 1);
}private static void mergeSortFun(int[] array, int start, int end) {if (start end) {return; // 如果起始索引大于等于结束索引表示子数组长度为1或0不需要排序直接返回}int mid (start end) / 2; // 计算中间索引将数组分为两部分mergeSortFun(array, start, mid); // 对左半部分进行归并排序mergeSortFun(array, mid 1, end); // 对右半部分进行归并排序merge(array, start, mid, end); // 合并左右两部分
}private static void merge(int[] array, int left, int mid, int right) {int s1 left; // 左半部分的起始索引int e1 mid; // 左半部分的结束索引int s2 mid 1; // 右半部分的起始索引int e2 right; // 右半部分的结束索引// 定义一个新数组来存储合并结果int[] tmpArr new int[right - left 1];int k 0; // tmpArr的下标// 同时满足条件时证明两个归并段都还有数据while (s1 e1 s2 e2) {if (array[s1] array[s2]) {tmpArr[k] array[s1]; // 将左半部分的元素放入tmpArr并移动相应索引} else {tmpArr[k] array[s2]; // 将右半部分的元素放入tmpArr并移动相应索引}}// 处理剩余的元素若左半部分还有剩余则将剩余元素放入tmpArrwhile (s1 e1) {tmpArr[k] array[s1];}// 处理剩余的元素若右半部分还有剩余则将剩余元素放入tmpArrwhile (s2 e2) {tmpArr[k] array[s2];}// 将排好序的tmpArr中的元素拷贝回原始数组array中for (int i 0; i tmpArr.length; i) {array[i left] tmpArr[i]; // 注意需要加上偏移量left}
}//该段代码用非递归的方式,了解即可.//非递归归并public static void mergeSortNor(int[] array){int gap 1;while (gap array.length){//循环一个,两个,四个,八个...开始for (int i 0; i array.length; igap*2) {int left i;int mid left gap - 1; // 有可能会越界//比如有五个元素 最后一个元素下标为4即left 4,mid 42-1 5int right midgap;// 有可能会越界,同理if(mid array.length){//如果越界就把元素归还最后一个下标mid array.length-1;}if(right array.length){right array.length-1;}merge(array,left,mid,right);}gap*2;}}public static void main(String[] args) {int[] array {6,1,2,7,9,3,4,5,10,8};System.out.println(原数组 Arrays.toString(array));mergeSort(array);System.out.println(快速(前后指针法)优化排序后 Arrays.toString(array));}
运行截图如下: 归并排序的特点可以总结如下
稳定性归并排序是一种稳定的排序算法即相等元素的相对顺序在排序后保持不变。分治思想归并排序使用分治策略将原始数组分解为较小的子数组然后分别对子数组进行排序最后将排序好的子数组合并成一个有序数组。时间复杂度归并排序的时间复杂度是O(n log n)其中n是数组的长度。这是一种较为高效的排序算法尤其适用于大规模数据的排序。空间复杂度归并排序需要额外的空间来存储临时数组其空间复杂度为O(n)其中n是数组的长度。这使得归并排序在对大规模数据进行排序时可能需要较多的内存空间。 适用性归并排序对各种数据类型都适用并且对于链式存储结构也可以进行排序。由于归并排序的稳定性和可预测的性能它在实际应用中被广泛使用。缺点归并排序需要额外的空间来存储临时数组这增加了空间复杂度。此外在实现时需要涉及到递归操作可能会导致函数调用的开销。
总之归并排序是一种高效且稳定的排序算法适用于各种数据类型。它的主要思想是分治通过将数组分解为较小的子数组并递归地排序和合并最终得到完整的有序数组。 外部排序排序过程需要在磁盘等外部存储进行的排序 前提内存只有 1G 需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序 先把文件切分成 200 份每个 512 M 分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以 进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了 五.其他排序
除了上面提到的排序,还可以了解其他的排序.
计数排序:计数排序 - 知乎 (zhihu.com)
基数排序:1.10 基数排序 | 菜鸟教程 (runoob.com)
桶排序:【排序】图解桶排序_桶排序图解-CSDN博客 结语:
总的来说选择合适的排序算法取决于待排序数据的规模、特性以及排序的要求。在实际应用中我们需要根据具体情况选择合适的算法以获得最佳的排序性能。
通过了解和掌握不同的排序算法我们可以更好地理解数据结构的基础原理并在实际开发中选择最合适的排序方法。希望本文对您在数据结构排序方面的学习和实践有所帮助。
感谢您阅读本文如果您有任何问题或意见请随时在评论区分享。
