C语言:排序

ops/2024/12/23 13:55:06/

1. 插入排序 (Insertion Sort)

插入排序是一种简单直观的排序算法,它的工作原理类似于整理扑克牌。它的基本思想是将数组分为已排序部分和未排序部分,每次从未排序部分取出一个元素,插入到已排序部分的合适位置。

步骤
  1. 从数组的第二个元素开始(假设第一个元素是已排序部分)。
  2. 将当前元素与已排序部分的元素从后向前比较,找到合适的位置插入。
  3. 重复上述过程,直到所有元素都被插入到合适的位置。
示例代码(C语言):
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;}
}
性能分析
  • 时间复杂度
    • 最好情况:O(n)(数组已经有序)。
    • 最坏情况:O(n^2)(数组逆序)。
    • 平均情况:O(n^2)
  • 空间复杂度O(1)(原地排序)。
  • 稳定性:稳定(不改变相同元素的相对顺序)。
适用场景
  • 适用于小规模数据或部分有序的数据。

2. 选择排序 (Selection Sort)

选择排序是一种简单直观的排序算法,它的工作原理是每次从未排序部分选择最小(或最大)的元素,放到已排序部分的末尾。

步骤
  1. 将数组分为已排序部分和未排序部分。
  2. 从未排序部分中找到最小元素,与未排序部分的第一个元素交换位置。
  3. 重复上述过程,直到所有元素都被排序。
示例代码(C语言):
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[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}
性能分析
  • 时间复杂度
    • 最好、最坏、平均情况:O(n^2)
  • 空间复杂度O(1)(原地排序)。
  • 稳定性:不稳定(交换操作可能改变相同元素的相对顺序)。
适用场景
  • 适用于小规模数据,尤其是内存受限的场景。

3. 快速排序 (Quick Sort)

快速排序是一种高效的排序算法,基于“分治法”的思想。它通过选择一个“基准元素”(pivot)将数组分为两部分:小于基准的部分和大于基准的部分,然后递归地对两部分进行排序。

步骤
  1. 选择一个基准元素(通常是数组的第一个或最后一个元素)。
  2. 将数组分为两部分:一部分小于基准,另一部分大于基准。
  3. 递归地对两部分进行快速排序。
示例代码(C语言):
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 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;
}
性能分析
  • 时间复杂度
    • 最好情况:O(n log n)(每次分区均匀)。
    • 最坏情况:O(n^2)(每次分区极不均匀,例如数组已经有序)。
    • 平均情况:O(n log n)
  • 空间复杂度O(log n)(递归栈的深度)。
  • 稳定性:不稳定(分区操作可能改变相同元素的相对顺序)。
适用场景
  • 适用于大规模数据的排序,尤其是随机数据的排序。

4. 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法,它的工作原理是通过重复地遍历数组,依次比较相邻元素并交换顺序错误的元素。每一轮遍历都会将未排序部分的最大元素“冒泡”到末尾。

步骤
  1. 从数组的第一个元素开始,依次比较相邻元素。
  2. 如果前一个元素大于后一个元素,交换它们。
  3. 重复上述过程,直到没有需要交换的元素。
示例代码(C语言):
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {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;}}}
}
性能分析
  • 时间复杂度
    • 最好情况:O(n)(数组已经有序)。
    • 最坏情况:O(n^2)
    • 平均情况:O(n^2)
  • 空间复杂度O(1)(原地排序)。
  • 稳定性:稳定(不改变相同元素的相对顺序)。
适用场景
  • 适用于小规模数据,尤其是教学和理解排序算法的场景。

对比总结

算法时间复杂度空间复杂度稳定性特点
插入排序O(n^2)O(1)稳定适合小规模数据或部分有序数据
选择排序O(n^2)O(1)不稳定简单直观,适用于小规模数据
快速排序O(n log n)O(log n)不稳定高效,适用于大规模数据
冒泡排序O(n^2)O(1)稳定简单易于理解

http://www.ppmy.cn/ops/144314.html

相关文章

基于知识图谱的医疗问答系统(dockerfile+docker-compose)

文章目录 一、搭建 Neo4j 图数据库1、方式选择2、Dockerfiledocker-compose部署neo4j容器2.1、更新 yum 镜像源2.2、安装 docker-ce 社区版2.3、配置镜像加速2.4、安装 Docker Compose2.4.1、下载 Docker Compose 二进制包2.4.2、设置可执行权限2.4.3、查看版本 2.5、创建目录结…

国产 HighGo 数据库企业版安装与配置指南

国产 HighGo 数据库企业版安装与配置指南 1. 下载安装包 访问 HighGo 官方网站&#xff08;https://www.highgo.com/&#xff09;&#xff0c;选择并下载企业版安装包。 2. 上传安装包到服务器 将下载的安装包上传至服务器&#xff0c;并执行以下命令&#xff1a; [rootmas…

最大似然检测在通信解调中的应用

最大似然检测&#xff08;Maximum Likelihood Detection&#xff0c;MLD&#xff09;&#xff0c;也称为最大似然序列估计&#xff08;Maximum Likelihood Sequence Estimation&#xff0c;MLSE&#xff09;&#xff0c;是一种在通信系统中广泛应用的解调方法。其核心思想是在给…

使用NodeJs 实现图片转PPT

序言 帮朋友下载网络资源。最后转化为PPT 网页是这样的 下载图片 需要使用nodejs来下载图片 安装需要的库 npm install axios执行下面的JS const fs require(fs); const path require(path); const axios require(axios); const { URL } require(url); const readlin…

从零开始学前端之HTML(三)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 HTML CSS 内联样式内部样式表外部样式表 HTML图像HTML 表格HTML列表HTML区块HTML表单HTML框架 HTML CSS 内联样式- 在HTML元素中使用"style" 属性 内部…

驾驶证识别API-JavaScript驾驶证ocr接口集成-场景解析

随着数字化转型的加速和人工智能技术的进步&#xff0c;驾驶证识别技术正逐渐成为众多行业优化服务流程、提升用户体验的关键工具&#xff0c;它不仅仅是一个简单的信息提取过程&#xff0c;更体现了现代信息技术与传统交通管理融合的新趋势。 通过集成驾驶证识别技术&#xff…

【java面向对象编程】第七弹----Object类、类变量与类方法

笔上得来终觉浅,绝知此事要躬行 &#x1f525; 个人主页&#xff1a;星云爱编程 &#x1f525; 所属专栏&#xff1a;javase &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 一、Object类 1.1equa…