当前位置： 首页 > news >正文

9.c语言常用算法

news 2025/7/29 10:29:56

查找

顺序查找（线性查找）

算法思想：

从数组的第一个元素开始，逐个与目标值进行比较，直到找到目标值或查找完整个数组。

时间复杂度：

  • 最好情况：O(1)（目标在第一个位置）
  • 最坏情况：O(n)
  • 平均情况：O(n)

适用场景：

适用于无序数组或链表。

#include <stdio.h>int linearSearch(int arr[], int n, int target) {for (int i = 0; i < n; i++) {if (arr[i] == target)return i;  // 找到，返回索引}return -1;  // 未找到
}int main() {int arr[] = {5, 3, 8, 4, 2};int n = sizeof(arr) / sizeof(arr[0]);int target = 4;int index = linearSearch(arr, n, target);if (index != -1)printf("元素在索引 %d\n", index);elseprintf("未找到元素\n");return 0;
}

二分查找（折半查找）

算法思想：

在有序数组中查找目标值。每次将查找区间缩小一半，通过比较中间值与目标值的大小来决定下一步查找区间。

时间复杂度：

  • O(log n)

适用场景：

适用于有序数组。

C 语言实现（递归和非递归）：

#include <stdio.h>// 非递归实现
int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target)return mid;else if (arr[mid] < target)left = mid + 1;elseright = mid - 1;}return -1;
}// 递归实现
int binarySearchRecursive(int arr[], int left, int right, int target) {if (left > right) return -1;int mid = left + (right - left) / 2;if (arr[mid] == target)return mid;else if (arr[mid] < target)return binarySearchRecursive(arr, mid + 1, right, target);elsereturn binarySearchRecursive(arr, left, mid - 1, target);
}int main() {int arr[] = {2, 3, 4, 5, 8};int n = sizeof(arr) / sizeof(arr[0]);int target = 5;int index = binarySearch(arr, 0, n - 1, target);if (index != -1)printf("元素在索引 %d\n", index);elseprintf("未找到元素\n");return 0;
}

插值查找

算法思想：

是对二分查找的改进，根据目标值与数组两端值的差距来估算中间点的位置，适用于数据分布均匀的有序数组。

时间复杂度：

  • 平均情况：O(log log n)
  • 最坏情况：O(n)

C 语言实现：

int interpolationSearch(int arr[], int left, int right, int target) {while (left <= right && arr[left] != arr[right]) {int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);if (arr[pos] == target)return pos;else if (arr[pos] < target)left = pos + 1;elseright = pos - 1;}if (left <= right && arr[left] == target)return left;return -1;
}

排序

冒泡排序（Bubble Sort）

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

  • 时间复杂度：

    • 最好情况：O(n) （当输入数组已经是排序好的）
    • 平均和最坏情况：O(n^2)

  • 稳定性： 稳定

  • 适用场景： 数据量较小或基本有序的数据集

  •  语言代码：

    #include <stdio.h>void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int swapped = 0;for (int 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;swapped = 1;}}if (!swapped) break;  // 如果本轮没有交换，说明已经有序}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

选择排序（Selection Sort）

原理： 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完为止。

  • 时间复杂度：

    • 最好、平均和最坏情况：O(n^2)

  • 稳定性： 不稳定

  • 适用场景： 小规模数据集

语言代码：

#include <stdio.h>void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex])minIndex = j;}// 交换最小值和当前第一个未排序元素int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}
}int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

插入排序（Insertion Sort）

原理： 插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因此空间复杂度为O(1)。

  • 时间复杂度：

    • 最好情况：O(n) （输入数组已经是排序好的）
    • 平均和最坏情况：O(n^2)

  • 稳定性： 稳定

  • 适用场景： 小规模或者基本有序的数据

    语言代码：

    #include <stdio.h>void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

快速排序（Quick Sort）

原理： 快速排序使用分治法策略来把一个序列分成较小和较大的两个子序列，然后递归地排序两个子序列。具体来说，选择一个基准元素，通常选择第一个元素或者最后一个元素，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

  • 时间复杂度：

    • 最好和平均情况：O(n log n)
    • 最坏情况：O(n^2) （例如，当每次选取的基准都是当前序列中的最小或最大值时）

  • 稳定性： 不稳定

    语言代码：

    #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; 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[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

http://www.lryc.cn/news/602665.html

相关文章：

  • Anaconda创建环境报错：CondaHTTPEFTOT: HTTP 403 FORBIDDEN for url
  • Linux中配置haproxy
  • gitlab 在线合并分支a-分支b，解决冲突后，反向合并分支b-分支a
  • 数据结构——图（二、图的存储和基本操作）
  • 人机交互打字游戏
  • Leetcode——11. 盛最多水的容器
  • 力扣-39.组合总和
  • PhpStorm + PHP8.1 + XDebug3 实现断点调试（亲测可用）
  • 面试问题收集——卷积神经网络
  • 从 “看天吃饭” 到 “精准可控”：边缘计算网关如何引爆智慧农业种植变革？
  • 计算机毕设分享-基于SpringBoot的健身房管理系统（开题报告+前后端源码+Lun文+开发文档+数据库设计文档）
  • 服务器多线主要是指什么？
  • 服务器查日志太慢，试试grep组合拳
  • 数据中心入门学习（四）：服务器概述与PCIe总线
  • 数据结构面经
  • 坚鹏：AI智能体培训是知行学成为AI智能体创新应用引领者的基础
  • 【Spring Boot 快速开发】一、入门
  • AI技术落地的综合实战经验报告，结合最新行业案例、代码示例及可视化图表，系统阐述AI在开发提效、算法优化与行业应用中的实践路径。
  • Python将Word转换为Excel
  • EXCEL 怎么把汉字转换成拼音首字母
  • 根据发热量确定选择TEC制冷片测评分析学习
  • Open CV图像基本操作可莉版
  • IP协议解析：从寻址到路由
  • Vue3判断对象是否为空方法
  • 判断回文链表【两种O(n)时间复杂度】
  • 10_opencv_分离颜色通道、多通道图像混合
  • Netty中trySuccess和setSuccess的区别
  • Java程序员学从0学AI（七）
  • mybatis-plus-tenant-support
  • Caddy服务器指南