C 语言实现冒泡排序

冒泡排序的基本概念

什么是冒泡排序

冒泡排序（Bubble Sort）是一种简单的比较排序算法。它的基本思想是通过多次比较相邻的元素，如果顺序错误则交换它们，每一趟比较都会将最大（或最小）的元素“冒泡”到数组的末尾（或开头）。就如同水中的气泡，轻的气泡会逐渐浮到水面，而重的则留在水底。

想象有一个无序的数组，我们要对它进行从小到大的排序。冒泡排序会从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，就交换它们的位置。这样，在第一趟比较结束后，数组中最大的元素就会被移动到数组的末尾。接着进行第二趟比较，此时不需要再比较最后一个元素，因为它已经是最大的且在正确的位置上了。重复这个过程，直到所有元素都有序排列。

冒泡排序的工作原理

以一个包含 5 个元素的数组 arr = [5, 4, 3, 2, 1] 为例，我们来详细看看冒泡排序的工作过程。

1. 第一趟排序：

   • 比较 arr[0] 和 arr[1]，即 5 和 4。因为 5 > 4，所以交换它们，数组变为 [4, 5, 3, 2, 1]。
   • 比较 arr[1] 和 arr[2]，即 5 和 3。因为 5 > 3，交换后数组变为 [4, 3, 5, 2, 1]。
   • 比较 arr[2] 和 arr[3]，即 5 和 2。因为 5 > 2，交换后数组变为 [4, 3, 2, 5, 1]。
   • 比较 arr[3] 和 arr[4]，即 5 和 1。因为 5 > 1，交换后数组变为 [4, 3, 2, 1, 5]。第一趟排序结束，最大的元素 5 被移动到了数组的末尾。

2. 第二趟排序：

   • 比较 arr[0] 和 arr[1]，即 4 和 3。因为 4 > 3，交换后数组变为 [3, 4, 2, 1, 5]。
   • 比较 arr[1] 和 arr[2]，即 4 和 2。因为 4 > 2，交换后数组变为 [3, 2, 4, 1, 5]。
   • 比较 arr[2] 和 arr[3]，即 4 和 1。因为 4 > 1，交换后数组变为 [3, 2, 1, 4, 5]。第二趟排序结束，第二大的元素 4 被移动到了倒数第二个位置。

3. 第三趟排序：

   • 比较 arr[0] 和 arr[1]，即 3 和 2。因为 3 > 2，交换后数组变为 [2, 3, 1, 4, 5]。
   • 比较 arr[1] 和 arr[2]，即 3 和 1。因为 3 > 1，交换后数组变为 [2, 1, 3, 4, 5]。第三趟排序结束，第三大的元素 3 被移动到了倒数第三个位置。

4. 第四趟排序：

   • 比较 arr[0] 和 arr[1]，即 2 和 1。因为 2 > 1，交换后数组变为 [1, 2, 3, 4, 5]。第四趟排序结束，此时数组已经完全有序。

冒泡排序的时间复杂度

冒泡排序的时间复杂度取决于比较和交换操作的次数。在最坏情况下，即数组完全逆序时，需要进行 $n(n - 1)/2$ 次比较和交换，其中 $n$ 是数组的长度。这是因为第一趟需要比较 $n - 1$ 次，第二趟需要比较 $n - 2$ 次，以此类推，直到最后一趟比较 1 次。所以，冒泡排序的最坏时间复杂度为 $O(n^2)$。

在最好情况下，即数组已经有序时，冒泡排序只需要进行一趟比较，发现没有元素需要交换，就可以结束排序。此时比较次数为 $n - 1$ 次，时间复杂度为 $O(n)$。

平均时间复杂度也是 $O(n^2)$，因为大多数情况下数组是无序的，平均性能和最坏情况相近。

C 语言实现冒泡排序

简单实现

在 C 语言中，实现冒泡排序相对简单。下面是一个基本的冒泡排序代码示例：

#include <stdio.h>

// 交换两个整数的函数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// 打印数组的函数
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. swap 函数用于交换两个整数的值。它接受两个整数指针作为参数，通过一个临时变量来交换指针所指向的值。
2. bubbleSort 函数实现了冒泡排序的核心逻辑。外层循环控制排序的趟数，一共需要进行 n - 1 趟排序，其中 n 是数组的长度。内层循环用于每一趟中相邻元素的比较和交换，每次内层循环结束后，当前未排序部分的最大元素会被移动到正确的位置。内层循环的次数随着趟数的增加而减少，因为每一趟都会将一个最大元素“冒泡”到数组末尾，所以不需要再对已经排好序的部分进行比较。
3. printArray 函数用于打印数组中的所有元素，方便我们查看排序前后数组的状态。
4. 在 main 函数中，我们定义了一个数组并计算其长度。首先打印原始数组，然后调用 bubbleSort 函数对数组进行排序，最后再次打印数组以查看排序结果。

优化实现

虽然上述基本实现能够正确地对数组进行排序，但在某些情况下可以进一步优化。例如，如果在某一趟排序中没有发生任何交换操作，说明数组已经有序，此时可以提前结束排序，而不需要继续执行剩余的趟数。这种优化可以提高冒泡排序在接近有序数组情况下的性能。

下面是优化后的代码：

#include <stdio.h>

// 交换两个整数的函数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 优化的冒泡排序函数
void optimizedBubbleSort(int arr[], int n) {
    int i, j;
    int swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = 0;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                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);

    optimizedBubbleSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

在优化后的代码中，我们在 optimizedBubbleSort 函数中引入了一个 swapped 标志变量。在每一趟排序开始时，将 swapped 初始化为 0。如果在某一趟排序中发生了交换操作，就将 swapped 设置为 1。在内层循环结束后，检查 swapped 的值，如果它仍然为 0，说明在这一趟排序中没有发生任何交换，即数组已经有序，此时通过 break 语句提前结束外层循环，从而减少不必要的比较操作。

对不同数据类型的扩展

上述示例都是针对整数数组进行排序的。实际上，冒泡排序可以很容易地扩展到对其他数据类型进行排序，只要能够定义合适的比较和交换操作。

例如，假设我们要对浮点数数组进行排序，可以修改代码如下：

#include <stdio.h>

// 交换两个浮点数的函数
void swapFloat(float *a, float *b) {
    float temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序函数，用于浮点数数组
void bubbleSortFloat(float arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swapFloat(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// 打印浮点数数组的函数
void printArrayFloat(float arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%f ", arr[i]);
    }
    printf("\n");
}

int main() {
    float arr[] = {3.14, 1.618, 2.718, 0.577, 1.414};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始浮点数数组: \n");
    printArrayFloat(arr, n);

    bubbleSortFloat(arr, n);

    printf("排序后的浮点数数组: \n");
    printArrayFloat(arr, n);

    return 0;
}

在这个示例中，我们定义了 swapFloat 函数用于交换两个浮点数，bubbleSortFloat 函数用于对浮点数数组进行冒泡排序，以及 printArrayFloat 函数用于打印浮点数数组。通过这些函数，我们实现了对浮点数数组的排序。

同样，如果要对字符数组（字符串）进行排序，可以根据字符的 ASCII 码值来定义比较和交换操作。以下是一个简单的示例：

#include <stdio.h>
#include <string.h>

// 交换两个字符的函数
void swapChar(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序函数，用于字符数组（字符串）
void bubbleSortChar(char arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swapChar(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// 打印字符数组（字符串）的函数
void printArrayChar(char arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%c", arr[i]);
    }
    printf("\n");
}

int main() {
    char arr[] = "banana";
    int n = strlen(arr);

    printf("原始字符串: \n");
    printArrayChar(arr, n);

    bubbleSortChar(arr, n);

    printf("排序后的字符串: \n");
    printArrayChar(arr, n);

    return 0;
}

在这个示例中，swapChar 函数用于交换两个字符，bubbleSortChar 函数根据字符的 ASCII 码值对字符数组进行冒泡排序，printArrayChar 函数用于打印字符数组（字符串）。

冒泡排序与其他排序算法的比较

与选择排序的比较

1. 工作原理：

   • 冒泡排序：通过多次比较相邻元素并交换位置，将最大（或最小）的元素逐步“冒泡”到数组末尾（或开头）。
   • 选择排序：每一趟从未排序的元素中选择最小（或最大）的元素，与未排序部分的第一个元素交换位置。

2. 时间复杂度：

   • 冒泡排序：最坏和平均时间复杂度都是 $O(n^2)$，最好时间复杂度为 $O(n)$（数组已经有序时）。
   • 选择排序：无论数组初始状态如何，时间复杂度始终为 $O(n^2)$。因为选择排序每一趟都需要遍历未排序部分来找到最小（或最大）元素，无论数组是否有序，都需要进行固定次数的比较。

3. 稳定性：

   • 冒泡排序：是稳定的排序算法。在比较相邻元素时，如果两个元素相等，不会交换它们的位置，所以相等元素的相对顺序在排序前后保持不变。
   • 选择排序：是不稳定的排序算法。例如，对于数组 [5, 5, 3]，在选择排序过程中，当第一个 5 被选中与 3 交换位置后，两个 5 的相对顺序就改变了。

与插入排序的比较

1. 工作原理：

   • 冒泡排序：通过相邻元素的比较和交换，逐步将元素移动到合适位置。
   • 插入排序：将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。

2. 时间复杂度：

   • 冒泡排序：最坏和平均时间复杂度为 $O(n^2)$，最好时间复杂度为 $O(n)$。
   • 插入排序：最坏时间复杂度为 $O(n^2)$，当数组基本有序时，插入排序的时间复杂度接近 $O(n)$，平均时间复杂度也为 $O(n^2)$。但在数组部分有序的情况下，插入排序通常比冒泡排序性能更好，因为插入排序在移动元素时，对于已经有序的部分可以快速跳过。

3. 稳定性：

   • 冒泡排序：是稳定的。
   • 插入排序：也是稳定的。在插入元素时，当遇到相等元素时，新元素会插入到相等元素的后面，不会改变相等元素的相对顺序。

与快速排序的比较

1. 工作原理：

   • 冒泡排序：基于相邻元素的比较和交换，是一种比较简单直观的排序方式。
   • 快速排序：采用分治思想，选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于基准元素，右边部分的元素都大于基准元素，然后分别对左右两部分进行递归排序。

2. 时间复杂度：

   • 冒泡排序：最坏和平均时间复杂度为 $O(n^2)$，最好时间复杂度为 $O(n)$。
   • 快速排序：平均时间复杂度为 $O(nlogn)$，最坏时间复杂度为 $O(n^2)$（当每次选择的基准元素都是数组中的最大或最小元素时）。在大多数情况下，快速排序的性能要优于冒泡排序，尤其是对于大规模数据。

3. 稳定性：

   • 冒泡排序：是稳定的。
   • 快速排序：通常是不稳定的。因为在分区过程中，可能会改变相等元素的相对顺序。不过，通过一些特殊的实现方式可以使其成为稳定的排序算法，但这会增加算法的复杂度。

冒泡排序在实际应用中的场景

数据规模较小的情况

当数据规模较小时，冒泡排序的简单性和易于实现的特点使其成为一个不错的选择。例如，在一些嵌入式系统或小型应用程序中，数据量可能只有几十或几百个元素，此时使用冒泡排序可以在不占用过多资源的情况下完成排序任务。而且由于代码简单，易于理解和维护，对于开发周期较短或对性能要求不是特别高的场景，冒泡排序是可行的。

对稳定性有要求的情况

在某些场景下，数据的稳定性非常重要。例如，在对学生成绩进行排序时，如果成绩相同的学生希望保持原来的顺序，冒泡排序的稳定性就可以满足这一需求。而像快速排序等不稳定的排序算法在这种情况下就不太适用。虽然冒泡排序在大规模数据时性能不如一些高效排序算法，但对于这种对稳定性有严格要求且数据规模相对不大的情况，它的优势就体现出来了。

教学和算法演示

冒泡排序是一种基础的排序算法，其原理简单易懂，非常适合用于教学和算法演示。通过讲解冒泡排序，可以让初学者更好地理解排序算法的基本概念、比较和交换操作以及循环结构的应用。在学习编程和算法的初期，冒泡排序是一个很好的切入点，帮助学生建立对排序算法的初步认识，为后续学习更复杂的排序算法打下基础。

作为其他算法的子过程

在一些复杂的算法中，冒泡排序可以作为其中的一个子过程。例如，在某些需要对局部数据进行简单排序的算法中，由于冒泡排序实现简单，直接使用它可以减少代码的复杂性。虽然它可能不是整体算法的核心性能瓶颈，但在局部起到了辅助排序的作用，使得整个算法的逻辑更加清晰和易于实现。

总结冒泡排序的特点

优点

1. 简单易懂：冒泡排序的原理和实现都非常简单，对于初学者来说很容易理解和掌握。它通过相邻元素的比较和交换这种直观的方式进行排序，不需要复杂的数学原理或数据结构知识。
2. 稳定性：冒泡排序是稳定的排序算法，这在一些对元素相对顺序有要求的场景中非常重要，如前面提到的对成绩相同的学生保持原有顺序的情况。
3. 空间复杂度低：冒泡排序在排序过程中只需要几个临时变量来进行交换操作，不需要额外的大量空间。其空间复杂度为 $O(1)$，这使得它在空间有限的环境中，如嵌入式系统或对内存要求严格的应用中，具有一定的优势。

缺点

1. 时间复杂度高：在最坏和平均情况下，冒泡排序的时间复杂度为 $O(n^2)$，这使得它在处理大规模数据时效率较低。随着数据规模的增大，排序所需的时间会急剧增加。
2. 比较次数多：即使在数组已经部分有序的情况下，冒泡排序仍然需要进行较多的比较操作，除非使用优化版本来提前结束排序。这在一定程度上浪费了计算资源，降低了算法的性能。

适用场景与改进方向

1. 适用场景：适用于数据规模较小且对稳定性有要求的场景，或者作为教学和算法演示的示例。在一些对性能要求不高，但对代码简单性和稳定性有需求的应用中，冒泡排序也能发挥作用。
2. 改进方向：可以通过引入标志变量来优化冒泡排序，使其在数组提前有序时能够提前结束，减少不必要的比较。另外，在实际应用中，如果数据规模较大，可以考虑使用更高效的排序算法，如快速排序、归并排序等，这些算法在平均情况下具有更好的时间复杂度。但对于冒泡排序的研究和理解，有助于我们深入掌握排序算法的基本原理和优化方法，为学习和应用更复杂的算法奠定基础。

通过对冒泡排序在 C 语言中的实现、与其他排序算法的比较以及在实际应用中的场景分析，我们可以更全面地了解冒泡排序这一基础排序算法的特点和应用范围，在不同的编程场景中做出更合适的选择。