---

你的点赞评论就是对博主最大的鼓励
当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~

---

🍊自我介绍

  Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入式方面的内容。

---

🍊平均时间复杂度计算

在C语言的算法领域，排序算法占据着重要地位。今天我们就来详细剖析冒泡排序、快速排序、选择排序的平均时间复杂度计算过程，并附上相应的代码示例，以便大家能更透彻地理解。

一、冒泡排序

1. 算法原理

冒泡排序通过反复比较相邻的元素并在必要时交换它们，使得每一趟排序后最大（或最小）的元素像“冒泡”一样逐渐移到数组的一端。

2. 平均时间复杂度计算流程

设数组有 n个元素。在最好情况下，数组已经有序，只需进行一趟比较，时间复杂度为O(n) 。但在平均和最坏情况下，需要进行 n-1 趟排序。
每趟排序要比较 n-i 次（ i为当前趟数）。对于平均情况，假设数组元素初始排列是随机的，每趟排序中平均有一半的元素需要交换位置。大致也需要进行 n-1 趟排序，每趟比较次数接近 n-i 次。
计算平均时间复杂度：

$$n(n-1)/2$$

所以平均时间复杂度为 O($n^2$)。

3. 代码实现

#include <stdio.h>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]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {5, 4, 3, 2, 1};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

二、快速排序

1. 算法原理

快速排序采用分治策略，先选取一个基准元素，将数组分为两部分，小于基准的和大于基准的，然后对这两部分分别递归进行排序。

2. 平均时间复杂度计算流程

在平均情况下，每次划分都能将数组大致分成两个等长的子数组。设数组长度为 n。
第一次划分需要比较 n次，然后分成两个长度大致为n/2 的子数组。对这两个子数组又分别进行划分，如此递归下去。
根据递归树分析，树的高度大约为 ${log}_2$n，每层节点数大致为 n（因为每次划分都涉及对整个数组的部分进行操作）。
所以总的比较次数大约为n${log}_2$n ，平均时间复杂度为 O(n${log}_2$n)。

3. 代码实现

#include <stdio.h>int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (arr[j] <= pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return (i + 1);
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}int main() {int arr[] = {5, 4, 3, 2, 1};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

三、选择排序

1. 算法原理

选择排序每次从待排序的数组中选择最小（或最大）的元素，放到已排序序列的末尾。

2. 平均时间复杂度计算流程

对于有 个元素的数组，无论初始排列如何，都需要进行 次选择操作。
每次选择操作都要遍历剩余的未排序元素，最多需要比较 次（ 为已完成的选择次数）。
计算平均时间复杂度：

$$n(n-1)/2$$

所以平均时间复杂度为 O($n^2$)。
3. 代码实现

#include <stdio.h>void selectionSort(int arr[], int n) {int i, j, min_idx;for (i = 0; i < n - 1; i++) {min_idx = i;for (j = i + 1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}if (min_idx!= i) {int temp = arr[i];arr[i] = arr[min_idx];arr[min_idx] = temp;}}
}int main() {int arr[] = {5, 4, 3, 2, 1};int n = sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0