冒泡排序详解

1. 引言

冒泡排序是一种简单直观的排序算法，其基本思想是通过多次遍历数组，比较相邻元素并交换，使得每一轮遍历后最大的元素都位于数组末尾。

2. 冒泡排序原理

冒泡排序的核心思想是相邻元素两两比较，将较大的元素逐步交换到右侧，通过多轮遍历实现整体排序。

3. 冒泡排序步骤

冒泡排序的具体步骤如下：

从第一个元素开始，依次比较相邻元素。
如果前一个元素大于后一个元素，则交换它们的位置。
继续比较下一组相邻元素，重复步骤2。
一轮遍历后，最大的元素将移动到数组末尾。
重复以上步骤，每轮遍历确定一个最大元素的位置，直至整个数组有序。

4. 冒泡排序代码示例

4. 1 Python语言实现的冒泡排序

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        # 每一轮遍历确定一个最大元素的位置
        for j in range(0, n-i-1):
            # 两两比较相邻元素
            if arr[j] > arr[j+1]:
                # 交换元素位置
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:", arr)

4. 2 Java语言实现的冒泡排序

package org.example;  
  
import java.util.Arrays;  
  
public class BubbleSort {  
    public static void main(String[] args) {  
        int arr[] = {-1, -2, 3, 7, 4, 10};  
  
        bubbleSort(arr);  
  
        int arr2[] = new int[80000];  
        for (int i = 0; i < 80000; i++) {  
            arr2[i] = (int)(Math.random()*8000000);  
        }  
  
        System.out.println("arr2：" + Arrays.toString(arr2));  
  
//        bubbleSort(arr2);  
//        for (int i = 0; i < arr.length - 1 - 0; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第1躺排序：" + Arrays.toString(arr));  
//  
//        for (int i = 0; i < arr.length - 1 - 1; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第2躺排序：" + Arrays.toString(arr));  
//  
//        for (int i = 0; i < arr.length - 3; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第3躺排序：" + Arrays.toString(arr));  
//  
//        for (int i = 0; i < arr.length - 4; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第4躺排序：" + Arrays.toString(arr));  
    }  
  
    public static void bubbleSort(int[] arr){  
        boolean flag = false;//判断是否进行了交换  
        System.out.println("初始数组序列：" + Arrays.toString(arr));  
        int temp = 0;  
  
        for (int j = 0; j < arr.length - 1; j++) {  
            for (int i = 0; i < arr.length - (j + 1); i++) {  
                if (arr[i] > arr[i + 1]) {  
                    flag = true;  
                    temp = arr[i];  
                    arr[i] = arr[i + 1];  
                    arr[i + 1] = temp;  
                }  
            }  
            if (!flag) {  
//                说明没有交换，则可以结束，因为已经有序  
                break;  
            } else {  
                flag = false;  
            }  
            System.out.printf("第%d躺排序：", j + 1);  
            System.out.printf(Arrays.toString(arr));  
            System.out.println();  
        }  
        System.out.println("冒泡排序：" + Arrays.toString(arr));  
    }  
}

5. 冒泡排序的时间复杂度

冒泡排序的时间复杂度为O(n^2)，其中n为数组的长度。这是因为在最坏的情况下，需要进行n轮遍历，每轮遍历的比较次数为n-1。

6. 总结

冒泡排序虽然简单，但在大规模数据集上性能较差，不适合处理大量数据。然而，它的思想易于理解，是初学者学习排序算法的良好起点。在实际应用中，更高效的排序算法如快速排序、归并排序通常被优先选择。

06.1 冒泡排序