首页 > 代码库 > java基础之冒泡排序
java基础之冒泡排序
1.冒泡排序
冒泡排序是一种比较简单的排序算法。算法的原理是：
重复地走访过要排序的数列，一次比较相邻的两个元素，按照规定好的顺序进行比较，如果他们的顺序错误就把他们交换过来。走访数列的工作重复的进行直到没有再需要交换的元素，此时数列的排序已经完成。
核心代码：
1 private static void bubbleSortTest(int arr[]) { 2 int temp = 0; 3 for (int i = 0; i < arr.length-1; i++) { 4 for (int j = arr.length-1; j > i; j--) { 5 if (arr[j-1] > arr[j]) { 6 temp = arr[j-1]; 7 arr[j-1] = arr[j]; 8 arr[j] = temp; 9 }10 }11 }12 }
以上代码完成的工作是采用冒泡排序从小到大排列一个数组。
在外循环中从前往后读数组，然后在内循环中从后往前比较，相邻的数进行两两比较，若前一个数比它相邻的后一个大，则交换他们的位置。每次外循环一次都把第i小的元素移到了arr[i]的位置，所以内循环中的条件是j>i，因为arr[i]前面的都排好了序。每次从后往前比较时，到了arr[i]就不用再继续了。
当然，上面的核心代码也可以写成以下这种形式：
1 private static void bubbleSortTest2(int arr[]) { 2 int temp = 0; 3 for (int i = arr.length-1; i > 0; i++) { 4 for (int j = 0; j < i; j++) { 5 if (arr[j] < arr[j+1]) { 6 temp = arr[j+1]; 7 arr[j+1] = arr[j]; 8 arr[j] = temp; 9 }10 }11 }12 }
这里思想跟上面是一样的，都是相邻两个元素的比较。只是bubbleSortTest2(int arr[])是从前往后比较，把最大的数往后移。
冒泡排序java实现的完整代码：
1 public class BubbleSortTest { 2 3 public static void main(String[] args) { 4 int[] intArr; 5 intArr = new int[]{5,4,3,2,1}; 6 System.out.println("排序前："); 7 printList(intArr); 8 bubbleSortTest(intArr); 9 System.out.println("排序后：");10 printList(intArr);11 }12 /*冒泡排序核心代码*/13 private static void bubbleSortTest(int arr[]) {14 int temp = 0;15 for (int i = 0; i < arr.length - 1; i++) {16 for (int j = arr.length - 1; j > i; j--) {17 if (arr[j - 1] > arr[j]) {18 temp = arr[j - 1];19 arr[j - 1] = arr[j];20 arr[j] = temp;21 }22 }23 }24 }25 26 public static void printList(int[] list) {27 for (int value : list) {28 System.out.print(value + " ");29 }30 System.out.println();31 }32 }
2.冒泡排序的优化版
对冒泡排序常见的优化方法是加入一个标志变量changeFlag，用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换，则说明所有元素排序完成，可直接跳出循环，结束排序。
优化代码：
1 public class BubbleSortTest { 2 3 public static void main(String[] args) { 4 int[] intArr; 5 intArr = new int[]{5,4,3,1,7,8,9}; 6 System.out.println("排序前："); 7 printList(intArr); 8 bubbleSortTest(intArr); 9 System.out.println("排序后：");10 printList(intArr);11 }12 /*冒泡排序核心代码*/13 private static void bubbleSortTest(int arr[]) {14 int temp = 0;15 boolean changeFlag = false;16 17 for (int i = 0; i < arr.length - 1; i++) {18 changeFlag = false;19 for (int j = arr.length - 1; j > i; j--) {20 if (arr[j - 1] > arr[j]) {21 temp = arr[j - 1];22 arr[j - 1] = arr[j];23 arr[j] = temp;24 changeFlag = true; //如果数据进行过交换，把changeFlag置为true25 }26 }27 if(!changeFlag) {28 break; //没有再进行交换，跳出循环29 }30 System.out.print("第" + (i+1) + "次排序结果：");31 printList(arr);32 }33 }34 35 public static void printList(int[] list) {36 for (int value : list) {37 System.out.print(value + " ");38 }39 System.out.println();40 }41 }
运行结果：
此外，这里补充一个通过控制台输入数组进行排序的代码：
1 import java.util.Scanner; 2 public class BubbleSort { 3 4 public static void main(String[] args) { 5 Scanner sc = new Scanner(System.in); 6 System.out.println("请输入要冒泡排序的整数，在同一行以空格隔开："); 7 String intStr = sc.nextLine(); 8 9 String[] strArr = intStr.split(" ");10 int[] intArr = new int[strArr.length];11 12 for (int i = 0; i < strArr.length; i++) {13 intArr[i] = Integer.parseInt(strArr[i]);14 }15 bubbleSortTest(intArr);16 System.out.println("排序后：");17 printList(intArr);18 }19 20 private static void bubbleSortTest(int arr[]) {21 int temp = 0;22 boolean changeFlag = false;23 24 for (int i = 0; i < arr.length-1; i++) {25 changeFlag = false;26 for (int j = arr.length-1; j > i; j--) {27 if (arr[j-1] > arr[j]) {28 temp = arr[j-1];29 arr[j-1] = arr[j];30 arr[j] = temp;31 changeFlag = true;32 }33 } 34 if (!changeFlag) {35 break;36 }37 System.out.print("第" + (i+1) + "次排序结果：");38 printList(arr);39 }40 }41 42 public static void printList(int[] list) {43 for (int value : list) {44 System.out.print(value + " ");45 }46 System.out.println();47 }48 }
java基础之冒泡排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。