跳到主要内容

冒泡排序

代码​

C语言代码：

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        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;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    bubble_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

代码解释​

  1. 初始化：数组 arr 是待排序的数组，n 是数组的长度。
  2. 主排序循环：
    • 外部 for 循环控制轮数，从第0轮到第 n-2 轮。（最后一个自动有序）
    • 内部 for 循环控制每一轮的比较次数，从第0个元素到第 n-i-2 个元素。
    • 比较相邻元素，如果前一个元素大于后一个元素，则交换两者的位置。
  3. 结果输出：排序完成后，输出排序后的数组。

示例运行​

假设输入数组为 {64, 34, 25, 12, 22, 11, 90}：

  1. 初始状态：{64, 34, 25, 12, 22, 11, 90}
  2. 第一次外部循环（i=0）：
    • 比较并交换：{34, 64, 25, 12, 22, 11, 90}
    • 比较并交换：{34, 25, 64, 12, 22, 11, 90}
    • 比较并交换：{34, 25, 12, 64, 22, 11, 90}
    • 比较并交换：{34, 25, 12, 22, 64, 11, 90}
    • 比较并交换：{34, 25, 12, 22, 11, 64, 90}
    • 最后一轮：{34, 25, 12, 22, 11, 64, 90}
  3. 第二次外部循环（i=1）：
    • 比较并交换：{25, 34, 12, 22, 11, 64, 90}
    • 比较并交换：{25, 12, 34, 22, 11, 64, 90}
    • 比较并交换：{25, 12, 22, 34, 11, 64, 90}
    • 比较并交换：{25, 12, 22, 11, 34, 64, 90}
    • 最后一轮：{25, 12, 22, 11, 34, 64, 90}
  4. 如此反复，直到数组完全有序。

最终结果：{11, 12, 22, 25, 34, 64, 90}

时间复杂度分析​

冒泡排序的时间复杂度取决于数组的初始顺序。

  • 最优时间复杂度：当输入数组已经有序时，只需要进行 O(n)O(n) 次比较，不需要交换，时间复杂度为 O(n)O(n)。
  • 最坏时间复杂度：当输入数组是逆序时，冒泡排序需要进行最多的比较和交换操作，时间复杂度为 O(n2)O(n^2)。
  • 平均时间复杂度：在一般情况下，冒泡排序的时间复杂度为 O(n2)O(n^2)。

空间复杂度分析​

冒泡排序是一种原地排序算法，不需要额外的辅助空间，空间复杂度为 O(1)O(1)。在本实现中，我们仅使用了几个额外的变量（i, j, temp），因此空间复杂度保持为常数级别。

优缺点​

优点：

  • 简单易实现。
  • 稳定排序算法，不改变相同元素的相对顺序。
  • 原地排序，空间复杂度低。

缺点：

  • 时间复杂度较高，尤其是对大规模数据，效率较低。
  • 即使数组已经部分有序，仍然需要完整的比较和交换操作。

适用场景​

冒泡排序适用于以下场景：

  • 数据量较小的排序。
  • 需要一个简单且稳定的排序算法时。
  • 学习和教学用途，以理解基本的排序原理。

总结​

冒泡排序是一种简单直观的排序算法，通过重复地比较和交换相邻元素，使得较大的元素逐步“冒泡”到数组末端。尽管其最坏情况下的时间复杂度较高，但在特定场景下，尤其是数据量较小时，冒泡排序仍然是一个有效的选择。