最新十大排序算法详细讲解，以及各种应用场景

2024-07-13 19:22| 来源: 网络整理| 查看: 265

文章目录十大排序算法汇总比较和非比较的区别一些基本的术语排序算法复杂度及稳定性一、冒泡排序算法简介动图演示代码实现应用场景算法分析二、快速排序算法简介动图演示代码实现算法分析三、简单插入排序算法简介动图演示代码实现应用场景算法分析四、希尔排序算法简介图片演示代码实现算法的优点算法分析五、简单选择排序算法简介动图演示代码实现应用场景算法分析六、堆排序算法简介图片演示代码实现应用场景算法分析七、二路归并排序算法简介图片演示代码实现应用场景算法分析八、计数排序算法简介动图演示代码实现应用场景算法分析九、桶排序算法简介图片演示代码实现算法分析十、基数排序算法简介动图演示代码实现算法分析一些基本情况 **

十大排序算法汇总

** 在这里插入图片描述

比较和非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

一些基本的术语

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可能出现在b的后面；内排序：所有的排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度：一个算法执行所消耗的时间；空间复杂度：运行完一个程序所需内存的大小。

排序算法复杂度及稳定性

在这里插入图片描述

一、冒泡排序算法简介

1.从左向右依次对比相邻元素，将较大值交换到右边； 2.每一轮循环可将最大值交换到最左边 3.重复1.2两个步骤，直至完成整个数组。

动图演示

在这里插入图片描述

代码实现 /** * 冒泡算法的实现 * @param array * @return */ public static int[] bubbleSort(int[] array) { if(array.length==0) { return array; } for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length-1-i; j++) { if(array[j+1]= pivot)//让参考点与最右边的相比较，小于不动，大于右面减一 right--; if (left < right)//让小于参考点的数，进入空出来的位置， n[left++] = n[right]; while (left < right && n[left] =0&&array[preIndex]>temp) { array[preIndex+gap]=array[preIndex]; preIndex-=gap; } array[preIndex+gap]=temp; } gap/=2; } return array; } } 算法的优点

相对于直接插入排序，希尔排序要高效很多，因为当gap 值较大时，对子数组进行插入排序时要移动的元素很少，元素移动的距离很大，这样效率很高；在gap逐渐减小过程中，数组中元素已逐渐接近排序的状态，所以需要移动的元素逐渐减少；当gap为1时，相当于进行一次直接插入排序，但是各元素已接近排序状态，需要移动的元素很少且移动的距离都很小。

算法分析

最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)

五、简单选择排序算法简介

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

动图演示

在这里插入图片描述

代码实现 package leetcode; /** * 选择排序 * @author acer * */ public class Selection_sort { public static void main(String[] args) { int[] array= {3,3,345,2,753,4765,734658,567,7}; int[] arrayNew=Selection_sort.selection_sort(array); for (int i = 0; i < arrayNew.length; i++) { System.out.print(arrayNew[i]+" "); } } public static int[] selection_sort(int[] array) { if(array.length==0) { return array; } for(int i=0;i a[1]&&a[0]>a[2],说明0,1,2这棵树不需要调整，那么，下一步该到哪个节点了呢？肯定是a[1]所在的子树了， // 也就是说，是以本节点的左子节点为根的那棵小的子树 // 而如果a[0} temp) { swap(array, i, k); // 下面就是非常关键的一步了 // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？ // 所以，循环对子节点所在的树继续进行判断 i = k; // 如果不用交换，那么，就直接终止循环了 } else { break; } } } /** * 交换元素 * * @param arr * @param a * 元素的下标 * @param b * 元素的下标 */ public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } } 应用场景

堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

七、二路归并排序算法简介

分： 1.一直分两组，分别对两个数组进行排序(根据上层对下层在一组的数据通过临时数组排序，再将有序数组挪回上层数组中)。 2. 循环第一步，直到划分出来的“小组”只包含一个元素，只有一个元素的数组默认为已经排好序。合：（合并时，站在上层合并下层（使组内有序）） 1.将两个有序的数组合并到一个大的数组中。 2.从最小的只包含一个元素的数组开始两两合并。此时，合并好的数组也是有序的。最后把小组合成一个组。

图片演示

在这里插入图片描述

代码实现 public class MergeSort { /** * 归并排序 * @param arr * @param left * @param right */ public static void mergeSort(int[] arr, int left, int right) { if(null == arr) { return; } if(left < right) { //找中间位置进行划分 int mid = (left+right)/2; //对左子序列进行递归归并排序 mergeSort(arr, left, mid); //对右子序列进行递归归并排序 mergeSort(arr, mid+1, right); //“合”。进行归并 merge(arr, left, mid, right); } } /** * 进行归并 * @param arr * @param left * @param mid * @param right */ private static void merge(int[] arr, int left, int mid, int right) { int[] tempArr = new int[arr.length]; int leftStart = left; int rightStart = mid+1; int tempIndex = left; while(leftStart

【本文地址】

最新十大排序算法详细讲解，以及各种应用场景

最新十大排序算法详细讲解，以及各种应用场景

今日新闻

推荐新闻