冒泡排序之Java实现

淡淡的烟草味﹌ 2022-06-16 04:11 140阅读 0赞

冒泡法思路（由小到大排序）：给定的整形数组的两个相邻数据进行比较，大的数组移动到后边；依次类推，遍历整个数组执行前面的操作。

实现：

public static void bubbleSort(int [] arr){
    		for(int i = 0 ; i < arr.length ; i++){
    			
    			for(int j = 1 ; j < arr.length - i ; j++){
    				if(arr[j] < arr[j-1]){
    					int temp = arr[j];
    					arr[j] = arr[j-1];
    					arr[j-1] = temp;
    				}
    			}
    			
    		}
    	}

但是这样实现的话，效率会很低，假设一种情况，一个数组后边几个数据都是有序的。采用上述算法，会白白进行很多步无效运算。

如果能够标识在每趟某一数组元素之后，不会再产生数据交换操作，那么以后的遍历就都可以省去了。

改进：

public static void bubbleSort(int [] arr){
    		
    		int k = 0;
    		boolean flag = true;
    		while(flag){
    			flag = false;
    			for(int j = 1 ; j < arr.length-k;j++){
    				if(arr[j] < arr[j-1]){
    					int temp = arr[j];
    					arr[j] = arr[j-1];
    					arr[j-1] = temp;
    					flag = true;
    				}
    			}
    			k++;
    		}
    		
    	}

当然还存在一种情况，假设一个数组，只有前两个数据是无序的，后边的数据都是有序的，上边的算法也会损失一部分效率。

改进：

public static void bubbleSort(int [] arr){
    		int k  = 0;
    		int n = arr.length;
    		boolean flag = true;
    		while(flag){
    			flag = false;
    			for(int j = 1 ; j < n;j++){
    				if(arr[j] < arr[j-1]){
    					int temp = arr[j];
    					arr[j] = arr[j-1];
    					arr[j-1] = temp;
    					flag = true;
    					k = j;
    				}
    			}
    			n = k;
    		}
    	}

测试方法：

public static void main(String[] args) {
    		int [] arr = {5,9,1,3,52,13,8,4};
    		bubbleSort(arr);
    		for(int i : arr){
    			System.out.println(i);
    		}
    	}

参考资料：http://blog.csdn.net/morewindows/article/details/6657829