当前位置: 首页 > news >正文

排序算法总结(一)冒泡排序和选择排序

访问www.tomcoding.com网站,学习Oracle内部数据结构,详细文档说明,下载Oracle的exp/imp,DUL,logminer,ASM工具的源代码,学习高技术含量的内容。

冒泡排序

这个算法可以说是排序算法中最著名的一个了,名字独特,也好理解,在一个数组中有n个元素,扫描整个数组中没有排序的元素,从第一个元素开始,每个元素与它后面的元素比较,数值小的放在前面,数值大的放在后面,那么经过第一轮扫描,最大的数值就放在了数组最后的位置,就像每个元素是一个气泡,最大的气泡最先浮到数组顶端。第二轮扫描,由于最大的元素已经找到,需要找第二大的元素,这时扫描的元素个数少了一个,变为n-1,经过第二轮扫描,第二大的元素放到了数组倒数第二的位置。依次类推,第三次扫描元素个数变为n-2,第三大的元素排到了倒数第三的位置。这样每次扫描的元素越来越少,最后扫描到未排序的元素只有一个时,排序就结束了,这时数组中的数值按照升序排列好了。

第0轮:扫描n-1个元素,从0开始到n-2,每个元素j与后一个元素j+1比较,小的在前,大的在后,如果不一致时,要把这两个元素交换位置。

第1轮:扫描n-2个元素,从0开始到n-3,每个元素j与后一个元素j+1比较。

第2轮:扫描n-3个元素,从0开始到n-4,每个元素j与后一个元素j+1比较。

第3轮:扫描n-4个元素,从0开始到n-5,每个元素j与后一个元素j+1比较。

……

第n-2轮:扫描1个元素,第0个和第1个元素比较。

第n-1轮:扫描0个元素,结束。其实在上一轮比较完,就可以结束了。

用C语言编写一个函数实现冒泡排序算法,i表示扫描的轮的序号,j表示每一轮中扫描的元素序号(数组下标)。

/* ai是要排序的整数数组指针

 *  n是数组中元素的个数

 */

void bubble_sort(int *ai, int n)

{

    int         i, j, k;

    /* 循环n-1轮 */

    for (i = 0; i < (n-1); i++) {

        /* 每一轮,扫描n-1-i个元素 */

        for (j = 0; j < (n-1-i); j++) {

            if (ai[j] > ai[j+1]) {

                /* 前一个元素比后一个大,交换位置,否则不用交换 */

                k       = ai[j];

                ai[j]   = ai[j+1];

                ai[j+1] = k;

            }

        }

    }

}

选择排序

这个也是经常用到的排序算法,甚至是最容易想到的算法,虽然不好确定它的名字。工作原理如下,把要排序的数组分成两部分,第一部分是排过序的元素集合,第二部分是没有排过序的元素集合,开始时第一部分的元素个数为0,第二部分为全部元素,算法要进行多轮选择,每一轮选择都是从第二部分元素中找到最小的元素,把这个元素放到第一部分的末尾,这样经过多轮选择后,第一部分越来越大,第二部分越来越小,当第二部分元素数为0时,排序就结束了。

实现算法时也有两个关键点要确定,第一个是循环的轮数,假设数组中元素的个数是n,每一轮要找到一个最小数据,所以原则上应该找n轮,其实找到n-1轮时,最后一轮就剩下一个元素了,没有比较的必要了,所以循环的轮数为n-1。第二个是每轮查找元素的个数,看下表。

第0轮,扫描n-0个元素,从0到n-1

第1轮,扫描n-1个元素,从1到n-1

第2轮,扫描n-2个元素,从2到n-1

第3轮,扫描n-3个元素,从3到n-1

……

第n-2轮,扫描2个元素,从n-2到n-1

第n-1轮,扫描1个元素,从n-1到n-1

用C语言写一个函数实现这个算法。

/* ai 是要排序的整数数组

 *  n 是数组中元素的个数

 *

 * 函数中i,j是计数变量

 * min_index是第二部分数组中最小值的元素下标

 * min变量暂存第二部分中最小值

 * tail是第一部分的尾部位置

 * start是第二部分开始扫描的起始位置

 */

static void selection_sort(int *ai, int n)

{

    int         i, j, k, min_index;

    int         min;

    int         tail;

    int         start;

    /* 开始时,第一部分没有元素,尾部在第0个元素 */

    tail = 0;

    for (i = 0; i < (n-1); i++) {

        start = tail;

        min   = ai[start];

        min_index = -1;

        for (j = start; j < n; j++) {

            if (ai[j] < min) {

                min_index = j;

                min = ai[j];

            }

        }

        if (min_index != -1) {

            /* 找到了最小值,交换元素 */

            k             = ai[tail];

            ai[tail]      = ai[min_index];

            ai[min_index] = k;

        }

        tail++;

    }

}

这个函数看起来有些复杂,我们来简化一下。从上面看tail其实就是i的位置,start是i的下一个位置,min值是扫描第二部分的第一个元素,把这些简化后,得到下面的函数。

void selection_sort(int *ai, int n)

{

    int         i, j, k;

    int         min_index;

    for (i = 0; i < (n-1); i++) {

        min_index = i;

        for (j = i+1; j < n; j++) {

            if (ai[j] < ai[min_index])

                min_index = j;

        }

        if (min_index != i) {

            /* 交换元素 */

            k             = ai[i];

            ai[i]         = ai[min_index];

            ai[min_index] = k;

        }

    }

}

检查排序结果

写一个函数来检查一下排序后的元素顺序有没有错误,方法很简单,在数组中遍历一次,看看前一个元素是否比后一个元素大,如果大就说明排序出错了。

void check_result(int *ai, int n)

{

    int         i;

    for (i=0; i<n-1; i++) {

        if (ai[i] > ai[i+1]) {

            fprintf(stderr, "error, element[%d]=%d, element[%d]=%d\n\n", i, ai[i], i+1, ai[i+1]);

            return;

        }

    }

    fprintf(stdout, "element is sorted.\n\n");

}

写一个程序测试一下排序结果。

int main(int argc, char *argv[])

{

    static int  chaos[16] = {23, 6, 235, 89, 4, 12, 76, 35, 129, 30, 77, 15, 61, 44, 49, 88};

    int         array[16];

    fprintf(stdout, "test for bubble_sort function.\n\n");

    memcpy(array, chaos, 16*sizeof(int));

    bubble_sort(array, 16);

    check_result(array, 16);

    fprintf(stdout, "test for selection_sort function.\n\n");

    memcpy(array, chaos, 16*sizeof(int));

    selection_sort(array, 16);

    check_result(array, 16);

    return (0);

}

相关文章:

排序算法总结(一)冒泡排序和选择排序

访问www.tomcoding.com网站&#xff0c;学习Oracle内部数据结构&#xff0c;详细文档说明&#xff0c;下载Oracle的exp/imp&#xff0c;DUL&#xff0c;logminer&#xff0c;ASM工具的源代码&#xff0c;学习高技术含量的内容。 冒泡排序 这个算法可以说是排序算法中最著名的…...

伺服电动缸

美国EXLAR原装K系列伺服缸 高精度运动&#xff0c;运动平稳&#xff0c;低噪音&#xff0c;高速度 向下翻动查看更多 力姆泰克伺服电动缸 k系列电动缸采用Exlar滚柱丝杠技术&#xff0c;提供多种不同性能等级的产品&#xff0c;可外配第三方电机。 通用型设计&#xff0c;无…...

深度学习中的logit到底是什么?

1. 问题 在做深度学习的过程中&#xff0c;经常会碰到logit。这个和在学校学的概率有出入&#xff0c;因而想弄明白这到底是个什么参数。 2. 使用logit的原因 定义几率&#xff08;odds&#xff09;和 logit 函数的主要原因在于使用了线性空间转换&#xff0c;使得非线性的概…...

idea使用记录

文章目录 1、idea调出maven窗口2、跳转到指定行 1、idea调出maven窗口 首先尝试菜单栏View→Tool Windows→Maven&#xff0c;如果没有maven那很有可能是idea没有识别到这是一个maven项目&#xff0c;此时可以尝试在项目的pom文件上右击&#xff0c;选择“add as maven projec…...

Python - HTTP servers

python的http.server模块用于HTTP服务器的功能&#xff0c;这个模块是python标准库的一部分&#xff0c;不需要pip install。 使用前需要import&#xff1a; import http.server 然后就可以编辑代码&#xff0c;使用此模块提供的接口&#xff0c;实现http server相关功能。 除…...

内网Debian\Ubuntu服务器安装dep包,基于apt-rdepends下载相关依赖

文章目录 背景一、下载依赖二、拷贝到内网三、 使用dpkg安装可能会遇到的问题 背景 由于生产服务器是Debian\Ubuntu系统且在内网环境&#xff08;不联网&#xff09;&#xff0c;需要使用拷贝deb格式的包使用dpkg的方式进行安装。所以&#xff0c;需要现在联网的环境中将所需的…...

大模型——如何实现超长多轮对话

在自然语言处理的领域中&#xff0c;多轮对话系统是构建智能化交互应用的关键。无论是聊天机器人、虚拟助手&#xff0c;还是客户服务系统&#xff0c;能够保持连贯的对话并记住上下文信息是用户体验的核心。然而&#xff0c;大规模语言模型&#xff08;如GPT等&#xff09;的对…...

大数据面试-笔试SQL

一个表table: c_id u_id score&#xff1b;用SQL计算每个班级top5学生的平均分&#xff08;腾讯&#xff09; select class_id,avg(score) as score_avg from (select *,row_number() over(partition by class_id order by score desc) as score_rank from table ) t1 where t…...

希尔排序和直接插入排序

因为排序这些比较复杂点我就分几期给大家来讲~~~ 直接插入排序 直接插入排序是一种简单的排序算法&#xff0c;主要用于对少量数据进行排序。其基本思想是将待排序的元素逐个插入到已经排好序的部分中&#xff0c;从而形成一个有序序列。 具体步骤如下&#xff1a; 初始化&…...

IDEA 配置 Git 详解

本文将介绍在IntelliJ IDEA 中如何配置Git 没有安装配置 Git 的可以参考我的这篇文章&#xff1a;安装配置 Git 一、操作环境及准备 1.win 10 2.已安装且配置了Git 3.有Gitee账户 4.安装了IntelliJ IDEA 2023.2.1 5.全程联网 二、配置步骤 2.1 配置git 1.采用全局设置&…...

Docker 部署 Redis 监控系统实战:Redis Exporter 与 Prometheus 完整配置指南

Docker 部署 Redis 监控系统实战&#xff1a;Redis Exporter 与 Prometheus 完整配置指南 文章目录 Docker 部署 Redis 监控系统实战&#xff1a;Redis Exporter 与 Prometheus 完整配置指南一 缓存简述二 redis exporter 部署三 环境变量配置四 修改文件权限五 验证 exporter …...

高级算法设计与分析-MaxFlow网络流基础知识

MaxFlow网络流 1 网络流基础概念 source:源点 sink:终点 Flow:流量 capacity:容量 Residual:残量 Residual Network:残量网络 Augmenting path:增广路径,表示从源点 s 到终点 t 不包含环的路径 Bottleneck capacity:瓶颈容量 2 最大流 2.1 基础概念 2.2 增广路算法 …...

Java项目实战II基于Java+Spring Boot+MySQL的桂林旅游景点导游平台(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者 一、前言 桂林&#xff0c;以其独特的喀斯特地貌、秀美的自然风光闻名遐迩&#xff0c;每年吸引着无数国内外游…...

C语言-输入输出

实验一&#xff1a;编写一个输出两行自定义字符的 C 程序 一、实验目的 熟悉 C 语言的基本结构和语法。掌握 printf() 函数的使用方法。了解在 Code::Blocks 中编写、编译和运行程序的过程。 二、实验内容 编写一个 C 程序&#xff0c;要求输出两行字符&#xff0c;内容自定…...

如何在GitHub上传自己的项目?(一文看懂,每一步的操作和解决常见错误的方法)

目录 步骤一&#xff1a;准备 Git 环境 1. 安装 Git 2. 配置 Git 步骤二&#xff1a;在 GitHub 创建一个新的仓库 1. 登录到你的 GitHub 账号。 2. 点击右上角的 号&#xff0c;然后选择 New repository。 3. 填写以下信息&#xff1a; 步骤三&#xff1a;将本地项目上…...

数据结构_day1

目录 大纲 1.数据结构基础知识 1.1 什么是数据结构 1.2 数据 1.3 逻辑结构 1.4 存储结构 1.4.1 顺序存储 1.4.2 链式存储 1.4.3 索引存储结构 1.4.4 散列存储 1.5 操作 2.算法基础知识 2.1 什么是算法 2.2 算法的设计 2.3 算法的特性 2.4 评价算法的好坏 大纲 数据结构、算法(理…...

c# using 声明进行资源管理

在 C# 8 中&#xff0c;using 声明引入了一种新的语法&#xff0c;称为 using 声明&#xff0c;它使得开发人员在处理资源时的代码更加简洁和清晰。主要的变化包括 使用声明 和 使用上下文&#xff08;using declaration&#xff09; 的引入。 使用语句的简化 在 C# 8 中&…...

Kafka之基本概念

1、Kafka是什么&#xff1f; Kafka是由Scala语言开发的一个多分区、多副本&#xff0c;基于Zookeeper集群协调的系统。 那这个所谓的系统又是什么系统呢&#xff1f; 回答这个问题要从发展的角度来看&#xff1a;起初Kafka的定位是分布式消息系统。但是目前它的定位是一个分布…...

倪师学习笔记-天纪-斗数简介

一、学习过程 学习->验证->思考 二、算命方法 算命方法特点铁板神数适合核对六亲子平法准确度一般紫微斗数天文地理融合最好&#xff0c;批六亲不准&#xff0c;配合相可以提升准确率 三、果 天地人三者一起影响果&#xff0c;天时地利人和促成成功1/31/31/31算命部…...

Python酷库之旅-第三方库Pandas(143)

目录 一、用法精讲 646、pandas.Timestamp.is_quarter_start属性 646-1、语法 646-2、参数 646-3、功能 646-4、返回值 646-5、说明 646-6、用法 646-6-1、数据准备 646-6-2、代码示例 646-6-3、结果输出 647、pandas.Timestamp.is_year_end属性 647-1、语法 647…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

「Java基本语法」变量的使用

变量定义 变量是程序中存储数据的容器&#xff0c;用于保存可变的数据值。在Java中&#xff0c;变量必须先声明后使用&#xff0c;声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例&#xff1a;声明与初始化 public class VariableDemo {publi…...