Java实现冒泡排序与双向冒泡排序算法的代码示例
冒泡排序：
就是按索引逐次比较相邻的两个元素，如果大于/小于(取决于需要升序排还是降序排)，则置换，否则不做改变
这样一轮下来，比较了n-1次，n等于元素的个数；n-2,n-3...一直到最后一轮，比较了1次
所以 比较次数为递减：从n-1到1
那么总的比较次数为：1+2+3+...+(n-1), 以等差公式计算：(1+n-1)/2*(n-1)==>n/2*(n-1)==>(n^2-n)*0.5
用大O表示算法的时间复杂度：O(n^2), 忽略了系数0.5和常数-n
publicclassBubbleSort{
publicstaticvoidmain(String[]args){
intlen=10;
int[]ary=newint[len];
Randomrandom=newRandom();
for(intj=0;j<len;j++){
ary[j]=random.nextInt(1000);
}
System.out.println("-------排序前------");
for(intj=0;j<ary.length;j++){
System.out.print(ary[j]+"");
}
/*
*升序，Asc1和Asc2优化了内部循环的比较次数，比较好
*总的比较次数：
*Asc1、Asc2：(1+n-1)/2*(n-1)==>n/2*(n-1)==>n*(n-1)/2==>(n^2-n)/2
*Asc：n^2-n
*/
//orderAsc(ary);
//orderAsc2(ary);
orderAsc1(ary);
//降序，只需要把判断大小于置换一下
}
staticvoidorderAsc(int[]ary){
intcount=0;//比较次数
intlen=ary.length;
for(intj=0;j<len;j++){//外层固定循环次数
for(intk=0;k<len-1;k++){//内层固定循环次数
if(ary[k]>ary[k+1]){
ary[k]=ary[k+1]+(ary[k+1]=ary[k])*0;//一步交换
/*交换两个变量值
*a=a+b
*b=a-b
*a=a-b
*/
}
count++;
}
}
System.out.println("\n-----orderAsc升序排序后------次数："+count);
for(intj=0;j<len;j++){
System.out.print(ary[j]+"");
}
}
staticvoidorderAsc1(int[]ary){
intcount=0;//比较次数
intlen=ary.length;
for(intj=0;j<len;j++){//外层固定循环次数
for(intk=len-1;k>j;k--){//内层从多到少递减比较次数
if(ary[k]<ary[k-1]){
ary[k]=ary[k-1]+(ary[k-1]=ary[k])*0;//一步交换
}
count++;
}
}
System.out.println("\n-----orderAsc1升序排序后------次数："+count);
for(intj=0;j<len;j++){
System.out.print(ary[j]+"");
}
}
staticvoidorderAsc2(int[]ary){
intcount=0;//比较次数
intlen=ary.length;
for(intj=len-1;j>0;j--){//外层固定循环次数
/*
*k<j;总的比较次数=(n^2-n)/2
*/
for(intk=0;k<j;k++){//内层从多到少递减比较次数
if(ary[k]>ary[k+1]){
ary[k]=ary[k+1]+(ary[k+1]=ary[k])*0;//一步交换
}
count++;
}
}
System.out.println("\n-----orderAsc2升序排序后------次数："+count);
for(intj=0;j<len;j++){
System.out.print(ary[j]+"");
}
}
}
打印
-------排序前------ 8987862286879660433724316737 -----orderAsc1升序排序后------次数：45 7286316433660724737862879898
双向冒泡排序
冒泡排序_鸡尾酒排序、就是双向冒泡排序。
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序,外层比较左右边界l<r,
内层一个循环从左向右比，取高值置后；一个循环从右向左，取低值置前；
效率上，O(N^2),不比普通的冒泡快
publicclassBubble_CocktailSort{
publicstaticvoidmain(String[]args){
intlen=10;
int[]ary=newint[len];
Randomrandom=newRandom();
for(intj=0;j<len;j++){
ary[j]=random.nextInt(1000);
}
/*
*交换次数最小也是1次，最大也是(n^2-n)/2次
*/
//ary=newint[]{10,9,8,7,6,5,4,3,2,1};//测试交换次数
//ary=newint[]{1,2,3,4,5,6,7,8,10,9};//测试交换次数
System.out.println("-------排序前------");
for(intj=0;j<ary.length;j++){
System.out.print(ary[j]+"");
}
orderAsc1(ary);
//orderAsc2(ary);
//降序，只需要把判断大小于置换一下
}
staticvoidorderAsc1(int[]ary){
intcompareCount=0;//比较次数
intchangeCount=0;//交换次数
intlen=ary.length;
intleft=0,right=len-1,tl,tr;
while(left<right){//外层固定循环次数
tl=left+1;
tr=right-1;
for(intk=left;k<right;k++){//内层从多到少递减比较次数,从左向右
if(ary[k]>ary[k+1]){//前大于后，置换
ary[k]=ary[k+1]+(ary[k+1]=ary[k])*0;//一步交换
changeCount++;
tr=k;//一轮中最后一比较的时候，将k所在索引赋给tr,tr表示以后比较的结束索引值,从左向右比后，k表示左边的索引
}
compareCount++;
}
right=tr;
for(intk=right;k>left;k--){//内层从多到少递减比较次数,从右向左
if(ary[k]<ary[k-1]){//后小于前置换
ary[k]=ary[k-1]+(ary[k-1]=ary[k])*0;//一步交换
changeCount++;
tl=k;//一轮中最后一比较的时候，将k所在索引赋给tl,tl表示以后比较的开始索引值,从向右向左比后，k表示右边的索引
}
compareCount++;
}
left=tl;
}
System.out.println("\n-----orderAsc1升序排序后------比较次数："+compareCount+",交换次数："+changeCount);
for(intj=0;j<len;j++){
System.out.print(ary[j]+"");
}
}
//跟orderAsc1的思路没有区别
staticvoidorderAsc2(int[]ary){
intcompareCount=0;//比较次数
intchangeCount=0;//交换次数
intlen=ary.length;
intl=0,r=len-1,tl,tr;
for(;l<r;){//外层固定循环次数
tl=l+1;
tr=r-1;
/*
*从左向右比，将大的移到后面
*/
for(intk=l;k<r;k++){
if(ary[k]>ary[k+1]){
inttemp=ary[k]+ary[k+1];
ary[k+1]=temp-ary[k+1];
ary[k]=temp-ary[k+1];
changeCount++;
tr=k;
}
compareCount++;
}
r=tr;
/*
*从右向左比，将小的移到前面
*/
for(intk=r;k>l;k--){
if(ary[k]<ary[k-1]){
inttemp=ary[k]+ary[k-1];
ary[k-1]=temp-ary[k-1];
ary[k]=temp-ary[k-1];
changeCount++;
tl=k;
}
compareCount++;
}
l=tl;
}
System.out.println("\n-----orderAsc2升序排序后------比较次数："+compareCount+",交换次数："+changeCount);
for(intj=0;j<len;j++){
System.out.print(ary[j]+"");
}
}
}
打印
-------排序前------ 78317353955697839201899680677 -----orderAsc1升序排序后------比较次数：34,交换次数：22 53173201677680697783839899955