Java改进的冒泡排序ImprovedBubbleSort

原理：冒泡排序需要遍历几次数组，每次遍历都要比较相邻的元素，如果某一对降序则互换他们的值，由于较小的值像“气泡”一样浮向顶部，较大的值沉向底部，所以叫冒泡排序。
实例演示：

一般冒泡排序的特点是：n个数总共要比较（遍历）n-1趟，第i趟要比较n-i次。
一般程序是：

public static void bubbleSort(int[] list){int n=list.length;for(int i=1;i<n;i++){//总共比较n-1趟for(int j=0;j<n-i;j++){//第i趟比较n-i次if(list[j]>list[j+1]){int temp;temp=list[j];list[j]=list[j+1];list[j+1]=temp; }}}}

注意！！！：可以看到如果某次遍历没有发生交换，吗么就不必进行下一次遍历，因为所有的元素已经有序了。改进算法效率可以如下：

public static void bubbleSort(int[] list){int n=list.length;boolean NeedNextPass=true;for(int i=1;i<n&&NeedNextPass;i++){//总共比较n-1趟，如果某趟遍历中没有交换，那么不需要下次遍历，因为元素以排好NeedNextPass=false;for(int j=0;j<n-i;j++){//第i趟比较n-i次if(list[j]>list[j+1]){int temp;temp=list[j];list[j]=list[j+1];list[j+1]=temp; NeedNextPass=true;}}}}

一般代码是：

public class BubbleSort {//冒泡排序public static void bubbleSort(int[] list){int n=list.length;for(int i=1;i<n;i++){//总共比较n-1趟for(int j=0;j<n-i;j++){//第i趟比较n-i次if(list[j]>list[j+1]){int temp;temp=list[j];list[j]=list[j+1];list[j+1]=temp; }}}}public static void main(String args[]){int[] list={2,1,56,34,9,6,55,20,37,22}; System.out.println("排序前的list是：");for(int i=0;i<list.length;i++){System.out.print(list[i]+" ");}bubbleSort(list);//进行冒泡排序System.out.println();System.out.println("排序后的list是：");for(int i=0;i<list.length;i++){System.out.print(list[i]+" ");}} }

改进代码是：

public class BubbleImprovedSort {//冒泡排序public static void bubbleSort(int[] list){int n=list.length;boolean NeedNextPass=true;for(int i=1;i<n&&NeedNextPass;i++){//总共比较n-1趟，如果某趟遍历中没有交换，那么不需要下次遍历，因为元素以排好NeedNextPass=false;for(int j=0;j<n-i;j++){//第i趟比较n-i次if(list[j]>list[j+1]){int temp;temp=list[j];list[j]=list[j+1];list[j+1]=temp; NeedNextPass=true;}}}}public static void main(String args[]){int[] list={2,1,56,34,9,6,55,20,37,22}; System.out.println("排序前的list是：");for(int i=0;i<list.length;i++){System.out.print(list[i]+" ");}bubbleSort(list);//进行冒泡排序System.out.println();System.out.println("排序后的list是：");for(int i=0;i<list.length;i++){System.out.print(list[i]+" ");}} }

总结

以上是生活随笔为你收集整理的Java改进的冒泡排序ImprovedBubbleSort的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。