数据排序的重要性在实际项目开发中的重要性不言而喻,无论是数据整理还是分析都离不开排序这道工序。
冒泡排序——
是一种比较简单的排序方法,也是在数据结构课程中我们学习到的第一种排序方法。但是冒泡排序在简单排序中属于时间复杂度较高的方法,用大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); } } } } }
运行效果: