C语言算法–冒泡排序

1-什么是冒泡排序

冒泡排序是一种简单的排序算法，它通过比较相邻元素的大小，并根据需要交换它们的位置来排序数据。它的名称来自于越小的元素会慢慢“冒泡”到数组的开头。

冒泡排序的基本思想是从数组的第一个元素开始，依次比较相邻的两个元素的大小，并根据需要进行交换，使较大的元素逐渐向数组的末尾移动。在一次遍历中，最大的元素会被交换到数组的最后一个位置。然后，再进行下一次遍历，但这次只需比较到倒数第二个元素，依次类推。每次遍历都会将当前未排序的最大元素放置到正确的位置。

如下图（图片来源于图解算法使用C语言）：

从上面我们可以看到，第一次先对55和23进行比较，如果其中的一个大于另一个则进行互换，假设55号大于23号中的元素。然后在接着对55号和87号进行比较，就这样一直比较下去，直到完成确定完整的为止。

2-冒泡排序的优点

1. 简单易懂：冒泡排序的实现逻辑相对简单，容易理解和实现。它只需要使用基本的比较和交换操作就可以完成排序。
2. 原地排序：冒泡排序是一种原地排序算法，不需要额外的空间来存储排序结果。它只需要在原始数组上进行元素的比较和交换操作。
3. 稳定性：冒泡排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。只有当两个相邻元素进行交换时才会改变它们的相对顺序。
4. 适用于小规模数据：由于冒泡排序的时间复杂度为O(n^2)，在数据规模较小的情况下，冒泡排序的性能还是可以接受的。对于小规模的数据集，冒泡排序可能比其他复杂的排序算法更快。

3- 冒泡排序的缺点

1. 时间复杂度高：冒泡排序的时间复杂度是O(n^2)，其中n是待排序元素的个数。这意味着随着数据规模的增大，排序所需的比较和交换操作的次数会成平方倍增长。对于大规模数据集，冒泡排序的性能较差。
2. 低效的性能：由于冒泡排序的特性，它在实际应用中的性能往往不如其他高效的排序算法。冒泡排序需要多次迭代才能将最大（或最小）元素移动到正确的位置，这可能导致大量的不必要比较和交换操作。
3. 不适合大规模数据：由于冒泡排序的复杂度较高，它在处理大规模数据时效率较低。当数据集很大时，冒泡排序的执行时间可能会非常长，无法满足实时性要求。
4. 缺乏适应性：冒泡排序的算法逻辑是通过相邻元素的比较和交换来逐步将较大（或较小）的元素“冒泡”到数组的末尾。这意味着即使在部分已经有序的情况下，冒泡排序仍然需要进行完整的比较和交换操作，无法充分利用已排序的部分。

4-冒泡排序可以应用哪些场景

1. 小规模数据集：冒泡排序适用于处理小规模数据集，其中元素数量相对较少。在这种情况下，冒泡排序的性能可以接受，并且实现起来简单。
2. 部分有序的数据：如果待排序的数据集已经部分有序，即只有少量元素需要进行排序，而其他元素已经有序，那么冒泡排序的性能会相对较好。由于冒泡排序会在每一轮迭代中扫描整个数组，但对于已经有序的部分，它可以快速跳过，减少不必要的比较和交换操作。
3. 教育和理论研究：冒泡排序作为一种经典的排序算法，可以用于教育目的或理论研究中。它的实现简单，易于理解和教授。通过实现和分析冒泡排序，可以帮助学习者理解排序算法的基本原理和算法复杂度分析。

5-举例

#include <stdio.h>

void bubbleSort(int arr[], int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - 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[] = {5, 2, 8, 12, 1, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：");
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }

    bubbleSort(arr, size);

    printf("\n排序后的数组：");
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

运行结果：

#include <stdio.h>

// 定义结构体
typedef struct
{
    int value;

} Element;

// 定义枚举类型
typedef enum
{
    ASCENDING,
    DESCENDING
} SortOrder;

// 冒泡排序函数
void bubbleSort(Element arr[], int size, SortOrder sortOrder)
{
    int i, j;
    Element temp;

    for (i = 0; i < size - 1; i++)
    {
        for (j = 0; j < size - i - 1; j++)
        {
            // 根据排序顺序进行比较
            if ((sortOrder == ASCENDING && arr[j].value > arr[j + 1].value) ||
                (sortOrder == DESCENDING && arr[j].value < arr[j + 1].value))
            {
                // 交换元素
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main()
{
    Element arr[] =
    {
        {5},
        {2},
        {8},
        {1},
        {9}
        };
    int size = sizeof(arr) / sizeof(Element);
    int i;

    printf("原始数组: ");
    for (i = 0; i < size; i++)
    {
        printf("%d ", arr[i].value);
    }
    printf("\n");

    // 升序排序
    bubbleSort(arr, size, ASCENDING);

    printf("排序数组(升序): ");
    for (i = 0; i < size; i++)
    {
        printf("%d ", arr[i].value);
    }
    printf("\n");

    // 降序排序
    bubbleSort(arr, size, DESCENDING);

    printf("排序数组(降序): ");
    for (i = 0; i < size; i++)
    {
        printf("%d ", arr[i].value);
    }
    printf("\n");

    return 0;
}