复杂度分析

Coddy 冒泡排序课程的第 5 课，共 11 课。

冒泡排序的复杂度分析。

时间复杂度取决于执行的比较和交换次数。

我们需要执行 n 趟，每一趟进行 (n-1) 次比较。其中，n 是列表中的元素个数。

总比较次数=(n-1)+(n-1)+(n-1)....n 次

=n*(n-1)

=n²-n

冒泡排序算法的时间复杂度是 O(n²)。

如果说到空间复杂度，该算法不使用额外空间，它执行的是原地排序，元素直接在原列表中排列。

冒泡排序算法的空间复杂度是 O(1)（常数）。

挑战

简单

创建一个名为 count_swaps 的函数，接收一个数组和数组的大小。对数组执行冒泡排序，并统计交换操作执行的次数。

亲手试试

#include <stdio.h>
#include <stdlib.h>

int count_swaps(int* arr, int arr_size, int n) {
    // 在这里编写代码
    return 0;
}

冒泡排序中的所有课

1冒泡排序基础

2分析

3练习挑战