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置为true 25 } 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 }