您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# Java冒泡排序代码怎么实现
## 一、排序算法概述
排序算法是计算机科学中最基础也是最重要的算法类别之一。在数据处理、数据库操作、信息检索等众多领域，排序都扮演着关键角色。根据统计，商业计算机系统中约有25%的计算周期都用于排序操作。在众多排序算法中，冒泡排序因其简单直观的特性，成为初学者学习算法的经典案例。
排序算法主要可以分为两大类：
1. **比较排序**：通过比较元素间的大小关系来决定排序顺序，如冒泡排序、快速排序、归并排序等
2. **非比较排序**：不通过比较来决定元素顺序，如计数排序、基数排序、桶排序等
冒泡排序(Bubble Sort)属于最简单的比较排序算法之一，其名称来源于较大的元素会像气泡一样逐渐"浮"到数组的顶端。虽然在实际应用中效率不高，但作为教学工具，它能够很好地帮助理解算法设计和分析的基本概念。
## 二、冒泡排序基本原理
冒泡排序的核心思想是通过重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个过程的重复进行直到没有再需要交换的元素为止，此时数列已经排序完成。
### 2.1 算法步骤详解
1. **比较相邻元素**：从数组的第一个元素开始，比较当前元素与下一个元素
2. **交换元素位置**：如果当前元素大于下一个元素（对于升序排序），则交换它们的位置
3. **移动至下一位置**：移动到数组的下一个位置，重复上述比较
4. **完成一轮遍历**：当遍历完整个数组后，最大的元素会"冒泡"到数组的最后位置
5. **重复过程**：对除最后一个元素外的所有元素重复上述过程
6. **终止条件**：当一轮遍历中没有发生任何交换时，说明数组已经有序，算法可以终止
### 2.2 时间复杂度分析
冒泡排序的时间复杂度是衡量其效率的重要指标：
- **最坏情况**：当数组是逆序排列时，需要进行n(n-1)/2次比较和交换，时间复杂度为O(n²)
- **最好情况**：当数组已经有序时，只需进行n-1次比较，时间复杂度为O(n)
- **平均情况**：时间复杂度为O(n²)
### 2.3 空间复杂度分析
冒泡排序是一种**原地排序算法**，它只需要常量级的额外空间来存储临时变量（用于元素交换），因此空间复杂度为O(1)。
### 2.4 稳定性分析
冒泡排序是**稳定排序算法**，因为相等的元素在排序过程中不会改变相对位置。只有当相邻元素不满足排序条件时才会交换，这保证了相等元素的原始顺序得以保留。
## 三、基础冒泡排序实现
### 3.1 基本实现代码
```java
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制遍历轮数
for (int i = 0; i < n - 1; i++) {
// 内层循环进行相邻元素比较
for (int j = 0; j < n - i - 1; j++) {
// 如果前一个元素大于后一个元素，则交换
if (arr[j] > arr[j + 1]) {
// 交换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};
System.out.println("排序前数组:");
for (int num : arr) {
System.out.print(num + " ");
}
bubbleSort(arr);
System.out.println("\n排序后数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
n-i-1，因为每轮后最大的元素已经移动到正确位置以数组[5, 3, 8, 6, 2]为例：
第一轮： - 比较5和3 → 交换 → [3,5,8,6,2] - 比较5和8 → 不交换 - 比较8和6 → 交换 → [3,5,6,8,2] - 比较8和2 → 交换 → [3,5,6,2,8]
第二轮： - 比较3和5 → 不交换 - 比较5和6 → 不交换 - 比较6和2 → 交换 → [3,5,2,6,8]
第三轮： - 比较3和5 → 不交换 - 比较5和2 → 交换 → [3,2,5,6,8]
第四轮： - 比较3和2 → 交换 → [2,3,5,6,8]
排序完成。
虽然基础冒泡排序可以完成任务，但在某些情况下效率较低。以下是几种常见的优化方法：
如果在某一轮遍历中没有发生任何交换，说明数组已经有序，可以提前终止算法。
public static void optimizedBubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; 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 furtherOptimizedBubbleSort(int[] arr) {
int n = arr.length;
int lastSwapPos = n - 1;
for (int i = 0; i < n - 1; i++) {
int currentSwapPos = 0;
for (int j = 0; j < lastSwapPos; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
currentSwapPos = j;
}
}
lastSwapPos = currentSwapPos;
if (lastSwapPos == 0) break;
}
}
传统冒泡排序只单向移动元素，鸡尾酒排序则双向交替进行。
public static void cocktailSort(int[] arr) {
boolean swapped = true;
int start = 0;
int end = arr.length;
while (swapped) {
swapped = false;
// 从左到右的冒泡
for (int i = start; i < end - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
end--;
swapped = false;
// 从右到左的冒泡
for (int i = end - 1; i >= start; i--) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
start++;
}
}
| 版本 | 最好情况 | 最坏情况 | 平均情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 基础版 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 提前终止 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 记录交换位置 | O(n) | O(n²) | 优于基础版 | O(1) | 稳定 |
| 鸡尾酒排序 | O(n) | O(n²) | 通常优于基础版 | O(1) | 稳定 |
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 稳定 | 教学、小数据集 |
| 选择排序 | O(n²) | O(1) | 不稳定 | 交换成本高的场景 |
| 插入排序 | O(n²) | O(1) | 稳定 | 部分有序或小数据集 |
虽然冒泡排序在时间复杂度上不如快速排序、归并排序等高效算法，但在某些特定场景下仍有其应用价值：
初学者常犯的错误是在内层循环中使用错误的边界条件：
// 错误示例：可能导致ArrayIndexOutOfBoundsException
for (int j = 0; j < n - i; j++) {
if (arr[j] > arr[j + 1]) { // 当j=n-i-1时，j+1将越界
// 交换代码
}
}
解决方案：确保内层循环的上界为n-i-1
如果需要保持相等元素的原始顺序，应使用严格的大于比较：
// 保持稳定性的正确比较方式
if (arr[j] > arr[j + 1]) { // 使用>而不是>=
// 交换代码
}
过度优化可能导致代码复杂而收益有限。应根据实际需求选择合适的优化级别。
虽然冒泡排序本质上是顺序算法，但可以通过奇偶排序(Odd-Even Sort)实现并行化：
public static void oddEvenSort(int[] arr) {
boolean sorted = false;
int n = arr.length;
while (!sorted) {
sorted = true;
// 奇数阶段
for (int i = 1; i < n - 1; i += 2) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
sorted = false;
}
}
// 偶数阶段
for (int i = 0; i < n - 1; i += 2) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
sorted = false;
}
}
}
}
虽然不推荐（因为效率低且可能栈溢出），但冒泡排序也可以用递归实现：
public static void recursiveBubbleSort(int[] arr, int n) {
// 基本情况：如果只有一个元素，已经有序
if (n == 1) return;
boolean swapped = false;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
// 如果没有交换，数组已经有序
if (!swapped) return;
// 递归处理剩余元素
recursiveBubbleSort(arr, n - 1);
}
使冒泡排序能够处理各种可比较的数据类型：
public static <T extends Comparable<T>> void genericBubbleSort(T[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {
T temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
使用JUnit测试冒泡排序的正确性：
import org.junit.Test;
import static org.junit.Assert.*;
public class BubbleSortTest {
@Test
public void testBubbleSort() {
int[] arr = {5, 3, 8, 6, 2};
int[] expected = {2, 3, 5, 6, 8};
BubbleSort.bubbleSort(arr);
assertArrayEquals(expected, arr);
}
@Test
public void testOptimizedBubbleSortWithSortedArray() {
int[] arr = {1, 2, 3, 4, 5};
int[] expected = {1, 2, 3, 4, 5};
BubbleSort.optimizedBubbleSort(arr);
assertArrayEquals(expected, arr);
}
@Test
public void testCocktailSort() {
int[] arr = {34, 2, 10, -9, 5, 8};
int[] expected = {-9, 2, 5, 8, 10, 34};
BubbleSort.cocktailSort(arr);
assertArrayEquals(expected, arr);
}
}
比较不同实现在不同数据规模下的表现：
import java.util.Random;
public class PerformanceTest {
public static void main(String[] args) {
int[] sizes = {100, 1000, 5000, 10000};
Random random = new Random();
for (int size : sizes) {
int[] arr1 = new int[size];
int[] arr2 = new int[size];
int[] arr3 = new int[size];
for (int i = 0; i < size; i++) {
int num = random.nextInt(size * 10);
arr1[i] = num;
arr2[i] = num;
arr3[i] = num;
}
System.out.println("\n测试数据规模: " + size);
long start = System.currentTimeMillis();
BubbleSort.bubbleSort(arr1);
long end = System.currentTimeMillis();
System.out.println("基础冒泡排序耗时: " + (end - start) + "ms");
start = System.currentTimeMillis();
BubbleSort.optimizedBubbleSort(arr2);
end = System.currentTimeMillis();
System.out.println("优化冒泡排序耗时: " + (end - start) + "ms");
start = System.currentTimeMillis();
BubbleSort.cocktailSort(arr3);
end = System.currentTimeMillis();
System.out.println("鸡尾酒排序耗时: " + (end - start) + "ms");
}
}
}
冒泡排序虽然在实际应用中较少使用，但作为算法学习的起点具有重要意义：
Arrays.sort()方法针对不同情况进行了优化”`java /** * 冒泡排序及其优化实现合集 */ public class BubbleSort {
// 基础冒泡排序
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
// 优化冒泡排序：提前终止
public static void optimizedBubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。