频道栏目
首页 > 资讯 > Java > 正文

Java两种形式实现冒泡排序(代码实例)

18-05-26        来源:[db:作者]  
收藏   我要投稿

数据排序的重要性在实际项目开发中的重要性不言而喻,无论是数据整理还是分析都离不开排序这道工序。

冒泡排序——

是一种比较简单的排序方法,也是在数据结构课程中我们学习到的第一种排序方法。但是冒泡排序在简单排序中属于时间复杂度较高的方法,用大O表示法为O(N*N)。可是虽然如此,这种排序的思想仍然需要我们去很好的掌握,而且由于其在理解上较为容易,所以在数据量较少(此数量级基本上感觉不到冒泡排序的笨拙)的情况下使用起来也是相当顺手的。

排序思想:

此处借助《Java数据结构和算法》一书中的形象例子来呈现:

我们从这幅图中可以很清楚的找到冒泡排序的思想,即从左向右依次俩俩比较,较大者向右移动,若比较时较大者本在右侧则不做右移操作,也因为此操作使得实际的比较次数>交换次数。经过N*(N-1)/2次的比较后完成排序操作(若有10个数要进行9+8+7+6+5+4+3+2+1此比较)。

代码实现——

我们将通过用户指定输入的数组大小,自动产生一个整数类型的数组,然后进行冒泡排序。

import java.util.Random;  
import java.util.Scanner;  
public class BubbleSort{  
    //test the bubbleSort  
    public static void main(String[] aegs){  
        Scanner sc=new Scanner(System.in);  
        int[] array=null;  
        //produce a array  
        ArrayUtil util=new ArrayUtil();  
        System.out.println("Pleace set array`s size:");  
        int size=sc.nextInt();  
        array=util.produce(size);  
        System.out.println("Before sort!");  
        util.show(array);  
        Sort s=new Sort(array);  
        array=s.sortArray();  
        //show sorted array  
        System.out.println("After sort!");  
        util.show(array);  
        System.out.format("compairsion_times:%d--exchange_times:%d",s.getComparisiontimes(),s.getExchangetimes());  
    }  
}  
class Sort{  
    private int[] arr=null;  
    private int EXCHANGE_TIMES=0;  
    private int COMPIRASION_TIMES=0;  
    public Sort(int[] array){  
        arr=array;  
    }  
    public int[] sortArray(){  
        //this array is not empty  
        if(arr!=null&&arr.length>0){  
            //sort array  
            int temp=0;  
            int index=0;  
            int count=0;  
            //method1(根据冒泡思想衍生出的另一种书写方式,while+for实现)  
            while(true){  
                for(int i=index+1;i<arr.length-count;i++){  
                    if(arr[index]>arr[i]){  
                        temp=arr[i];  
                        arr[i]=arr[index];  
                        arr[index]=temp;  
                        EXCHANGE_TIMES++;  
                    }  
                    COMPIRASION_TIMES++;  
                    index++;  
                }  
                index=0;  
                count++;  
                if(count==arr.length-1){  
                    break;  
                }  
            }  
            //method2  
                   /*(方法二,也是我们书本上常见的书写方式,通过俩层for循环完成排序) 
            for(int i=arr.length-1;i>1;i--){ 
                for(int j=0;j<i;j++){ 
                    if(arr[j]>arr[j+1]){ 
                        EXCHANGE_TIMES++; 
                        temp=arr[j+1]; 
                        arr[j+1]=arr[j]; 
                        arr[j]=temp; 
                    } 
                    COMPIRASION_TIMES++; 
                } 
                 
            } 
            */  
            return arr;  
        }else{  
            return null;  
        }  
    }  
    //get exchange times(获取排序时交换次数)  
    public int getExchangetimes(){  
        return EXCHANGE_TIMES;  
    }  
      
    //get comparision times(获取排序时比较次数)  
    public int getComparisiontimes(){  
        return COMPIRASION_TIMES;  
    }  
}  
//tool class(此类完成数组的自动生成和数组数据的显示)  
class ArrayUtil{  
    private int[] arr=null;  
    //make a array(产生指定大小的数组)  
    public int[] produce(int num){  
        Random rand=new Random(500);  
        arr=new int[num];  
        for(int i=0;i<num;i++){  
            arr[i]=rand.nextInt(100);  
        }  
        return arr;  
    }  
    //show array(显示数组数据)  
    public void show(int[] array){  
        if(array!=null){  
            for(int a:array){  
                if(a==array[array.length-1]){  
                  System.out.format("%d\n",a);  
                }else{  
                  System.out.format("%d->",a);  
                }  
            }  
        }  
    }  
  
}   

运行效果:

相关TAG标签
上一篇:进程–multiprocessing模块解析
下一篇:编程开发练习题Subsets II
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站