排序一 几种冒泡排序的比较和优化

如题所述

package com.asin.algorithm;

import java.util.Arrays;

public class BubbleSort {

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

/**
 * 最简单的排序实现
 * 
 * 当i = 1, j = 8时，虽然把2排到前面了，但是也把3排到了最后，效率非常低
 */
private static void sort1(int[] arr) {

int sumSwap = 0, sumIn = 0, sumOut = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
swap(arr, i, j);
sumSwap++;
}
sumIn++;
}
sumOut++;
}
System.out.println("sort1执行次数：sumSwap:" + sumSwap + " sumIn:" + sumIn + " sumOut:" + sumOut);
System.out.println(Arrays.toString(arr));
}

/**
 * 冒泡排序，从底往上遍历
 * 
 * 当i=2时，把4往前排了，还把3往前排了，最终把2排到第二位
 */
private static void sort2(int[] arr) {

int sumSwap = 0, sumIn = 0, sumOut = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = arr.length - 1; j > i; j--) {
if (arr[j - 1] > arr[j]) {
swap(arr, j - 1, j);
sumSwap++;
}
sumIn++;
}
sumOut++;
}
System.out.println("sort2执行次数：sumSwap:" + sumSwap + " sumIn:" + sumIn + " sumOut:" + sumOut);
System.out.println(Arrays.toString(arr));
}

/**
 * 冒泡排序优化，避免了已经是有序的情况下的无意义的循环
 * 
 * 9, 1, 5, 8, 3, 7, 4, 6, 2
 * 
 * 2, 1, 3, 4, 5, 6, 7, 8, 9 这种情况下，只需要把2和1交换
 */
private static void sort3(int[] arr) {

int sumSwap = 0, sumIn = 0, sumOut = 0;
boolean flag = true;
for (int i = 0; i < arr.length && flag; i++) {// i < arr.length && flag
flag = false;
for (int j = arr.length - 1; j > i; j--) {
if (arr[j - 1] > arr[j]) {// 数组是否有序
swap(arr, j - 1, j);
flag = true;// 交换后，再判断
sumSwap++;
}
sumIn++;
}
sumOut++;
}
System.out.println("sort3执行次数：sumSwap:" + sumSwap + " sumIn:" + sumIn + " sumOut:" + sumOut);
System.out.println(Arrays.toString(arr));
}

/**
 * 测试比较混乱的数组
 */
private static void arr1() {
int[] arr1 = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
sort1(arr1);
int[] arr2 = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
sort2(arr2);
int[] arr3 = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
sort3(arr3);
}

/**
 * 测试不太混乱的数组
 */
private static void arr2() {
int[] arr1 = { 2, 1, 3, 4, 5, 6, 7, 8, 9 };
sort1(arr1);
int[] arr2 = { 2, 1, 3, 4, 5, 6, 7, 8, 9 };
sort2(arr2);
int[] arr3 = { 2, 1, 3, 4, 5, 6, 7, 8, 9 };
sort3(arr3);
}

public static void main(String[] args) {

arr1();// 比较混乱的数组
arr2();// 不太混乱的数组
}

温馨提示：内容为网友见解，仅供参考

当前网址：https://11.t2y.org/zz/mps48ff2m4mff8284m.html