【数据结构】冒泡排序,快速排序的学习知识总结
目录
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文件,里面配置相应的放行路径...

TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...

如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
2.2.2 ASPICE的需求分析
ASPICE的需求分析是汽车软件开发过程中至关重要的一环,它涉及到对需求进行详细分析、验证和确认,以确保软件产品能够满足客户和用户的需求。在ASPICE中,需求分析的关键步骤包括: 需求细化:将从需求收集阶段获得的高层需…...