【数据结构】冒泡排序,快速排序的学习知识总结
目录
1、冒泡排序
1.1 算法思想
1.2 代码实现
方式一:顺序表
方式二:链表
2、快速排序
2.1 算法思想
2.2 代码实现
2.3 例题分析
1、冒泡排序
1.1 算法思想
冒泡排序是一种简单的排序算法,它的基本思想是从数组的第一个元素开始依次比较相邻的两个元素,根据大小交换它们的位置,直到所有元素都排好序为止。
具体步骤如下:
1. 从数组的第一个元素开始,依次比较相邻的两个元素。
2. 如果前面的元素大于后面的元素,则交换它们的位置。
3. 接着比较下一对相邻元素,重复上述步骤,直到遍历到数组的最后一个元素。
4. 一次遍历过后,最后一个元素一定是当前数组中的最大元素,因此下一次遍历可以排除它。
5. 重复上述步骤,直到所有元素都排好序为止。
冒泡排序的时间复杂度为O(n^2),不适合处理大规模的数据。但是它实现简单,适用于对小规模数据排序,并且由于其稳定性和可读性,仍然被广泛应用。
1.2 代码实现
方式一:顺序表
以下是C语言实现冒泡排序的代码:
#include <stdio.h>void bubbleSort(int arr[], int n);
void printArray(int arr[], int n);int main()
{int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组:\n");printArray(arr, n);bubbleSort(arr, n);printf("排序后的数组:\n");printArray(arr, n);return 0;
}void bubbleSort(int arr[], int n)
{int i, j, temp;for (i = 0; i < n - 1; i++) // 外层循环控制轮数{for (j = 0; j < n - i - 1; j++) // 内层循环控制比较和交换{if (arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}void printArray(int arr[], int n)
{int i;for (i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}
输出结果:
原始数组:
64 34 25 12 22 11 90
排序后的数组:
11 12 22 25 34 64 90
方式二:链表
以下是基于链表的冒泡排序的C语言实现代码:
#include <stdio.h>
#include <stdlib.h>struct node {int data;struct node* next;
};void swap(struct node* a, struct node* b) {int temp = a->data;a->data = b->data;b->data = temp;
}void bubbleSort(struct node* head) {int swapped, i;struct node* ptr1;struct node* lptr = NULL;if (head == NULL) {return;}do {swapped = 0;ptr1 = head;while (ptr1->next != lptr) {if (ptr1->data > ptr1->next->data) {swap(ptr1, ptr1->next);swapped = 1;}ptr1 = ptr1->next;}lptr = ptr1;} while (swapped);
}void printList(struct node* head) {struct node* temp = head;while (temp != NULL) {printf("%d ", temp->data);temp = temp->next;}
}void push(struct node** head_ref, int new_data) {struct node* new_node = (struct node*)malloc(sizeof(struct node));new_node->data = new_data;new_node->next = (*head_ref);(*head_ref) = new_node;
}int main() {struct node* head = NULL;push(&head, 5);push(&head, 20);push(&head, 4);push(&head, 3);push(&head, 30);printf("Original Linked List:\n");printList(head);bubbleSort(head);printf("\nSorted Linked List:\n");printList(head);return 0;
}
该程序首先定义了一个结构体node
,其中包含一个整型数据data
和一个指向下一个结构体node
的指针next
。接着定义了三个函数:
swap
函数用于交换两个结构体的数据成员data
。bubbleSort
函数实现了基于链表的冒泡排序。printList
函数用于遍历链表并打印所有节点的数据成员data
。
最后,main
函数中创建了一个空的链表,并用push
函数向其中添加了五个节点。然后,原始链表被打印出来,接着使用bubbleSort
函数对链表进行排序。最后,排好序的链表也被打印出来。
2、快速排序
2.1 算法思想
快速排序(Quick Sort)是一种常用的排序算法,其基本思想是选取一个基准元素,将所有小于基准元素的数放到其左边,所有大于基准元素的数放到其右边,然后再对两边分别进行递归排序。快速排序是一种比较快的排序算法,平均时间复杂度为O(nlogn)。
具体算法步骤如下:
-
选取一个基准元素(通常是第一个元素或者随机选取),将数组分成左右两个部分;
-
将小于等于基准元素的数放到左边,大于基准元素的数放到右边,分别形成两个子数组;
-
对左右两个子数组进行递归排序,直到每个子数组只有一个元素或为空为止;
-
合并两个子数组,完成排序。
快速排序的关键在于如何进行划分,一般采用双指针法,即左指针从左往右扫描数组,右指针从右往左扫描数组,当左指针找到一个大于基准元素的数,右指针找到一个小于基准元素的数时,交换两个数的位置,直到左指针和右指针相遇。最后将基准元素与左右子数组的中间位置交换,完成一次排序。
2.2 代码实现
时间复杂度为O(nlogn)
下面是C语言实现快速排序的代码:
void quick_sort(int arr[], int left, int right) {if (left >= right)return;int i = left, j = right, pivot = arr[left];while (i < j) {while (i < j && arr[j] >= pivot)j--;arr[i] = arr[j];while (i < j && arr[i] <= pivot)i++;arr[j] = arr[i];}arr[i] = pivot;quick_sort(arr, left, i - 1);quick_sort(arr, i + 1, right);
}
上述代码中,arr
表示待排序数组,left
表示待排序区间左边界,right
表示待排序区间右边界。首先判断左右边界是否相等或左边界大于右边界,如果是,则直接返回。然后取arr[left]
作为枢轴元素,从右向左找到第一个小于枢轴元素的元素,从左向右找到第一个大于枢轴元素的元素,并交换两个元素。重复上述操作直到i=j,将枢轴元素放到i位置上,此时数组被分成了两个部分,左边部分小于枢轴元素,右边部分大于枢轴元素。然后递归调用快速排序函数对左右两个部分进行排序。
2.3 例题分析
以下是一个快速排序的例题:
假设我们要对以下数组进行快速排序:[7, 2, 8, 1, 4, 3, 6, 5]
-
首先选择一个基准值,可以选择数组中的任意一个数,这里我们选择第一个数7作为基准值。
-
接着从数组的左边开始,找到第一个大于等于基准值的数,这里是8;然后从数组的右边开始,找到第一个小于等于基准值的数,这里是5,将它们交换位置。
现在数组变成了:[5, 2, 8, 1, 4, 3, 6, 7]
- 继续从左到右找到一个大于等于基准值的数,这里是8,然后从右到左找到一个小于等于基准值的数,这里是3,将它们交换位置。
现在数组变成了:[5, 2, 3, 1, 4, 8, 6, 7]
- 继续从左到右找到一个大于等于基准值的数,这里是4,然后从右到左找到一个小于等于基准值的数,这里是1,将它们交换位置。
现在数组变成了:[5, 2, 3, 1, 4, 8, 6, 7]
- 继续从左到右找到一个大于等于基准值的数,这里是6,然后从右到左找到一个小于等于基准值的数,这里是1,将它们交换位置。
现在数组变成了:[5, 2, 3, 1, 4, 1, 6, 7, 8]
- 重复上述步骤,直到将整个数组排好序。
最后的排序结果是:[1, 2, 3, 4, 5, 6, 7, 8]
相关文章:

【数据结构】冒泡排序,快速排序的学习知识总结
目录 1、冒泡排序 1.1 算法思想 1.2 代码实现 方式一:顺序表 方式二:链表 2、快速排序 2.1 算法思想 2.2 代码实现 2.3 例题分析 1、冒泡排序 1.1 算法思想 冒泡排序是一种简单的排序算法,它的基本思想是从数组的第一个元素开始…...
ubuntu终端 中文显示 改为 英文显示
临时有效 如果希望终端显示英文,可以在终端设置环境变量 export LC_ALLC 若希望取消环境变量 unset LC_ALL 实际是改变系统两个环境变量 $LANGUAGE 和 $LANG的值(可以用echo $LANG 来查看值) 永久有效; 1.打开终端…...

ChatGPT Prompting开发实战(十二)
一、如何开发prompts实现个性化的对话方式 通过设置“system”和“user”等roles,可以实现个性化的对话方式,并且可以结合参数“temperature”的设定来差异化LLM的输出内容。在此基础上,通过构建一个餐馆订餐对话机器人来具体演示对话过程。…...

springboot整合eureka
1、直入主题,导入pom文件 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http:/…...

记录一个 GUI 库的对比测试结果
1,Java 的 JavaFX 2,golang 的 Fyne 1, Java 测试的是一个俄罗斯方块的 GUI 程序。一切正常。 2,Golang github 的原仓库网络问题,没能测试上,使用以下库 https://gitee.com/mirrors/Fyne 下载代码后提示“编译失…...

解决 MyBatis-Plus 中增加修改时,对应时间的更新问题
问题:在添加修改时,对应的 create_time 与 insert_time 不会随着添加修改而自动的更新时间 第一步:首先在对应的属性上,加上以下注解 如果只添加以下注解,在增加或者修改时,可能对应的 LocalDateTime 会出…...

【力扣2057】值相等的最小索引
👑专栏内容:力扣刷题⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录 一、题目描述二、题目分析 一、题目描述 题目链接:值相等的最小索引 给你一个下标从 0 开始的整数数组 nums …...

计算机图像处理:图像轮廓
图像轮廓 图像阈值分割主要是针对图片的背景和前景进行分离,而图像轮廓也是图像中非常重要的一个特征信息,通过对图像轮廓的操作,就能获取目标图像的大小、位置、方向等信息。画出图像轮廓的基本思路是:先用阈值分割划分为两类图…...

解决java.io.FileNotFoundException: HADOOP_HOME and hadoop.home.dir are unset.的错误
文章目录 1. 复现错误2. 分析错误3. 解决问题3.1 下载Hadoop3.2 配置Hadoop3.3 下载winutils3.4 配置winutils 1. 复现错误 今天在运行同事给我的项目,但在项目启动时,报出如下错误: java.io.FileNotFoundException: java.io.FileNotFoundEx…...
软件设计中常见的设计模式
以下是常见的设计模式,并且给出了应用场景: 工厂模式(Factory Pattern):用于创建对象,隐藏了具体对象的创建细节,客户端只需要通过工厂接口获取对象即可。应用场景包括:当需要根据不…...

为什么我的remix没有injected web3
原因 Remix近期做了升级,去除了Web3的选项,您在进行部署的时候,可以选择injected provider metamask,同样能连接到Web3钱包哦。具体如下图所示:...

第1章 数据结构绪论
1.1 开场白 1.2 你数据结构怎么学的 1.3 数据结构起源 早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出一个解此数据模型的算…...

现代 GPU 容易受到新 GPU.zip 侧通道攻击
来自四所美国大学的研究人员开发了一种新的 GPU 侧通道攻击,该攻击利用数据压缩在访问网页时泄露现代显卡中的敏感视觉数据。 研究人员通过 Chrome 浏览器执行跨源 SVG 过滤器像素窃取攻击,证明了这种“ GPU.zip ”攻击的有效性。 研究人员于 2023 年 …...

8+单基因+细胞凋亡+WGCNA+单细胞+实验验证
今天给同学们分享一篇单基因细胞凋亡WGCNA实验验证的生信文章“RASGRP2 is a potential immune-related biomarker and regulates mitochondrial-dependent apoptosis in lung adenocarcinoma”,这篇文章于2023年2月3日发表在Front Immunol期刊上,影响因…...

BM4 合并两个排序的链表
思路:先选择最小的作为Head,每次从两个队列中取最小的挂到Head后面,如果一个合并空,后面直接挂。此外判断几个为空链表的情况 /*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullp…...

【lesson12】理解进程地址空间
文章目录 什么是进程地址空间?进程地址空间的作用扩展内容初步理解深入理解 什么是进程地址空间? 故事: 背景:有一个大富豪,家里的存款有10亿美元,他有三个私生子三个人之间彼此互不相识,只有富…...

计算机里的神灵(SCIP)
计算机程序的构造和解释 我找到计算机里的神灵了,开心一刻 下面是从MIT官网下载的 SCIP求值器(解释器)的代码,这个官网是个宝藏库 还有其他视频课程和 SCIP的问题答案和可运行代码 链接:https://ocw.mit.edu/courses/6…...

基于微信小程序的公交信息在线查询系统小程序设计与实现(源码+lw+部署文档+讲解等)
文章目录 前言系统主要功能:具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序(小蔡coding)有保障的售后福利 代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…...

【STM32】IAP升级01 bootloader实现以及APP配置(主要)
APP程序以及中断向量表的偏移设置 前言 通过之前的了解 之前的了解,我们知道实现IAP升级需要两个条件: 1.APP程序必须在 IAP 程序之后的某个偏移量为 x 的地址开始; 2.APP程序的中断向量表相应的移动,移动的偏移量为 xÿ…...

ruoyi(若依)接口拦截路径配置,接口访问要授权,放开授权直接访问
1.找到文件SecurityConfig.java文件,里面配置相应的放行路径...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...