婚纱摄影网站开发的目的,磁力猫torrent kitty,如何开发一个聊天软件,wordpress 搬家后无法打开这篇文章对排序算法进行一个汇总比较#xff01;
目录
0.十大排序汇总
0.1概述
0.2比较和非比较的区别
0.3基本术语
0.4排序算法的复杂度及稳定性
1.冒泡排序
算法简介
动图演示
代码演示
应用场景
算法分析
2.快速排序
算法简介
动图演示
代码演示
应用场景…这篇文章对排序算法进行一个汇总比较
目录
0.十大排序汇总
0.1概述
0.2比较和非比较的区别
0.3基本术语
0.4排序算法的复杂度及稳定性
1.冒泡排序
算法简介
动图演示
代码演示
应用场景
算法分析
2.快速排序
算法简介
动图演示
代码演示
应用场景
算法分析
3.插入排序
算法简介
动图演示
代码演示
应用场景
算法分析
4.选择排序
算法简介
动图演示
代码演示
应用场景
算法分析
5.归并排序
算法简介
图片演示
代码演示
应用场景
算法分析
6.希尔排序
算法简介
图片演示
代码演示
应用场景
算法分析
7.堆排序
算法简介
图片演示
代码演示
应用场景
算法分析
8.计数排序
算法分析
动图演示
代码演示
应用场景
算法分析
9.基数排序
算法分析
动图演示
代码演示
应用场景
算法分析
10.桶排序
算法分析
动图演示
代码演示
应用场景
算法分析
11.Java自带的排序算法 0.十大排序汇总
0.1概述
一图以蔽之 0.2比较和非比较的区别
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较才能确定自己的位置。 在冒泡排序之类的排序中问题规模为 n又因为需要比较 n 次所以平均时间复杂度为O(n²)。
在归并排序、快速排序之类的排序中问题规模通过分治法消减为 logN 次所以时间复杂度平均O(nlogn)。
比较排序的优势是适用于各种规模的数据也不在乎数据的分布都能进行排序。可以说比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前应该有多少个元素来排序。针对数组 arr计算 arr 之前有多少个元素则唯一确定了 arr 在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可所有一次遍历即可解决。算法时间复杂度O(n)。 非比较排序时间复杂度底但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
0.3基本术语
稳定如果a原本在b前面而ab排序之后a仍然在b的前面不稳定如果a原本在b的前面而ab排序之后a可能出现在b的后面内排序所有的排序操作都在内存中完成外排序由于数据太大因此把数据放在磁盘中而排序通过磁盘和内存的数据传输才能进行时间复杂度一个算法执行所消耗的时间空间复杂度运行完一个程序所需内存的大小。
0.4排序算法的复杂度及稳定性 1.冒泡排序
算法简介
1. 从左向右依次对比相邻元素将较大值交换到右边 2. 每一轮循环可将最大值交换到最左边 3. 重复1.2两个步骤直至完成整个数组。
动图演示 代码演示
package Sorts;import java.util.Arrays;
//冒泡排序
public class MaoPaoSort {public static void main(String[] args) {int[] arr new int []{5,9,2,7,3,1,10};maoPaoSort(arr);System.out.println(Arrays.toString(arr));}public static void maoPaoSort(int[]arr){for (int i 0; i arr.length ; i) {for (int j 0; j arr.length-1 ; j) {if (arr[j] arr[j1]){//这是比较相邻的元素int temp arr[j];arr[j]arr[j1];arr[j1]temp;}}}}
}应用场景
一般在学习的时候作为理解排序原理的时候使用在实际应用中不会使用
算法分析
最佳情况T ( n ) O ( n )
最差情况T ( n ) O ( n^2 )
平均情况T ( n ) O ( n^2 ) 2.快速排序
算法简介
选择一个元素赋值给中间元素temp默认选择左边第一个元素这样左边第一个元素的位置就空出来了先从最右边的元素开始依次跟temp比较大小大于等于temp元素的原地不动遇到小于temp元素的则终止循环把该元素赋值到左侧空出来的位置同时左侧索引值自增这是该元素原来的位置就空出然后左侧元素开始依次跟temp比较大小小于等于temp元素的原地不动遇到大雨temp元素的则终止循环把该元素赋值到右侧空出来的位置同时右侧索引值自减依次循环2,3步直至左侧索引等于右侧索引则完成一轮循环把哨兵赋值到该索引的位置。在分别递归地对 temp 左右两侧的子数组进行1234步直至递归子数组只有一个元素则排序完成
动图演示 代码演示
package Sorts;import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;
//快排
public class QuickSort {public static void main(String[] args) {int[] array {16,13,7,15,28,11,9,32,22,19};int[] array1 {4,2,1,3,2,4};System.out.println(排序前 Arrays.toString(array1));sort(array1);System.out.println(排序后 Arrays.toString(array1));}/*** 交换操作* */private static void swap(int[] array,int i,int j){int t array[i];array[i] array[j];array[j] t;}/*** 排序的函数* */private static void sort(int[] array) {quick(array,0,array.length-1);}/*** 递归的函数* */private static void quick(int[] array, int left, int right) {//结束递归的条件如果我们左边的索引大于或等于右边的索引了最多只能等于不可能大于那说明就只有一个元素的了那就不用递归了if (leftright){return;}int p partition4(array,left,right); //p代表基准点元素的索引quick(array,left,p-1); // 对基准点左边的区进行递归操作quick(array,p1,right); // 对基准点右边的区进行递归操作}/*** 分区并进行比较然后排序的函数这部分是核心代码* 单边快排* */private static int partition1(int[] array, int left, int right) {int pv array[right]; //基准点的值int i left;int j left;while (jright){ //当j小于右边届的时候j就要1if (array[j]pv){ //j找到比基准点小的值if (i!j){swap(array,i,j);}/*** 这里多说一点* i与j都是从left开始的初始指向是一致的i找大的j找小的* 进入这个判断就是说明j找到小的了* 没进入这个判断就是说明j没有找到小的也就是说此时j指向的值大于等于基准值* 因为i与j的指向在初始时是一致的* 所以没进入这个判断时i指向的值就比基准值大了* 所以i就找到了不用1了* 但是j没有找到* 所以j要1* 这就是i在里面j在外面的原因* 如果进入这个判断即j找到小的了此时i在哪* i在j前面或者和i在同一个位置看代码就能想清楚* 有没有可能j找到小的了然后不走了i没找到继续走然后在j后面找到大的了* 这种情况就没必要交换了并且这种情况进不来这个判断* */i;}j;}swap(array,i,right); //交换基准点与i的位置此时i记录的就是基准点的位置return i;}/*** 双边快排* */private static int partition2(int[] array, int left, int right) {int pv array[left]; //基准点的值int i left; //游标i从最左边开始找大的int j right; //游标j从最右边开始找小的while (i j){ //ij的时候进行循环一旦ij或ij就要退出循环while (i j array[j] pv){//找比基准点小的值没找到j就--一旦找到就退出循环j--;}
// while (ij array[i]pv)while (ij array[i]pv){//找比基准点大的值没找到i就一旦找到就退出循环i;}swap(array,i,j);//交换}swap(array,left,i);return i;}/*** 定义随机的基准点* */private static int partition3(int[] array, int left, int right) {int idx ThreadLocalRandom.current().nextInt(right-left1)left;//生成范围内的随机数swap(array,idx,left);//交换随机数与left的值int pv array[left];//基准点的值int i left; //游标i从最左边开始找大的int j right; //游标j从最右边开始找小的while (i j){ //ij的时候进行循环一旦ij或ij就要退出循环while (i j array[j] pv){//找比基准点小的值没找到j就--一旦找到就退出循环j--;}while (ij array[i]pv){//找比基准点大的值没找到i就一旦找到就退出循环i;}swap(array,i,j);//交换}swap(array,left,i);return i;}/*** 改进后的算法* 为了处理重复的元素* */private static int partition4(int[] array, int left, int right) {int pv array[left];//基准点的值int i left1; //游标i从left1开始找大的int j right; //游标j从最右边开始找小的while (i j){ //ij的时候进行循环一旦ij就要退出循环,当ij的时候也要进入循环while (i j array[j] pv){//找比基准点小或等于的值没找到j就--一旦找到就退出循环j--;}while (ij array[i] pv){//找比基准点大或相等的值没找到i就一旦找到就退出循环i;}if (ij){swap(array,i,j);//交换i;j--;}}swap(array,left,j);return j;}
}应用场景
略
算法分析
最佳情况T ( n ) O ( nlogn )
最差情况T ( n ) O ( n^2 )
平均情况T ( n ) O ( nlogn ) 3.插入排序
算法简介
左边第一个元素可作为有序子数组从第二个元素开始依次向前比较大于该元素的则向右移一位直到比该元素小的元素插入其后依次向后推进直至整个数组成为有序数组
动图演示 代码演示
package Sorts;import java.util.Arrays;
//插入排序
public class InsertSort {public static void main(String[] args) {int [] arr new int[]{5,9,2,7,3,1,10};Insert2(arr);System.out.println(Arrays.toString(arr));}//递归版的方法public static void Insert1(int[]arr, int low){if (low arr.length)return;int t arr[low];int i low-1;//从右向左找插入位置如果比待插入元素大则不断右移空出插入位置while (i 0 t arr[i]){arr[i1] arr[i];i--;}//找到插入位置if (i1 ! low){arr[i1] t;}Insert1(arr,low1);}public static void Insert2(int[]arr){for (int low 1; low arr.length-1 ; low) {int t arr[low];int i low-1;//从右向左找插入位置如果比待插入元素大则不断右移空出插入位置while (i 0 t arr[i]){arr[i1] arr[i];i--;}//找到插入位置if (i1 ! low){arr[i1] t;}}}
}应用场景
如果大部分数据距离它正确的位置很近或者近乎有序例如银行的业务完成的时间 如果是这样的话插入排序是更好的选择。
算法分析
最佳情况T ( n ) O ( n )
最坏情况T ( n ) O ( n^2 )
平均情况T ( n ) O ( n^2 ) 4.选择排序
算法简介
首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
动图演示 代码演示
package Sorts;import java.util.Arrays;
//选择排序
public class ChooseSort {public static void main(String[] args) {int [] arr new int [] {5,9,2,7,3,1,10};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int []arr){for (int i 0; i arr.length ; i) {//从第一个索引开始遍历数组for (int j i; j arr.length ; j) {//从当前索引位置开始遍历后面的数组if (arr[j]arr[i]){//后面的数组元素比它小就交换他两的位置这两元素不相邻int temp arr[i];arr[i]arr[j];arr[j]temp;}}}}
}应用场景
当数据量较小的时候适用
算法分析
最佳情况T ( n ) O ( n^2 )
最差情况T ( n ) O ( n^2 )
平均情况T ( n ) O ( n^2 ) 5.归并排序
算法简介
分
一直分两组分别对两个数组进行排序根据上层对下层在一组的数据通过临时数组排序再将有序数组挪回上层数组中。 循环第一步直到划分出来的“小组”只包含一个元素只有一个元素的数组默认为已经排好序。
合合并时站在上层合并下层使组内有序
将两个有序的数组合并到一个大的数组中。从最小的只包含一个元素的数组开始两两合并。此时合并好的数组也是有序的。最后把小组合成一个组。
图片演示 代码演示
package Sorts;import java.util.Arrays;
//归并排序
public class Merge {public static void main(String[] args) {int[] array new int[]{13,56,2,8,19,34,29};System.out.println(排序前 Arrays.toString(array));mergeSort(array,0,array.length-1);System.out.println(排序后Arrays.toString(array));}public static void mergeSort(int[] array, int low, int height){if (low height)return;int mid (lowheight)1;mergeSort(array,low,mid);mergeSort(array,mid1,height);merge(array,low,mid,height);}public static void merge(int[] array,int low,int mid,int height){int[] ret new int[height-low1];int i 0;//新数组的索引int s1 low;//前一个分段的初始位置int s2 mid1;//后一个分段的初始位置while (s1mid s2height){if (array[s1]array[s2]){//比较元素的大小ret[i] array[s1];//赋值给新数组然后索引}else {ret[i] array[s2];i;s2;}}while (s1mid){//将前半段剩下的全部赋值到新数组中ret[i] array[s1];}while (s2height){//将后半段剩下的全部赋值到新数组中ret[i] array[s2];}for (int j 0; j ret.length; j) {//将新数组中的元素全部挪到原数组中array[jlow] ret[j];}}
}应用场景
内存空间不足的时候使用归并排序能够使用并行计算的时候使用归并排序。
算法分析
最佳情况T ( n ) O ( n )
最差情况T ( n ) O ( nlogn )
平均情况T ( n ) O ( nlogn ) 6.希尔排序
算法简介
首先选择一个步长值gap以步长值为间隔把数组分为gap个子数组gaplength/2对每个子数组进行插入排序逐步减小步长 gap gap/2,重复对数组进行12 步骤当步长值减为1时相当于对数组进行一次直接插入排序。
图片演示 代码演示
package Sorts;import java.util.Arrays;
//希尔排序
public class XiErSort {public static void main(String[] args) {int [] arr new int []{5,9,2,7,3,1,10};xiEr(arr);System.out.println(Arrays.toString(arr));}public static void xiEr(int arr[]){for (int gap arr.length/2; gap 0 ; gap /2) {for (int low gap; low arr.length ; low) {int t arr[low];int i low - gap;//自右向左找插入位置如果比待插入的元素大则不断右移空出插入位置while (i 0 t arr[i]){arr[igap] arr[i];i-gap;}//找到插入位置if(i ! low-gap){arr[igap] t;}}}}
}应用场景
相对于直接插入排序希尔排序要高效很多因为当gap 值较大时对子数组进行插入排序时要移动的元素很少元素移动的距离很大这样效率很高在gap逐渐减小过程中数组中元素已逐渐接近排序的状态所以需要移动的元素逐渐减少当gap为1时相当于进行一次直接插入排序但是各元素已接近排序状态需要移动的元素很少且移动的距离都很小。
算法分析
最佳情况T ( n ) O ( nlog2 n )
最坏情况T ( n ) O ( nlog2 n )
平均情况T ( n ) O ( nlog2 n ) 7.堆排序
算法简介
堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。
堆排序可以说是一种利用堆的概念来排序的选择排序。
分为两种方法
大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列 图片演示
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆一般升序采用大顶堆降序采用小顶堆)。 a.假设给定无序序列结构如下 此时我们从最后一个非叶子结点开始叶结点自然不用调整第一个非叶子结点 arr.length/2-15/2-11也就是下面的6结点从左至右从下至上进行调整。
此处必须注意我们把 6 和 9 比较交换之后必须考量 9 这个节点对于其子节点会不会产生任何影响因为其是叶子节点所以不加考虑
但是一定要熟练这种思维写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。 找到第二个非叶节点4由于[4,9,8]中9元素最大4和9交换。
在真正代码的实现中这时候4和9交换过后必须考虑9所在的这个节点位置因为其上的值变了必须判断对其的两个子节点是否造成了影响这么说不合适实际上就是判断其作为根节点的那棵子树是否还满足大根堆的原则每一次交换都必须要循环把子树部分判别清楚。 这时交换导致了子根[4,5,6]结构混乱继续调整[4,5,6]中6最大交换4和6。
牢记上面说的规则每次交换都要把改变了的那个节点所在的树重新判定一下这里就用上了4和9交换了变动了的那棵子树就必须重新调整一直调整到符合大根堆的规则为截。 此时我们就将一个无序序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换使末尾元素最大。然后继续调整堆再将堆顶元素与末尾元素交换得到第二大元素。如此反复进行交换、重建、交换。
将堆顶元素9和末尾元素4进行交换
这里必须说明一下所谓的交换实际上就是把最大值从树里面拿掉了剩下参与到排序的树其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。 重新调整结构使其继续满足堆定义 再将堆顶元素8与末尾元素5进行交换得到第二大元素8. 后续过程继续进行调整交换如此反复进行最终使得整个序列有序 代码演示
package Sorts;
//堆排
public class HeapSort {public static void main(String[] args) {int[] arr {16, 7, 3, 20, 17, 8};heapSort(arr);for (int i : arr) {System.out.print(i );}}/*** 创建堆*/private static void heapSort(int[] arr) {//创建堆for (int i (arr.length - 1) / 2; i 0; i--) {//从第一个非叶子结点从下至上从右至左调整结构adjustHeap(arr, i, arr.length);}//调整堆结构交换堆顶元素与末尾元素for (int i arr.length - 1; i 0; i--) {//将堆顶元素与末尾元素进行交换int temp arr[i];arr[i] arr[0];arr[0] temp;//重新对堆进行调整adjustHeap(arr, 0, i);}}/*** 调整堆* param arr 待排序列* param parent 父节点* param length 待排序列尾元素索引*/private static void adjustHeap(int[] arr, int parent, int length) {//将temp作为父节点int temp arr[parent];//左孩子int lChild 2 * parent 1;while (lChild length) {//右孩子int rChild lChild 1;// 如果有右孩子结点并且右孩子结点的值大于左孩子结点则选取右孩子结点if (rChild length arr[lChild] arr[rChild]) {lChild;}// 如果父结点的值已经大于孩子结点的值则直接结束if (temp arr[lChild]) {break;}// 把孩子结点的值赋给父结点arr[parent] arr[lChild];//选取孩子结点的左孩子结点,继续向下筛选parent lChild;lChild 2 * lChild 1;}arr[parent] temp;}
}
应用场景
堆排序适合于数据量非常大的场合百万数据。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录因为快速排序归并排序都使用递归来设计算法在数据量非常大的时候可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆最大的数据在堆顶然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆交换数据依次下去就可以排序所有的数据。
算法分析
最佳情况T ( n ) O ( nlogn )
最差情况T ( n ) O ( nlogn )
平均情况T ( n ) O ( nlogn ) 8.计数排序
算法分析
找出待排序的数组中最大和最小的元素 统计数组中每个值为 i 的元素出现的次数存入数组C的第 i 项 对所有的计数累加从C中的第一个元素开始每一项和前一项相加 反向填充目标数组将每个元素i放在新数组的第C( i ) 项每放一个元素就将C( i ) 减去1。
动图演示 代码演示
package Sorts;import java.util.Arrays;//计数排序
public class CountSort {public static void main(String[] args) {int[] arr {5,1,1,1,3,0};System.out.println(Arrays.toString(arr));countSort1(arr);System.out.println(Arrays.toString(arr));}//数组中元素0private static void countSort1(int[] arr) {int max arr[0];for (int i 1; i arr.length; i) {if (arr[i] max)max arr[i];}int[] count new int[max1];for (int v : arr) { //原始数组的元素count[v];}int k 0;for (int i 0; i count.length; i) {// i 代表原始数组中的元素count[i]代表出现次数while (count[i]0){arr[k] i;count[i]--;}}}//不限制数组中元素的大小可以有负数private static void countSort2(int[] arr) {//让数组中的最小值映射到数组的count[0]位置最大值映射到count的最右侧int min arr[0];int max arr[0];for (int i 1; i arr.length; i) {if (arr[i] max)max arr[i];if (arr[i] min)min arr[i];}int[] count new int[max - min 1];//原始数组元素 - 最小值 count 索引for (int v : arr) { //原始数组的元素count[v - min];}int k 0;for (int i 0; i count.length; i) {// imin 代表原始数组中的元素count[i]代表出现次数while (count[i]0){arr[k] i min;count[i]--;}}}
}应用场景
计数排序需要占用大量空间它仅适用于数据比较集中的情况。比如 [0100][1000019999] 这样的数据。
算法分析
最佳情况T ( n ) O ( nk )
最差情况T ( n ) O ( nk )
平均情况T ( n ) O ( nk ) 9.基数排序
算法分析
相比其它排序主要是利用比较和交换而基数排序则是利用分配和收集两种基本操作。基数排序是一种按记录关键字的各位值逐步进行排序的方法。此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。
实现将所有待比较数值自然数统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。基数排序的两种方式高位优先又称为最有效键(MSD),它的比较方向是由右至左低位优先又称为最无效键(LSD),它的比较方向是由左至右
动图演示 代码演示
package Sorts;import java.util.Arrays;//基数排序
public class RadixSort {public static void main(String[] args) {int [] arr new int[]{193,255,12,6,78,50,31,564};radixSort(arr);;System.out.println(Arrays.toString(arr));}public static void radixSort(int[] array) {if (array null || array.length 1) {return;}int length array.length;// 每位数字范围0~9基为10int radix 10;int[] aux new int[length];int[] count new int[radix 1];// 以关键字来排序的轮数由位数最多的数字决定其余位数少的数字在比较高位时自动用0进行比较// 将数字转换成字符串字符串的长度就是数字的位数字符串最长的那个数字也拥有最多的位数int x Arrays.stream(array).map(s - String.valueOf(s).length()).max().getAsInt();// 共需要d轮计数排序, 从d 0开始说明是从个位开始比较符合从右到左的顺序for (int d 0; d x; d) {// 1. 计算频率在需要的数组长度上额外加1for (int i 0; i length; i) {// 使用加1后的索引有重复的该位置就自增count[digitAt(array[i], d) 1];}// 2. 频率 - 元素的开始索引for (int i 0; i radix; i) {count[i 1] count[i];}// 3. 元素按照开始索引分类用到一个和待排数组一样大临时数组存放数据for (int i 0; i length; i) {// 填充一个数据后自增以便相同的数据可以填到下一个空位aux[count[digitAt(array[i], d)]] array[i];}// 4. 数据回写for (int i 0; i length; i) {array[i] aux[i];}// 重置count[]以便下一轮统计使用for (int i 0; i count.length; i) {count[i] 0;}}}//Description: 根据d获取某个值的个位、十位、百位等d 0取出个位d 1取出十位以此类推。对于不存在的高位用0补private static int digitAt(int value, int d) {return (value / (int) Math.pow(10, d)) % 10;}
}应用场景
略
算法分析
最佳情况T ( n ) O ( n * k )
最差情况T ( n ) O ( n * k )
平均情况T ( n ) O ( n * k ) 10.桶排序
算法分析
桶排序(Bucket Sort)的原理很简单它是将数组分到有限数量的桶子里。
假设待排序的数组a中共有N个整数并且已知数组a中数据的范围[0, MAX)。在桶排序时创建容量为MAX的桶数组r并将桶数组元素都初始化为0将容量为MAX的桶数组中的每一个单元都看作一个桶。 在排序时逐个遍历数组a将数组a的值作为桶数组r的下标。当a中数据被读取时就将桶的值加1。例如读取到数组a[3]5则将r[5]的值1。
动图演示 代码演示
package Sorts;import java.util.*;//桶排
public class BucketSort {public static void main(String[] args) {int [] arr new int[]{193,255,12,6,78,50,31,564};bucketSort(arr);;System.out.println(Arrays.toString(arr));}public static void bucketSort(int[] array) {if (array null || array.length 1) {return;}// 建立桶个数和待排序数组长度一样int length array.length;LinkedListInteger[] bucket (LinkedListInteger[]) new LinkedList[length];// 待排序数组中的最大值int maxValue Arrays.stream(array).max().getAsInt();// 根据每个元素的值分配到对应范围的桶中for (int i 0; i array.length; i) {int index toBucketIndex(array[i], maxValue, length);// 没有桶才建立桶(延时)if (bucket[index] null) {bucket[index] new LinkedList();}// 有桶直接使用bucket[index].add(array[i]);}// 对每个非空的桶排序排序后顺便存入临时的List则list中已经有序ListInteger temp new ArrayList();for (int i 0; i length; i) {if (bucket[i] ! null) {Collections.sort(bucket[i]);temp.addAll(bucket[i]);}}// 将temp中的数据写入原数组for (int i 0; i length; i) {array[i] temp.get(i);}}private static int toBucketIndex(int value, int maxValue, int length) {return (value * length) / (maxValue 1);}/***public static void bucketSort(int arr[] ){//定义二维数组int [][] bucket new int[10][arr.length];//定义记录桶中数据个数的数组int [] bucketElement new int[10];for (int i 0; i arr.length ; i) {int element arr[i] % 10;bucket[element][bucketElement[element]] arr[i];bucketElement[element];}int index 0;for (int k 0; k bucketElement.length ; k) {if (bucketElement[k]!0){for (int l 0; l bucketElement [k] ; l) {arr[index] bucket[k][l];index;}}bucketElement[k]0;}}*/
}应用场景
略
算法分析
桶排序最好情况下使用线性时间O(n)桶排序的时间复杂度取决与对各个桶之间数据进行排序的时间复杂度因为其它部分的时间复杂度都为O(n)。很显然桶划分的越小各个桶之间的数据越少排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况T ( n ) O ( nk )
最差情况T ( n ) O ( nk )
平均情况T ( n ) O ( n^2 )
11.Java自带的排序算法
JDK7-13 JDK14-20 其中TimSort是用归并 二分插入排序的混合排序算法值得注意的是从JDK8开始支持 Arrays.parallelSort 并行排序根据最新的提交记录来看JDK21可能会引入基数排序等优化
