文章目录
- 🍊自我介绍
- 🍊平均时间复杂度计算
- 一、冒泡排序
- 二、快速排序
- 三、选择排序
你的点赞评论就是对博主最大的鼓励
当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~
🍊自我介绍
Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入式方面的内容。
🍊平均时间复杂度计算
在C语言的算法领域,排序算法占据着重要地位。今天我们就来详细剖析冒泡排序、快速排序、选择排序的平均时间复杂度计算过程,并附上相应的代码示例,以便大家能更透彻地理解。
一、冒泡排序
- 算法原理
冒泡排序通过反复比较相邻的元素并在必要时交换它们,使得每一趟排序后最大(或最小)的元素像“冒泡”一样逐渐移到数组的一端。
- 平均时间复杂度计算流程
设数组有 n个元素。在最好情况下,数组已经有序,只需进行一趟比较,时间复杂度为O(n) 。但在平均和最坏情况下,需要进行 n-1 趟排序。
每趟排序要比较 n-i 次( i为当前趟数)。对于平均情况,假设数组元素初始排列是随机的,每趟排序中平均有一半的元素需要交换位置。大致也需要进行 n-1 趟排序,每趟比较次数接近 n-i 次。
计算平均时间复杂度:
n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2
所以平均时间复杂度为 O( n 2 {n}^{2} n2)。
- 代码实现
#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;
}
二、快速排序
- 算法原理
快速排序采用分治策略,先选取一个基准元素,将数组分为两部分,小于基准的和大于基准的,然后对这两部分分别递归进行排序。
- 平均时间复杂度计算流程
在平均情况下,每次划分都能将数组大致分成两个等长的子数组。设数组长度为 n。
第一次划分需要比较 n次,然后分成两个长度大致为n/2 的子数组。对这两个子数组又分别进行划分,如此递归下去。
根据递归树分析,树的高度大约为 l o g 2 {log}_{2} log2n,每层节点数大致为 n(因为每次划分都涉及对整个数组的部分进行操作)。
所以总的比较次数大约为n l o g 2 {log}_{2} log2n ,平均时间复杂度为 O(n l o g 2 {log}_{2} log2n)。
- 代码实现
#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;
}
三、选择排序
- 算法原理
选择排序每次从待排序的数组中选择最小(或最大)的元素,放到已排序序列的末尾。
- 平均时间复杂度计算流程
对于有 个元素的数组,无论初始排列如何,都需要进行 次选择操作。
每次选择操作都要遍历剩余的未排序元素,最多需要比较 次( 为已完成的选择次数)。
计算平均时间复杂度:
n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2
所以平均时间复杂度为 O( n 2 {n}^{2} n2)。
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