面试题：C语言中冒泡排序的算法复杂度分析

Question

请用C语言实现冒泡排序算法，并分析其时间复杂度和空间复杂度。同时说明在何种情况下，该算法的时间复杂度会达到最优和最坏。

Answer 1

冒泡排序算法实现

#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++) {
        // 最后 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");
}

时间复杂度分析

1. 最坏情况：数组完全逆序。此时每次比较都需要交换，总共需要进行 n(n - 1)/2 次比较和交换操作，时间复杂度为 $O(n^2)$，其中 n 是数组的长度。
2. 最优情况：数组已经有序。在这种情况下，只需进行 n - 1 次比较，不需要交换，时间复杂度为 $O(n)$。但这需要对冒泡排序算法进行优化，添加一个标志位来判断在某次遍历中是否有元素交换，如果没有交换则说明数组已经有序，可以提前结束排序。

空间复杂度分析

冒泡排序是原地排序算法，除了输入数组本身外，只需要常数级别的额外空间，所以空间复杂度为 $O(1)$。

完整测试代码

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    bubbleSort(arr, n);

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

    return 0;
}

上述代码实现了冒泡排序算法，并对其时间复杂度和空间复杂度进行了分析，同时说明了最优和最坏情况。