冒泡排序及其改进

import java.util.Arrays; /* * 冒泡排序及其优化： */ public class maopaoSort { //原始的冒泡排序 public static void bubbleSort1(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } } // 优化1 ：添加标志位 public static void bubbleSort2(int[] arr) { boolean flag; for (int i = 0; i < arr.length - 1; i++) { flag = false; for (int j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = true; } } if (!flag) { break; // 如果上一遍遍历 flag没有发生变化交换说明已经排好了，直接跳出 } } } //优化2：用 last记录最后一次交换的地址，那么[last--length]之间肯定是排好的， // 下次直接从[0--last]开始 public static void bubbleSort3(int[] arr) { int last = arr.length - 1; //初始位置 int last_temp = 0; for (int i = 0; i < arr.length - 1; i++) { last_temp = last; for (int j = 0; j < last_temp; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; last = j; } } if (last == last_temp) {//结合优化1 break; } } } public static void main(String[] args) { int[] a = { 0, 1, 2, 3, 4, 9, 7, 56, 89, 6, 7,9 }; bubbleSort3(a); System.out.println(Arrays.toString(a)); } }