Java冒泡排序的不同实现

一、基础版冒泡排序

基础版冒泡排序是最直观的实现方式，其核心思想是重复遍历待排序数组，每次比较相邻的两个元素，若顺序错误则交换位置。

public class BubbleSortBasic {

public static void bubbleSort(int[] arr) {

if (arr == null || arr.length <= 1) {

return;

}

int n = arr.length;

for (int i = 0; i < n - 1; i++) {

for (int j = 0; j < n - 1 - i; j++) {

if (arr[j] > arr[j + 1]) {

// 交换元素

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

}

public static void main(String[] args) {

int[] arr = {64, 34, 25, 12, 22, 11, 90};

bubbleSort(arr);

System.out.println("排序后的数组：");

for (int num : arr) {

System.out.print(num + " ");

}

}

}

在基础版中，外层循环控制排序的轮数，内层循环负责每轮中相邻元素的比较和交换。随着每一轮的进行，最大的元素会 “浮” 到数组的末尾，所以内层循环的范围会逐渐缩小。

二、优化版冒泡排序

基础版存在一个问题：当数组在中途已经排好序时，算法仍会继续执行剩余的循环，造成不必要的开销。优化版通过引入一个标志位来解决这个问题。

public class BubbleSortOptimized {

public static void bubbleSort(int[] arr) {

if (arr == null || arr.length <= 1) {

return;

}

int n = arr.length;

boolean swapped;

for (int i = 0; i < n - 1; i++) {

swapped = false;

for (int j = 0; j < n - 1 - i; j++) {

if (arr[j] > arr[j + 1]) {

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

swapped = true;

}

}

// 如果本轮没有发生交换，说明数组已排好序，提前退出

if (!swapped) {

break;

}

}

}

public static void main(String[] args) {

int[] arr = {64, 34, 25, 12, 22, 11, 90};

bubbleSort(arr);

System.out.println("排序后的数组：");

for (int num : arr) {

System.out.print(num + " ");

}

}

}

优化版中添加了一个swapped标志，当某一轮循环中没有元素交换时，说明数组已经有序，此时直接跳出外层循环，大大减少了不必要的比较操作。

三、双向冒泡排序

双向冒泡排序（也称为鸡尾酒排序）在传统冒泡排序的基础上进行了改进，它不仅会将最大的元素 “浮” 到末尾，还会将最小的元素 “沉” 到开头，从而提高排序效率。

public class CocktailSort {

public static void cocktailSort(int[] arr) {

if (arr == null || arr.length <= 1) {

return;

}

int left = 0;

int right = arr.length - 1;

while (left < right) {

// 从左到右，将最大元素移到右侧

for (int i = left; i < right; i++) {

if (arr[i] > arr[i + 1]) {

int temp = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = temp;

}

}

right--;

// 从右到左，将最小元素移到左侧

for (int i = right; i > left; i--) {

if (arr[i] < arr[i - 1]) {

int temp = arr[i];

arr[i] = arr[i - 1];

arr[i - 1] = temp;

}

}

left++;

}

}

public static void main(String[] args) {

int[] arr = {64, 34, 25, 12, 22, 11, 90};

cocktailSort(arr);

System.out.println("排序后的数组：");

for (int num : arr) {

System.out.print(num + " ");

}

}

}

双向冒泡排序适合处理一些特定的数组，例如当最小的元素位于数组末尾时，传统冒泡排序需要多轮循环才能将其移到正确位置，而双向冒泡排序一次从右到左的遍历就能完成。

四、基于链表的冒泡排序

除了对数组进行排序，冒泡排序也可以应用于链表。基于链表的冒泡排序不需要像数组那样频繁地交换元素，而是通过调整节点的指针来实现排序。

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

public class BubbleSortLinkedList {

public static ListNode bubbleSort(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode end = null;

while (end != head) {

ListNode current = head;

ListNode prev = null;

while (current.next != end) {

if (current.val > current.next.val) {

// 交换节点

ListNode nextNode = current.next;

current.next = nextNode.next;

nextNode.next = current;

if (prev == null) {

head = nextNode;

} else {

prev.next = nextNode;

}

prev = nextNode;

} else {

prev = current;

current = current.next;

}

}

end = current;

}

return head;

}

public static void main(String[] args) {

ListNode head = new ListNode(64);

head.next = new ListNode(34);

head.next.next = new ListNode(25);

head.next.next.next = new ListNode(12);

head.next.next.next.next = new ListNode(22);

head.next.next.next.next.next = new ListNode(11);

head.next.next.next.next.next.next = new ListNode(90);

head = bubbleSort(head);

System.out.println("排序后的链表：");

ListNode current = head;

while (current != null) {

System.out.print(current.val + " ");

current = current.next;

}

}

}

基于链表的冒泡排序在空间复杂度上有一定优势，它不需要额外的数组空间来存储元素，只需操作指针即可。

五、各种实现方式的对比