排序算法 - 冒泡

1. 冒泡排序

1.1 简介

冒泡排序（Bubble Sort）是一种简单的排序算法，其基本思想是通过相邻元素的比较和交换，把最大的元素逐步“冒泡”到列表的末尾。该算法的名称来源于较小的元素会逐渐“浮”到列表的顶端，而较大的元素则逐渐“沉”到列表的底部，就像气泡在水中上升和下沉一样。

1.2 基本步骤：

1. 比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。如果前一个元素比后一个元素大，则交换它们的位置。

2. 遍历列表：重复上述过程，直到列表的末尾。这一轮操作结束后，最大的元素会被移动到列表的最后一个位置。

3. 重复步骤：再次从列表的第一个元素开始，重复上述过程，但这次不再包括最后一个已经排好的元素。

4. 终止条件：重复上述步骤，直到整个列表有序（即没有需要交换的元素）。

1.3 示例代码（C）

#include <stdio.h>

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        // 提前退出标志，如果在一轮中没有发生交换，说明数组已经有序
        int swapped = 0;
        for (j = 0; j < n-i-1; j++) {
            // 如果前一个元素大于后一个元素，则交换它们
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1; // 标记发生了交换
            }
        }
        // 如果没有发生交换，说明数组已经有序，提前退出循环
        if (swapped == 0) {
            break;
        }
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("排序前的数组: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

1.4 复杂度分析

• 时间复杂度：

  • 最优情况（列表已经有序）：O(n)，因为只需遍历一次就可以确定列表已经有序。
  • 最坏情况（列表完全逆序）：O(n^2)，因为每一轮都需要遍历整个列表，并且需要进行n-1次比较和交换。
  • 平均情况：O(n^2)

• 空间复杂度：O(1)，因为冒泡排序是原地排序，不需要额外的存储空间。

1.5 动画展示