数据结构-交换排序(冒泡、快速)

冒泡排序

基本思想

先将第一个记录与第二个记录比较,将较大的记录放到第二个位置上,之后再将第二个记录与第三

个记录比较,将较大的记录放到第三个位置上,如此类推,知道比较完最后一个位置,此时注意到

最后一个位置是整个记录表中最大的记录了。随后我们进行第二趟比较,但是此时只需要比较到倒

数第二个位置即可,此时次大的记录被放在了倒数第二个位置,直到比较完成。

注意到,较大的记录被放在了后面,娇小的记录被放在了前面,这跟水中冒泡一样,较重的物体下

沉,而水泡上浮。

故被称作:“冒泡法”。

示例

代码

OrderList BubbleSort(OrderList L)
{RecordType tmp;int i,j;for(i=1;i<=L.length-1;i++){for(j=1;j<=L.length-i;j++){if(L.data[j].key > L.data[j+1].key){tmp = L.data[j];L.data[j] = L.data[j+1];L.data[j+1] = tmp;}}}return L;
}

快速排序

基本思想

从待排序的N个记录中,取第一个记录作为枢纽记录,所有比枢纽记录小的记录放在左侧,比枢纽

记录大的记录放在右侧。然后对两边的两个字表重新进行快速排序(选择枢纽记录)。

直到每个子表的长度不大于1为止。

示例

代码

int Partition(OrderList *L,int i,int j)		//对当前i->j范围内的记录做一次快速排序 
{KeyType pivotkey;L->data[0] = L->data[i];pivotkey = L->data[i].key;while(i<j){while(i<j&&L->data[j].key>=pivotkey)j--;L->data[i] = L->data[j];while(i<j&&L->data[i].key<=pivotkey)i++;L->data[j] = L->data[i];}L->data[i] = L->data[0];return i;
}void QuickSort(OrderList *L,int i,int j)	//递归快速排序 
{int pivotkey;if(i<j){pivotkey = Partition(L,i,j);QuickSort(L,i,pivotkey-1);QuickSort(L,pivotkey+1,j);}
}

总代码

#include<stdio.h>
#define MAX 100
typedef int KeyType;
typedef struct{KeyType key;
}RecordType;
typedef struct{RecordType data[MAX];int length;
}OrderList;OrderList BubbleSort(OrderList L)
{RecordType tmp;int i,j;for(i=1;i<=L.length-1;i++){for(j=1;j<=L.length-i;j++){if(L.data[j].key > L.data[j+1].key){tmp = L.data[j];L.data[j] = L.data[j+1];L.data[j+1] = tmp;}}}return L;
}int Partition(OrderList *L,int i,int j)		//对当前i->j范围内的记录做一次快速排序 
{KeyType pivotkey;L->data[0] = L->data[i];pivotkey = L->data[i].key;while(i<j){while(i<j&&L->data[j].key>=pivotkey)j--;L->data[i] = L->data[j];while(i<j&&L->data[i].key<=pivotkey)i++;L->data[j] = L->data[i];}L->data[i] = L->data[0];return i;
}void QuickSort(OrderList *L,int i,int j)	//递归快速排序 
{int pivotkey;if(i<j){pivotkey = Partition(L,i,j);QuickSort(L,i,pivotkey-1);QuickSort(L,pivotkey+1,j);}
}int main()
{int simple[11] = {-1,5,9,1,100,56,78,22,40,60,99};int i;OrderList L;L.length = 10;for(i=1;i<11;i++)L.data[i].key = simple[i];//L = BubbleSort(L);	冒泡排序 //QuickSort(&L,1,10);	快速排序 for(i=1;i<11;i++)printf("%d ",L.data[i].key);return 0;
} 

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

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

相关文章

『 Linux 』进程优先级

文章目录 什么是优先级Linux下的进程优先级PRI与NI使用top查看进程以及对进程的优先级的修改 进程优先级的其他概念竞争性与独立性并发与并行 什么是优先级 优先级,顾名思义,即在同一环境下不同单位对同一个资源的享有顺序; 一般优先级高的单位将优先占有该资源; 在进程当中进…

万宾科技第四代可燃气体监测仪的作用

燃气作为一种重要的能源已在居民生活、工业生产和商业活动等领域得到了广泛的应用。但是与之而来的便是各种各样的燃气管网的安全问题&#xff0c;其中燃气管网泄漏成为了城市生命线建设中亟待解决的安全隐患。因此采取切实有效的措施来保障燃气管网的安全运行&#xff0c;应用…

Matlab 点云曲率计算(之二)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 之前已经讨论过许多关于计算曲率的问题,这里使用一个通过拟合三次曲面方程的方式来计算曲率,计算过程如下图所示: 二、实现代码 %********

centos7.9 + gitlab12.3.0安装

本文在centos7.9操作系统上安装gitlab 12.3.0&#xff0c;gitlab官方最新的版本已经是16.6.0了&#xff0c;这里仍然安装12.3.0版本的原因是汉化包的最新版本是12.3.0&#xff0c;如果汉化包的版本和gitlab的版本不对应&#xff0c;会出现汉化他无法启动的现象。 1、安装依赖 …

4/150:寻找两个正序数组的中位数⭐

题目&#xff1a;寻找两个正序数组的中位数 给定两个大小分别为 m 和 n 的正序&#xff08;从小到大&#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (mn)) 。 题解1&#xff1a;暴力 暴力思路简介&#xff0c;…

服务器bash进程占用cpu过多疑似中挖矿病毒记录

发现过程 因为我有使用conky的习惯&#xff0c;也就是在桌面上会显示cpu和内存的占用情况&#xff0c;由于服务器不止我一个人使用&#xff0c;最近发现好几次我同学的账户下的bash进程占用特别多&#xff0c;问了他之后&#xff0c;他也说他几次都是没有使用过bash相关服务&a…

029 - STM32学习笔记 - ADC(三) 独立模式单通道DMA采集

029 - STM32学习笔记 - 单通道DMA采集&#xff08;三&#xff09; 单通道ADC采集在上节中学习完了&#xff0c;这节在上节的内容基础上&#xff0c;学习单通道DMA采集。程序代码以上节的为基础&#xff0c;需要删除NVIC配置函数、中段服务子程序、R_ADC_Mode_Config()函数中使能…

JSP forEach 标签遍历map集合

之前我们说了 普通list 单纯按数量循环 bean类型list的遍历方式 那么 我们forEach标签 也能循环map语法非常简单&#xff0c;和循环list基本是一样的 我们直接上jsp代码 <% page import"java.util.Map" %> <% page import"java.util.HashMap" %…

2023网络安全产业图谱

1. 前言 2023年7月10日&#xff0c;嘶吼安全产业研究院联合国家网络安全产业园区&#xff08;通州园&#xff09;正式发布《嘶吼2023网络安全产业图谱》。 嘶吼安全产业研究院根据当前网络安全发展规划与趋势发布《嘶吼2023网络安全产业图谱》调研&#xff0c;旨在进一步了解…

类和对象——(2)类

归纳编程学习的感悟&#xff0c; 记录奋斗路上的点滴&#xff0c; 希望能帮到一样刻苦的你&#xff01; 如有不足欢迎指正&#xff01; 共同学习交流&#xff01; &#x1f30e;欢迎各位→点赞 &#x1f44d; 收藏⭐ 留言​&#x1f4dd; 虽然夜晚很长&#xff0c;但天一…

ABAP算法 模拟退火

模拟退火算法 算法原理及概念本文仅结合实现过程做简述 模拟退火算法是一种解决优化问题的算法。通过模拟固体退火过程中的原子热运动来寻找全局最优解。在求解复杂问题时&#xff0c;模拟退火算法可以跳出局部最优解获取全局最优解。 模拟退火算法包含退火过程和Metropolis算法…

AI模型训练——入门篇(二)

导语&#xff1a;本文主要介绍了基于BERT的文本分类方法&#xff0c;通过使用huggingface的transformers库实现自定义模型和任务。具体步骤包括&#xff1a;使用load_dataset函数加载数据集&#xff0c;并应用自定义的分词器&#xff1b;使用map函数将自定义分词器应用于数据集…

数组中的第 K 个最大元素(C++实现)

数组中的第 K 个最大元素 题目思路代码 题目 数组中的第 K 个最大元素 思路 通过使用优先队列&#xff08;最大堆&#xff09;来找到数组中第k大的元素。通过弹出最大堆中的前k-1个元素&#xff0c;留下堆中的顶部元素作为结果返回。 代码 class Solution { public:int find…

Day41 使用listwidget制作简易图片播放器

1.简介 使用QlistWidget实现简易图片播放器&#xff0c;可以打开一个图片序列&#xff0c;通过item的单击事件实现图片的切换&#xff0c;通过设置list的各种属性实现图片预览的显示&#xff0c;美化滚动条即可实现一个简易图片播放器。 2.效果 3.实现步骤&#xff1a; 1.初始…

QT linux下应用程序打包

一、应用程序app 1、应用程序的pro文件 2、 程序工作函数 3、app的UI界面 二、动态库lib 1、Lib类头文件 2、.cpp文件 三、对应用程序和动态库进行构建 1、对动态库进行qmake,然后进行构建 2、对应用程序进行qmake&#xff0c;然后进行构建 3、查看构建目录 四、编写脚本 …

postgreSQL如何快速查询大表数据量

文章目录 场景方案结果 场景 我有一个非常大的表&#xff0c;估计几百万或者几千万。 我开始使用了 select count(*) from my_table_javapub 方式&#xff0c;查询非常慢。 如何解决&#xff1f;&#xff1f;&#xff1f; 方案 如果你需要更快地获取表中的行数&#xff0c…

【PHP】MySQL简介与MySQLi函数(含PHP与MySQL交互)

文章目录 一、MySQL简介二、MySQLi函数1. 开启mysqli扩展&#xff1a;2. PHP MySQLi扩展的常用函数 三、PHP与MySQL交互0. 准备1. 创建连接&#xff08;mysqli_connect() &#xff09;连接mysql语法 2. 选择数据库&#xff08;mysqli_select_db()&#xff09;3. 在php中操作数据…

如果每天工资按代码行数来算,来看看你每天工资是多少

说在前面 &#x1f63c;&#x1f63c;如果每天的工资取决于我们所编写的代码行数&#xff0c;那么我们的生活会发生怎样的改变&#xff1f;来看看你的同事们今天都提交了多少代码吧&#xff0c;看看谁是卷王&#xff0c;谁在摸鱼&#xff08;&#x1f436;&#x1f436;狗头保命…

HTML新手入门笔记整理:HTML基本介绍

网页 静态页面 仅可供用户浏览&#xff0c;不具备与服务器交互的功能。 动态页面 可供用户浏览&#xff0c;具备与服务器交互的功能。 HTML HTML&#xff0c;全称HyperText Markup Language&#xff08;超文本标记语言&#xff09;,是一种用于创建网页的标准标记语言。用于…

如何应对雨天飞行的挑战?无人机机库防护能力解析

一、 背景介绍 无人机机库是无人机停放和起降场所&#xff0c;类似传统飞机的 hangar&#xff08;飞机库&#xff09;。它是一个专门用于存储、维护和保护无人机的设施。无人机机库的存在有助于提高无人机的安全性&#xff0c;同时也为无人机提供了一个有序的管理场所。 雨天…