「桶排序用数组java」有一个排好序的数组

今天给各位分享桶排序用数组java的知识，其中也会对有一个排好序的数组进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、桶排序与哈希桶排序
• 2、桶排序的算法
• 3、Java中冒泡排序和选择排序有什么不同？
• 4、java 桶排序 输入n个0~1000之间的整数，将它们从大到小排序。谢谢啦
• 5、java 怎么将List里面数据排序

桶排序与哈希桶排序

桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面，然后对每个桶再分别排序（可以使用其它的排序算法或者是递归使用桶排序算法），最后将各个桶中的数据有序的合并起来成为一个整体有序的序列。

排序过程：

1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶

2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序

3.将各个桶中的数据有序的合并起来

设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么数组中最大数为 49，先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶，如下图：

1.时间复杂度：O(m+n)

2.空间复杂度：O(m+n)

适用于序列比较均匀的情况，否则会很耗空间。

或者特殊的场景，例如需要对一个公司的员工的年龄进行排序，年龄的范围为1-120，此时就可以开辟120个桶进行统计排序。

另，桶排序的瓶颈主要是桶数量的选择。

另此算法为稳定的排序算法。

排序算法主要是用分治法，用哈希函数对序列进行划分，最后使用其它的排序算法或者递归使用哈希排序进行排序从而得到一个整体有序的序列。下面先介绍几个自定义的概念：

1.哈希桶排序：因为本算法是使用了哈希函数把序列划分到对应的桶里面，所以本排序算法取名为哈希桶排序。

2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length

计算公式如上式，当结果小于等于0的时候再做特殊处理，据此因子进行桶的划分。

设有数组 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那么数组中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。对数组进行划分，10011 / 1001 = 10，所以10011放在keywei10的桶里面；10001 / 1001 = 9， 所以10001放在key为9的桶里面，以此类推，最后得到的桶的情况为：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分别对每个桶进行排序即可。

1.时间复杂度：O(m+n)

2.空间复杂度：O(m+n)

此算法与桶排序对比，主要是通过哈希建桶的方式减少了空间的消耗，对序列进行了一个归约，时间上跟桶排序相当。

使用与序列的最小最大值相差比较大同时又出现在某一个取值区间的集聚的情况。

另此算法为稳定的排序算法。

桶排序的算法

桶排序算法要求，数据的长度必须完全一样，程序过程要产生长度相同的数据，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的扫描顺序是按照上次扫描的结果来的，所以设计上提供相同的两个桶数据结构。前一个保存每一次扫描的结果供下次调用，另外一个临时拷贝前一次扫描的结果提供给前一个调用。

数据结构设计：链表可以采用很多种方式实现，通常的方法是动态申请内存建立结点，但是针对这个算法，桶里面的链表结果每次扫描后都不同，就有很多链表的分离和重建。如果使用动态分配内存，则由于指针的使用，安全性低。所以，笔者设计时使用了数组来模拟链表（当然牺牲了部分的空间，但是操作却是简单了很多，稳定性也大大提高了）。共十个桶，所以建立一个二维数组，行向量的下标0—9代表了10个桶，每个行形成的一维数组则是桶的空间。

平均情况下桶排序以线性时间运行。像基数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具 体来说，基数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1)上。 桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。

在桶排序算法的代码中，假设输入是含n个元素的数组A，且每个元素满足0≤ A[i]1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。

桶排序的算法如下(伪代码表示)，其中floor(x)是地板函数，表示不超过x的最大整数。

procedure Bin_Sort(var A:List);begin

n:=length(A);

for i:=1 to n do

将A[i]插到表B[floor(n*A[i])]中;

for i:=0 to n-1 do

用插入排序对表B[i]进行排序;

将表B[0],B[1],...,B[n-1]按顺序合并;

end;

右图演示了桶排序作用于有10个数的输入数组上的操作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶)数组B[0..9]。桶i中存放了区间[i/10，(i+1)/10]上的值。排序输出由表B[O]、B[1]、...、B[9]的按序并置构成。

要说明这个算法能正确地工作，看两个元素A[i]和A[j]。如果它们落在同一个桶中，则它们在输出序列中有着正确的相对次序，因为它们所在的桶是采用插入排序的。现假设它们落到不同的桶中，设分别为B[i']和B[j']。不失一般性，假设i' i'=floor(n*A[i])≥floor(n*A[j])=j' 得矛盾 (因为i' 来分析算法的运行时间。除第5行外，所有各行在最坏情况的时间都是O(n)。第5行中检查所有桶的时间是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的时间。

为分析插人排序的时间代价，设ni为表示桶B[i]中元素个数的随机变量。因为插入排序以二次时间运行，故为排序桶B[i]中元素的期望时间为E[O(ni2)]=O(E[ni2])，对各个桶中的所有元素排序的总期望时间为：O(n)。(1) 为了求这个和式，要确定每个随机变量ni的分布。我们共有n个元素，n个桶。某个元素落到桶B[i]的概率为l/n，因为每个桶对应于区间[0，1)的l/n。这种情况与投球的例子很类似：有n个球 (元素)和n个盒子 (桶)，每次投球都是独立的，且以概率p=1/n落到任一桶中。这样，ni=k的概率就服从二项分布B(k;n,p)，其期望值为E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。对任意随机变量X，有右图所示表达式。

(2)将这个界用到(1)式上，得出桶排序中的插人排序的期望运行时间为O(n)。因而，整个桶排序的期望运行时间就是线性的。

Java中冒泡排序和选择排序有什么不同？

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

public class Paixu {

public static void main(String[] args) {

int [] a = {2,6,4,5,1,7,3};

int i = 0;

int j = 0;

int n = 0;

for(i= 0;ia.length-1;i++){

for(j=0;ja.length-i-1;j++){

if(a[j]a[j+1]){

n = a[j];

a[j] = a[j+1];

a[j+1] = n;

}

}

}

for ( i = 0; i a.length; i++) {

System.out.println(a[i]);

}

}

}

直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R{1}~R[n-1]中选取最小值，与R[1]交换，....， 第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.

public class Paixu {

public static void main(String[] args) {

int [] a = {2,6,4,5,1,7,3};

int i = 0;

int j = 0;

int n = 0;

for(i= 0;ia.length;i++){

for(j=i+1;ja.length;j++){

if(a[i]a[j]){

n = a[i];

a[j] = a[i];

a[i] = n;

}

}

}

for ( i = 0; i a.length; i++) {

System.out.println(a[i]);

}

}

}

java 桶排序 输入n个0~1000之间的整数，将它们从大到小排序。谢谢啦

import java.util.Scanner;

public class Help {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int size=sc.nextInt();//记录次数n

int[] s=new int[size];//储存数字的数组

for(int i=0;isize;i++){

int p=sc.nextInt();

if(0pp1000){//进行判断

s[i]=p;

}

else{

System.out.println("您输入的数字非法！");}

}

Arrays.sort(s);//从小到大排序

for(int i=0;i=(int)size/2;i++){//再将顺序倒过来

int l=s.length;

int ss=s[i];

s[i]=s[l-1-i];

s[l-1-i]=ss;

}

for(int i=0;isize;i++) {

System.out.println(s[i]);

}

}

}

不懂再问哦~~~

java 怎么将List里面数据排序

学生实体类，包含姓名和年龄属性，

比较时先按姓名升序排序，如果姓名相同则按年龄升序排序。

第一种：实体类自己实现比较

（实现comparable接口：public interface ComparableT ，里面就一个方法声明：public int compareTo(T o); ）

然后利用List类的sort(Comparator? super E c)方法或java.util.Collections工具类的sort(ListT list) （其实里面就一句：list.sort(null); ）进行排序：

结果：

第二种：借助比较器进行排序。

示例代码：

比较器java.util.Comparator类是一个接口（public interface ComparatorT )，包含int compare(T o1, T o2);等方法：

我们的比较器要实现该接口并实现compare方法：

比较的时候可以利用List的sort(Comparator? super E c)方法（或者java.util.Collections工具类的sort(ListT list, Comparator? super T c)方法）进行排序。

结果跟第一种方法一样：

桶排序用数组java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于有一个排好序的数组、桶排序用数组java的信息别忘了在本站进行查找喔。