做卷闸门网站有用吗,做移动网站点击软件下载,长春做网站 长春万网,php手机网站制作文章目录 小程一言直接插入排序步骤举例复杂度分析应用场景实际举例代码实现 希尔排序步骤举例复杂度分析应用场景实际举例代码实现 堆排序步骤举例复杂度分析应用场景实际举例代码实现 小程一言
这篇文章是在排序进行曲1.0之后的续讲#xff0c;
由于在上一篇讲的排序的基本… 文章目录 小程一言直接插入排序步骤举例复杂度分析应用场景实际举例代码实现 希尔排序步骤举例复杂度分析应用场景实际举例代码实现 堆排序步骤举例复杂度分析应用场景实际举例代码实现 小程一言
这篇文章是在排序进行曲1.0之后的续讲
由于在上一篇讲的排序的基本概念与分类所以这篇主要是对几个
简单的排序进行细致的分析有直接插入排序、希尔排序以及堆排序。直接插入排序
直接插入排序是一种简单直观的排序算法它的基本思想是将待排序的元素依次插入到已排序的序列中的合适
位置从而逐步形成有序序列。步骤
1、将待排序的元素序列分为已排序区和未排序区。一开始已排序区只有一个元素就是待排序序列的第一个元素。
2、从未排序区取出第一个元素将其与已排序区的元素逐个比较找到合适的位置插入。
3、比较的过程是从已排序区的最后一个元素开始如果该元素大于待插入元素则将该元素后移一位直到找到一个小于等于待插入元素的元素位置。
4、将待插入元素插入到找到的位置后已排序区的元素个数加一。
5、重复步骤2~4直到未排序区的元素全部插入到已排序区。举例
原始序列5 3 8 6 4第一轮插入3 5 8 6 4第二轮插入3 5 6 8 4第三轮插入3 4 5 6 8通过例子可以看出直接插入排序每次将一个元素插入到已排序序列中的合适位置通过不断地插入操作最终将序列排序完成。复杂度分析
直接插入排序的时间复杂度为O(n^2)其中n是待排序序列的长度。直接插入排序的最好情况时间复杂度为O(n)即当待排序序列已经有序时只需要比较n-1次即可完成排序。最坏情况时间复杂度为O(n^2)即当待排序序列逆序排列时需要比较和移动的次数最多。平均情况下直接插入排序的时间复杂度也是O(n^2)。直接插入排序的空间复杂度为O(1)即只需要常数级别的额外空间。直接插入排序是一种稳定的排序算法即相等元素的相对顺序在排序前后不会改变。应用场景
小规模数据排序直接插入排序对于小规模的数据排序效果较好因为它的时间复杂度为O(n^2)在数据规模较小的情况下其性能优于其他复杂度较高的排序算法。例如对于一个包含100个元素的数组进行排序直接插入排序的效率较高。部分有序数据排序如果待排序的数据已经部分有序即每个元素距离它的最终位置不远那么直接插入排序的效果会很好。这是因为直接插入排序每次将一个元素插入到已经有序的部分中插入的操作比较快速。例如对于一个近乎有序的数组进行排序直接插入排序的效率较高。数据量较小且基本有序的在线排序直接插入排序可以在不断接收新数据的情况下实时对数据进行排序。例如一个在线的股票交易系统需要对新到达的交易数据进行排序直接插入排序可以满足实时性的要求。实际举例
假设有一个学生成绩的数组需要按照成绩从低到高进行排序。可以使用直接插入排序来实现。首先将第一个元素视为有序的部分然后从第二个元素开始逐个将元素插入到已经有序的部分中。具体的操作是从第二个元素开始将其与已经有序的部分比较找到合适的位置插入然后再将下一个元素插入直到所有元素都被插入完成。这样就可以得到按照成绩从低到高排序的数组。代码实现
public class InsertionSort {public static void main(String[] args) {int[] arr {5, 2, 8, 3, 1};insertionSort(arr);for (int num : arr) {System.out.print(num );}}public static void insertionSort(int[] arr) {int n arr.length;for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}}
}其中n是数组的长度。这个时间复杂度是基于希尔增量序列的选择得出的。然而希尔排序的时间复杂度并不是确定的它可能会受到输入数据的影响。对于某些特定的输入数据希尔排序的时间复杂度可能会更低甚至接近O(n)。这是因为希尔排序在每一轮排序中对于相隔较远的元素进行了交换从而提前将较小或较大的元素移动到了正确的位置减少了后续排序的次数。总结起来希尔排序的时间复杂度是不确定的但平均情况下为O(n^1.3)。应用场景
数组规模较大希尔排序在大规模数组排序时具有较好的性能表现比如对百万级别的数据进行排序。数据分布较均匀希尔排序对于数据分布较均匀的情况下排序效率较高。如果数据分布不均匀可能会导致排序效率下降。对稳定性没有要求希尔排序是一种不稳定的排序算法即相同元素的相对位置可能会发生变化。如果对排序结果的稳定性有要求不适合使用希尔排序。对内存空间要求较低希尔排序是一种原地排序算法不需要额外的内存空间适合在内存空间有限的情况下使用。实际举例
排序算法希尔排序可以用于对大规模数据进行排序尤其是在数据量较大且无序程度较高的情况下相比于其他排序算法希尔排序具有较高的效率。数据库索引在数据库中索引是对表中的数据进行快速查找的一种数据结构。希尔排序可以用于对索引进行排序提高数据库查询的效率。编程语言中的排序函数许多编程语言中的排序函数底层实现使用了希尔排序算法例如C中的std::sort函数就是使用希尔排序作为默认实现。数据压缩希尔排序可以用于对数据进行压缩通过对数据进行排序可以使得相同的数据连续出现从而提高数据的压缩率。图像处理希尔排序可以用于对图像进行排序例如对像素点的颜色值进行排序从而实现图像的特效处理。代码实现
public class ShellSort {public static void shellSort(int[] arr) {int n arr.length;for (int gap n / 2; gap 0; gap / 2) {for (int i gap; i n; i) {int temp arr[i];int j i;while (j gap arr[j - gap] temp) {arr[j] arr[j - gap];j - gap;}arr[j] temp;}}}public static void main(String[] args) {int[] arr {9, 5, 2, 7, 1, 8, 6, 3, 4};shellSort(arr);System.out.println(排序结果);for (int num : arr) {System.out.print(num );}}
}//排序结果1 2 3 4 5 6 7 8 9堆排序
堆排序是一种基于堆数据结构的排序算法它的时间复杂度为O(nlogn)。堆排序的基本思想是将待排序的序列构建成一个大顶堆或小顶堆然后依次将堆顶元素与最后一个元素交换再重新调整堆重复这个过程直到整个序列有序。步骤
堆排序是一种基于二叉堆的排序算法1、构建最大堆或最小堆将待排序的数组看作是一个完全二叉树根据堆的性质可以通过从最后一个非叶子节点开始依次向上调整每个节点使得每个节点都满足堆的性质。这样就可以得到一个最大堆或最小堆。2、将堆顶元素与最后一个元素交换将最大堆或最小堆的堆顶元素与数组的最后一个元素交换位置这样最大或最小的元素就被放到了最后的位置。3、调整堆将交换后的堆顶元素向下调整使得堆的性质仍然成立。具体操作是将堆顶元素与其左右子节点中较大或较小的元素交换位置然后继续向下调整交换后的节点直到堆的性质满足。4、重复步骤2和步骤3直到完成排序重复执行步骤2和步骤3每次都将堆顶元素与当前未排序的部分的最后一个元素交换并调整堆直到所有元素都被交换到了正确的位置。这样就完成了堆排序。举例
待排序序列[4, 10, 3, 5, 1]建堆从最后一个非叶子节点开始依次向上调整使得每个节点的值都大于等于其子节点的值。调整后的堆为[10, 5, 3, 4, 1]排序将堆顶元素10与最后一个元素1交换位置并将堆的大小减1。交换后的堆为[1, 5, 3, 4]。然后再对堆顶元素1进行一次向下调整使得堆重新满足堆的定义。调整后的堆为[5, 4, 3, 1]。再次排序将堆顶元素5与最后一个元素1交换位置并将堆的大小减1。交换后的堆为[1, 4, 3]。然后再对堆顶元素1进行一次向下调整使得堆重新满足堆的定义。调整后的堆为[4, 1, 3]。再次排序将堆顶元素4与最后一个元素3交换位置并将堆的大小减1。交换后的堆为[3, 1]。然后再对堆顶元素3进行一次向下调整使得堆重新满足堆的定义。调整后的堆为[1, 3]。最后排序将堆顶元素1与最后一个元素3交换位置并将堆的大小减1。交换后的堆为[3]。堆的大小为1排序完成。
最终排序结果[1, 3, 4, 5, 10]复杂度分析
建堆建堆的时间复杂度为O(n)其中n为待排序序列的长度。调整堆调整堆的时间复杂度为O(logn)。在堆排序过程中需要调整堆的次数为n-1次每次调整堆的时间复杂度为O(logn)。堆排序堆排序的时间复杂度为O(nlogn)。在堆排序过程中需要进行n-1次调整堆的操作每次调整堆的时间复杂度为O(logn)。因此堆排序的总时间复杂度为O(nlogn)。综上所述堆排序的时间复杂度为O(nlogn)。应用场景
需要对大量数据进行排序的场景堆排序的时间复杂度为O(nlogn)效率较高。需要稳定性较差的排序算法堆排序是一种不稳定的排序算法适用于不要求相同元素的相对位置保持不变的场景。需要对数据进行动态排序的场景堆排序可以在不断插入新元素的情况下快速对数据进行排序。需要找出最大或最小的前k个元素的场景堆排序可以通过构建最大堆或最小堆快速找到最大或最小的元素。实际举例
优先级队列堆排序可以用于实现优先级队列其中每个元素都有一个优先级。通过使用最大堆可以确保优先级最高的元素始终位于堆的根节点从而可以快速找到并删除具有最高优先级的元素。任务调度在任务调度中每个任务都有一个优先级和执行时间。通过使用最小堆可以按照任务的优先级和执行时间对任务进行排序从而实现高效的任务调度。多路归并排序堆排序可以用于多路归并排序其中有多个有序序列需要合并成一个有序序列。通过使用最小堆可以选择每个有序序列的最小元素进行合并从而实现高效的多路归并排序。求Top K问题在一组数据中找到最大或最小的K个元素。通过使用最大堆可以维护一个大小为K的堆每次从数据中取出一个元素与堆顶元素比较如果比堆顶元素大则替换堆顶元素并重新调整堆最终堆中的元素就是最大的K个元素。中位数问题在一组数据中找到中间位置的元素。通过使用最大堆和最小堆可以将数据分为两部分其中最大堆存储较小的一半数据最小堆存储较大的一半数据。这样可以快速找到中位数并支持动态添加和删除元素。
代码实现
public class HeapSort {public void heapSort(int[] arr) {int n arr.length;// 建立最大堆for (int i n / 2 - 1; i 0; i--)heapify(arr, n, i);// 逐个将堆顶元素移到数组末尾for (int i n - 1; i 0; i--) {// 将当前堆顶元素最大值与数组末尾元素交换int temp arr[0];arr[0] arr[i];arr[i] temp;// 重新调整堆找出剩下元素的最大值heapify(arr, i, 0);}}// 调整堆void heapify(int[] arr, int n, int i) {int largest i; // 初始化最大值为根节点int left 2 * i 1; // 左子节点int right 2 * i 2; // 右子节点// 如果左子节点大于根节点将最大值设为左子节点if (left n arr[left] arr[largest])largest left;// 如果右子节点大于当前最大值将最大值设为右子节点if (right n arr[right] arr[largest])largest right;// 如果最大值不是根节点交换根节点与最大值并继续调整堆if (largest ! i) {int swap arr[i];arr[i] arr[largest];arr[largest] swap;heapify(arr, n, largest);}}// 测试代码public static void main(String[] args) {int[] arr {9, 5, 2, 7, 1, 8, 3};HeapSort heapSort new HeapSort();heapSort.heapSort(arr);System.out.println(排序结果);for (int num : arr) {System.out.print(num );}}
}
//输出结果为1 2 3 5 7 8 9。
