【数据结构】冒泡排序

冒泡排序是一种简单的排序算法。

它基于重复地交换相邻元素的位置。算法的每一步都会比较相邻的两个元素，如果它们的顺序错误（即第一个元素比第二个元素大），则交换它们。这样，每经过一轮比较和交换，数组中最大的元素就会“冒泡”到数组的最后位置。这个过程重复进行，每次循环时排除已经排序好的最大元素，直到整个数组排序完成。

以下是冒泡排序的基本步骤：

1. 比较相邻的元素：从数组的第一个元素开始，比较相邻的两个元素的大小。
2. 交换元素：如果第一个元素比第二个元素大，则交换它们的位置。
3. 对下一个元素重复上述步骤：对数组中的每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对。这样，在第一轮结束后，最大的元素就位于数组的最后一个位置。
4. 重复步骤1-3：对数组的前 n-1 个元素重复上述步骤，因为最后一个元素已经是最大的了。每轮结束后，最大的元素都会“冒泡”到它应该在的位置。
5. 持续排序：持续进行上述过程，每次循环时减少要比较的元素数量（因为每轮都会有一个元素被放到正确的位置），直到没有任何一对元素需要交换，这时数组就完全排序好了。

冒泡排序的平均和最坏时间复杂度都是 O(n^2)，其中 n 是数组的长度。这是因为它需要比较所有相邻元素对，并且在最坏的情况下，每个元素都需要移动到数组的另一端。不过，冒泡排序有一个优点，就是它是稳定的排序算法，即相等的元素在排序后保持它们的原始顺序。此外，如果在一轮比较中没有发生任何交换，冒泡排序可以提前终止，这提供了一种优化手段。

示例代码：使用 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]) {
                // 交换 arr[j] 和 arr[j + 1]
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        // 如果内循环中没有发生交换，说明数组已经排序完成
        if (swapped == 0) {
            break;
        }
    }
}
 
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    bubbleSort(arr, n);
    
    printf("排序后数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

这段代码定义了一个 bubbleSort 函数，它接受一个整数数组和数组的长度。然后，它使用冒泡排序算法对数组进行排序。在 main 函数中，我们定义了一个示例数组，调用 bubbleSort 函数对其进行排序，并打印排序前后的数组。

运行这段代码，你将看到以下输出：

原数组：
64 34 25 12 22 11 90
排序后数组：
11 12 22 25 34 64 90

以上就是冒泡排序的基本使用方法，本次代码分享到此结束，后续还会分享数据结构与算法有关代码。最后的最后，还请大家点点赞，点点关注，谢谢大家!