排序算法详解、应用对比与C语言实现

四种经典排序算法详解(原理+动图+代码)

一、排序算法的重要性

排序算法是计算机科学领域最基础的算法之一,在数据库索引、搜索引擎优化、大数据分析等领域有广泛应用。根据Stack Overflow 2022开发者调查,超过83%的面试会考察算法实现能力,其中排序算法是必考题型。

排序算法应用场景
(图示:电商平台价格排序、学生成绩排名等实际应用场景)

二、基础排序算法详解

2.1 冒泡排序(Bubble Sort)

算法原理

通过相邻元素两两比较,将最大值"冒泡"到数组末尾。每轮遍历减少一个比较元素。

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;}}}
}
过程演示(以数组[5,3,8,6,4]为例)
初始状态:5 3 8 6 4
第1轮:
3 5 8 6 4 → 3 5 6 8 4 → 3 5 6 4 8
第2轮:
3 5 6 4 → 3 5 4 6 
第3轮: 
3 5 4 → 3 4 5
第4轮:
3 4 → 完成排序

2.2 插入排序(Insertion Sort)

算法特点
  • 时间复杂度:O(n²)(最坏)
  • 空间复杂度:O(1)
  • 稳定排序
  • 适合小规模数据或基本有序数据
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;}
}

过程演示(以数组[5, 2, 9, 1, 5]为例)

未排序部分: [5, 2, 9, 1, 5]
已排序部分: []
第一步:
将第一个元素(5)视为已排序部分。
未排序部分: [2, 9, 1, 5]
已排序部分: [5]
第二步:
取未排序部分的第一个元素(2),与已排序部分的元素比较。
2 小于 5,将 5 向后移动,插入 2。
未排序部分: [9, 1, 5]
已排序部分: [2, 5]
第三步:
取未排序部分的下一个元素(9),与已排序部分的元素比较。
9 大于 5,直接插入到已排序部分的末尾。
未排序部分: [1, 5]
已排序部分: [2, 5, 9]
第四步:
取未排序部分的下一个元素(1),与已排序部分的元素比较。
1 小于 9,将 9 向后移动。
1 小于 5,将 5 向后移动。
1 小于 2,将 2 向后移动,插入 1。
未排序部分: [5]
已排序部分: [1, 2, 5, 9]
第五步:
取未排序部分的最后一个元素(5),与已排序部分的元素比较。
5 小于 9,将 9 向后移动。
5 等于已排序部分的最后一个元素(也是5),直接插入到该位置(或者保持不变,因为相等)。
未排序部分: []
已排序部分: [1, 2, 5, 5, 9]最终排序结果:
[1, 2, 5, 5, 9]

三、高效排序算法解析

3.1 快速排序(Quick Sort)

核心思想

分治策略:选取基准值(pivot),将数组划分为两个子数组,递归排序。

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++;swap(&arr[i], &arr[j]);}}swap(&arr[i+1], &arr[high]);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);}
}

快速排序分区过程图示
在这里插入图片描述

3.2 归并排序(Merge Sort)

算法优势
  • 稳定排序
  • 时间复杂度稳定O(n log n)
  • 适合链表结构排序
  • 可用于外部排序
void merge(int arr[], int l, int m, int r) {// 合并两个有序子数组int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 处理剩余元素while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}

归并排序过程图示
在这里插入图片描述

四、排序算法综合对比

算法时间复杂度(平均)空间复杂度稳定性适用场景
冒泡排序O(n²)O(1)稳定教学演示
快速排序O(n log n)O(log n)不稳定通用排序
归并排序O(n log n)O(n)稳定大数据量、外部排序
堆排序O(n log n)O(1)不稳定内存受限场景

扩展:主流排序算法综合对比
在这里插入图片描述

五、工程实践建议

  1. 小数据量(n < 100):优先使用插入排序
  2. 通用场景:采用快速排序(如C语言qsort函数)
  3. 稳定性要求:选择归并排序(如Java的Arrays.sort)
  4. 内存敏感:使用堆排序
  5. 数据基本有序:考虑冒泡排序优化版
// 优化版冒泡排序(增加交换标志)
void optimizedBubbleSort(int arr[], int n) {int swapped;for (int i = 0; i < n-1; i++) {swapped = 0;for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(&arr[j], &arr[j+1]);swapped = 1;}}if (!swapped) break;}
}

六、总结与思考

不同的排序算法各有利弊,理解其核心原理和适用场景比死记代码更重要。实际工程中常采用混合排序策略(如TimSort结合了归并排序和插入排序),建议读者在掌握基础算法后,可进一步研究:

  1. 不同编程语言的内置排序实现
  2. 并行排序算法设计
  3. 海量数据的分治策略优化
  4. 特殊数据结构的排序优化

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/16893.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python基于Django的微博热搜、微博舆论可视化系统(V3.0)【附源码】

博主介绍&#xff1a;✌Java老徐、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&…

网络安全ids是什么意思

1、 简述IPS和IDS的异同点&#xff1b; 入侵检测系统&#xff08;IDS&#xff09; IDS&#xff08;Intrusion Detection Systems&#xff0c;入侵检测系统&#xff09;&#xff0c;专业上讲就是依照一定的安全策略&#xff0c;对网络、系统、运行状况进行监视&#xff0c;尽可能…

JVM春招快速学习指南

1.说在前面 在Java相关岗位的春/秋招面试过程中&#xff0c;JVM的学习是必不可少的。本文主要是通过《深入理解Java虚拟机》第三版来介绍JVM的学习路线和方法&#xff0c;并对没有过JVM基础的给出阅读和学习建议&#xff0c;尽可能更加快速高效的进行JVM的学习与秋招面试的备战…

json格式,curl命令,及轻量化处理工具

一. JSON格式 JSON&#xff08;JavaScript Object Notation&#xff09; 是一种轻量级的数据交换格式。它基于一个子集的JavaScript编程语言&#xff0c;使用人类易于阅读的文本格式来存储和表示数据。尽管名字中有“JavaScript”&#xff0c;但JSON是语言无关的&#xff0c;几…

echarts 3d中国地图飞行线

一、3D中国地图 1. 一定要使用 echarts 5.0及以上的版本; 2. echarts 5.0没有内置中国地图了。点击下载 china.json&#xff1b; 3. 一共使用了四层地图。 &#xff08;1&#xff09;第一层是中国地图各省细边框和展示南海诸岛&#xff1b; &#xff08;2&#xff09;第二层是…

从 0 开始本地部署 DeepSeek:详细步骤 + 避坑指南 + 构建可视化(安装在D盘)

个人主页&#xff1a;chian-ocean 前言&#xff1a; 随着人工智能技术的迅速发展&#xff0c;大语言模型在各个行业中得到了广泛应用。DeepSeek 作为一个新兴的 AI 公司&#xff0c;凭借其高效的 AI 模型和开源的优势&#xff0c;吸引了越来越多的开发者和企业关注。为了更好地…

[AI]Mac本地部署Deepseek R1模型 — — 保姆级教程

[AI]Mac本地部署DeepSeek R1模型 — — 保姆级教程 DeepSeek R1是中国AI初创公司深度求索&#xff08;DeepSeek&#xff09;推出大模型DeepSeek-R1。 作为一款开源模型&#xff0c;R1在数学、代码、自然语言推理等任务上的性能能够比肩OpenAI o1模型正式版&#xff0c;并采用MI…

Linux(socket网络编程)TCP连接

Linux&#xff08;socket网络编程&#xff09;TCP连接 基础文件目录函数系统进程控制函数fork()exec系列函数void abort(void)void assert(int expression)void exit(int status)void _exit(int status)int atexit(void (*func)(void))int on_exit(void (*function)(int,void*)…

408-数据结构

数据结构在学什么&#xff1f; 1.用代码把问题信息化 2.用计算机处理信息 ch1 数据&#xff1a;数据是信息的载体&#xff0c;是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。 ch2 //假设线性表…

Go语言开发桌面应用基础框架(wails v3)-开箱即用框架

前言 本文是介绍如何集成好了Wails3开发框架以及提供视频教程&#xff0c;当你需要桌面开发时&#xff0c;直接下载我们基础框架代码&#xff0c;开箱即用不用配置开发需要依赖。 为什么使用v3版本&#xff0c;主要是v3新增的功能 ​支持多个窗口&#xff1a;在单个应用程序…

Git 与 Git常用命令

Git 是一个开源的分布式版本控制系统&#xff0c;广泛用于源代码管理。与传统的集中式版本控制系统不同&#xff0c;Git 允许每个开发者在本地拥有完整的代码库副本&#xff0c;支持离线工作和高效的分支管理。每次提交时&#xff0c;Git 会对当前项目的所有文件创建一个快照&a…

尚硅谷爬虫note004

一、urllib库 1. python自带&#xff0c;无需安装 # _*_ coding : utf-8 _*_ # Time : 2025/2/11 09:39 # Author : 20250206-里奥 # File : demo14_urllib # Project : PythonProject10-14#导入urllib.request import urllib.request#使用urllib获取百度首页源码 #1.定义一…

老WinForm中一个执行文件使用SQLite数据库

EF6在老WinForm中停止更新了&#xff0c;但如果只是在win10上面使用&#xff0c;老的.net Framework 4.8框架有一个优势&#xff0c;编译后的执行文件很小。还有一些老类库也只能在老的.net Framework 4.8框架使用&#xff0c;所以微软还是保留了老的.net Framework 4.8框架。 …

diff算法简析

diff算法的核心目的是用最少的步骤找出新旧节点的差异&#xff0c;从而更新视图。 diff算法是一种通过同层的树节点进行比较的高效算法&#xff0c;探讨的是虚拟DOM树发生变化后&#xff0c;生成DOM树更新补丁的方式。对比新旧两株虚拟DOM树的差异&#xff0c;将更新补丁作用于…

19.3 连接数据库

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 ​​​​​​​需要北风数据库的请留言自己的信箱。 连接数据库使用OleDbConnection&#xff08;数据连接&#xff09;类&#xff…

Redis实现分布式锁

一、使用分布式锁的背景是什么 1、如果你公司的业务&#xff0c;各个应用都只部署了一台机器&#xff0c;那么完全用不着分布式锁&#xff0c;直接使用Java的锁即可 2、可是当你们的业务量大&#xff0c;多台机器并发情况下争夺一个资源的时候&#xff0c;就必须要保证业务的…

变化检测相关论文可读list

一些用得上的&#xff1a; 遥感变化检测常见数据集https://github.com/rsdler/Remote-Sensing-Change-Detection-Dataset/ 代码解读&#xff1a;代码解读 | 极简代码遥感语义分割&#xff0c;结合GDAL从零实现&#xff0c;以U-Net和建筑物提取为例 对本list的说明&#xff1a;…

docker 逃逸突破边界

免责声明 本博客文章仅供教育和研究目的使用。本文中提到的所有信息和技术均基于公开来源和合法获取的知识。本文不鼓励或支持任何非法活动&#xff0c;包括但不限于未经授权访问计算机系统、网络或数据。 作者对于读者使用本文中的信息所导致的任何直接或间接后果不承担任何…

cv2.Sobel

1. Sobel 算子简介 Sobel 算子是一种 边缘检测算子&#xff0c;通过对图像做梯度计算&#xff0c;可以突出边缘。 Sobel X 方向卷积核&#xff1a; 用于计算 水平方向&#xff08;x 方向&#xff09; 的梯度。 2. 输入图像示例 假设我们有一个 55 的灰度图像&#xff0c;像素…

网络编程 day3

思维导图 以select函数模型为例 思维导图2 对应 epoll模型 应使用的函数 题目 使用epoll函数实现 两个客户端 通过服务器 实现聊天 思路 在原先代码基础上 实现 服务器 发向 客户端 使用客户端在服务器上的 套接字描述符 实现 客户端 接收 服务器…