首页 > 编程笔记 > 算法

C语言冒泡排序（附带源码和解析）

冒泡排序是一种简单直观的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个过程会一直重复，直到没有再需要交换的元素，也就是说该数列已经排序完成。
 

这个算法之所以叫"冒泡"排序，是因为越小的元素会经由交换慢慢"浮"到数列的顶端，就如同水中的气泡最终会上浮到水面一样。

冒泡排序的基本原理

冒泡排序的核心思想是通过相邻元素的比较和交换，将最大（或最小）的元素逐步“冒泡”到数列的一端。具体来说，冒泡排序的原理如下：

  1. 比较相邻的元素。如果第一个比第二个大（升序排列），就交换它们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。


为了更好地理解冒泡排序的过程，我们来看一个具体的例子，假设我们要对数组 [5, 2, 8, 12, 1, 6] 进行升序排序：

初始状态：[5, 2, 8, 12, 1, 6]
第一趟：  [2, 5, 8, 1, 6, 12]
第二趟：  [2, 5, 1, 6, 8, 12]
第三趟：  [2, 1, 5, 6, 8, 12]
第四趟：  [1, 2, 5, 6, 8, 12]
第五趟：  [1, 2, 5, 6, 8, 12]（无交换，排序完成）

在每一趟排序中，我们都会将当前未排序部分的最大元素"冒泡"到数列的末尾。经过 n-1 趟排序后（其中 n 是数组的长度），整个数列就变成了有序状态。

C语言实现冒泡排序

下面是冒泡排序的 C 语言实现代码：

#include <stdio.h>

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

// 打印数组
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;
}

运行结果：

排序前的数组:
64 34 25 12 22 11 90
排序后的数组:
11 12 22 25 34 64 90

这段代码中，bubbleSort 函数实现了冒泡排序的核心逻辑。外层循环 i 控制排序的趟数，内层循环 j 负责在每一趟中进行相邻元素的比较和交换。

冒泡排序的时间复杂度和空间复杂度

冒泡排序的时间复杂度在最坏情况下是 O(n^2)，其中 n 是数组的长度。这是因为我们需要进行 n-1 趟排序，每趟都要比较 n-1、n-2、...、1 个元素对。最好情况下，如果数组已经是有序的，我们只需要进行 n-1 次比较，不需要任何交换，时间复杂度为 O(n)。


空间复杂度方面，冒泡排序是一个原地排序算法，只需要常数级的额外空间，因此空间复杂度为 O(1)。

冒泡排序的优化

标准的冒泡排序可以通过一些优化来提高效率：

  1. 如果在某一趟排序中没有发生任何交换，说明数列已经有序，可以提前结束排序。
  2. 记录上一次交换发生的位置，下一轮排序只需要扫描到该位置即可。


下面是优化后的冒泡排序代码：

void optimizedBubbleSort(int arr[], int n) {
    int i, j, temp;
    int lastExchange = 0; // 记录最后一次交换的位置
    int sortBorder = n - 1; // 无序数列的边界，每次比较只需要比到这里
    for (i = 0; i < n-1; i++) {
        int isSorted = 1; // 假设数列已经有序
        for (j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                isSorted = 0; // 有元素交换，所以不是有序的
                lastExchange = j; // 更新最后交换的位置
            }
        }
        sortBorder = lastExchange;
        if (isSorted) break; // 如果没有发生交换，说明已经有序，提前退出
    }
}

这个优化版本的冒泡排序通过记录最后一次交换的位置，减少了不必要的比较，同时如果整个数列已经有序，可以提前结束排序过程，显著提高了算法的效率。

总结

冒泡排序是一种简单直观的排序算法，虽然在大规模数据排序中效率不高，但它对于理解排序算法的基本思想非常有帮助，尤其是初学者。通过不断比较相邻元素并交换它们的位置，最终将最大（或最小）的元素“冒泡”到数列的一端，从而实现整个数列的排序。
 

你可能还想关注其它九种排序算法：


声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。

相关文章

精选内容