思路

代码

package com.zgz;/** * 冒泡排序 * 优化思路： * 1. 引入标志位，判断数列是否有序，若有序则跳出不执行剩下的几轮循环 * 2. 界定数列有序区(3，4，2，1，5，6，7，8), 记录最后一次交换的位置，更新无序数列的边界 * @author guozhenZhao * @date 2019年4月4日 */public class BubbleSort { public static void main(String[] args) { int[] arr = {1,2,3,4,5,6,8,9,5,0}; sort(arr); print(arr); } static void sort(int[] arr) { //最好时间复杂度O(n) for(int i=0; i<arr.length; i++) { //标志位，如果上一轮冒泡排序已经全部有序,则减少循环次数 Boolean isSorted = true; //无序数列的边界 int sortBorder = arr.length-1; //最后一次交换的位置 int lastChangePos = 0; for(int j=0; j<arr.length-1-i; j++) { if(arr[j]>arr[j+1]) { swap(arr, j, j+1); //进行了排序，说明元素无序 isSorted = false; //记录元素交换的位置 lastChangePos = j; } } //把无序数列的边界更新为最后一次交换元素的位置 sortBorder = lastChangePos; if(isSorted) { break; } } } static void swap(int[] arr, int i, int j) { int temp = arr[j]; arr[j] = arr[i]; arr[i]= temp; } static void print(int[] arr) { for(int i=0; i<arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println(); }}