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

【海贼王的数据航海】排序——概念|直接插入排序|希尔排序

目录

1 -> 排序的概念及其运用

1.1 -> 排序的概念

1.2 -> 常见的排序算法

2 -> 插入排序

2.1 -> 基本思想

2.2 -> 直接插入排序

2.2.1 -> 代码实现

2.3 -> 希尔排序(缩小增量排序)

2.3.1 -> 代码实现


1 -> 排序的概念及其运用

1.1 -> 排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序不变,即在原序列中,r[ i ] = r[ j ],且r[ i ] 在 r[ j ]之前,而在排序后的序列中,r[ i ] 仍在 r[ j ]之前,则称这种排序算法是稳定的;否则称为不稳定。

内部排序:数据元素全部放在内存中的排序。

外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 -> 常见的排序算法

2 -> 插入排序

2.1 -> 基本思想

直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。

实际中我们玩扑克牌时,就用到了插入排序的思想。

2.2 -> 直接插入排序

当插入第i(i >= 1)个元素时,前面的arr[0],arr[1],arr[2]……,arr[i - 1]已经排好序,此时用arr[i]的排序码与arr[i - 1],arr[i - 2]……的排序码顺序进行比较,找到插入位置即将arr[i]插入,原来位置上的元素顺序后移。

直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高;
  2. 时间复杂度:O(N^{2})
  3. 空间复杂度:O(1),他是一种稳定的排序算法;
  4. 稳定性:稳定;

2.2.1 -> 代码实现

#define  _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 打印
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++)printf("%d ", a[i]);printf("\n");
}// 插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[i + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];--end;}else{break;}a[end + 1] = tmp;}}
}void TestInsertSort()
{int a[] = { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();return 0;
}

2.3 -> 希尔排序(缩小增量排序)

希尔排序法又称缩小增量法。希尔排序的基本思想就是:先选定一个整数,把待排序文件中所有记录分成各子序列,并对每一组内的记录进行排序,重复上述分组和排序的工作。当gap = 1时,完成排序。

希尔排序的特性总结:

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序了,这样就会很快。整体而言,可以达到优化的效果。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算。
  4. 稳定性:不稳定。

2.3.1 -> 代码实现

#define  _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[i + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];--end;}else{break;}a[end + 1] = tmp;}}
}// 希尔排序
void ShellSort(int* a, int n)
{int gap = n;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}void TestShellSort()
{int a[] = { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestShellSort();return 0;
}


感谢大佬们的支持!!!

互三啦!!!

相关文章:

【海贼王的数据航海】排序——概念|直接插入排序|希尔排序

目录 1 -> 排序的概念及其运用 1.1 -> 排序的概念 1.2 -> 常见的排序算法 2 -> 插入排序 2.1 -> 基本思想 2.2 -> 直接插入排序 2.2.1 -> 代码实现 2.3 -> 希尔排序(缩小增量排序) 2.3.1 -> 代码实现 1 -> 排序的概念及其运用 1.1 -&g…...

Docker环境快速搭建RocketMq

window上面安装&#xff1a; 1.Namesrv docker pull rocketmqinc/rocketmq创建C:/docker/rocketmq/data/namesrv/logs:/root/logs C:/docker/rocketmq/data/namesrv/store:/root/store 目录 namesrv: docker run -d --restartalways --name rmqnamesrv -p 9876:9876 -v C:/do…...

【leetcode热题】比较版本号

难度&#xff1a; 中等通过率&#xff1a; 22.1%题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目描述 比较两个版本号 version1 和 version2。 如果 version1 > version2 返回 1&#xff0c;如果 version1 < version2 返回 -1&#xff0c; 除此之外…...

【ArcGISPro】道路数据下载并使用

下载 下载链接: Geofabrik 下载服务器 这些数据通常 每天更新。 下载结果 arcmap用户下载工具 10.2:http://www.arcgis.com/home/item.html?id=16970017f81349548d0a9eead0ebba39 10.3:...

DataGrip 面试题及答案整理,最新面试题

DataGrip的数据库兼容性和多数据库支持如何实现&#xff1f; DataGrip实现数据库兼容性和多数据库支持的方式包括&#xff1a; 1、广泛的数据库支持&#xff1a; DataGrip支持多种数据库&#xff0c;包括但不限于MySQL, PostgreSQL, SQL Server, Oracle, SQLite, 和MongoDB&a…...

2、设计模式之单例模式详解(Singleton)

单例模式详解 一、什么是单例模式 单例模式是Java中最简单的设计模式之一。这种类型的设计模式属于创建者模式&#xff0c;它提供了一种访问对象的最佳方式。 这种设计模式涉及到一个单一的类&#xff0c;该类负责创建自己的对象&#xff0c;同时确保只有单个对象被创建。这个…...

【django framework】ModelSerializer+GenericAPIView,如何在提交前修改某些字段值

【django framework】ModelSerializerGenericAPIView&#xff0c;如何在提交前修改某些字段值 我们经常会遇到下面这种情况&#xff1a; 序列化器用的是ModelSerializer&#xff0c;写视图的时候继承的是generics.CreateAPIView。现在我想在正式提交到数据库(perform_create)之…...

2024年【P气瓶充装】模拟考试及P气瓶充装证考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 P气瓶充装模拟考试是安全生产模拟考试一点通生成的&#xff0c;P气瓶充装证模拟考试题库是根据P气瓶充装最新版教材汇编出P气瓶充装仿真模拟考试。2024年【P气瓶充装】模拟考试及P气瓶充装证考试 1、【多选题】《中华…...

<JavaEE> 数据链路层 -- 以太网协议、MTU限制、ARP协议

目录 以太网协议 什么是以太网&#xff1f; 以太网的帧格式 什么是MAC地址&#xff1f; MAC地址和IP地址的对比&#xff1f; MTU&#xff08;最大传输单元&#xff09;限制 什么是MTU限制&#xff1f; MTU对IP协议有什么影响&#xff1f; MTU对UDP协议有什么影响&…...

认识Testbench仿真激励

一、认识Testbench Bench有平台之意&#xff0c;所以Testbench就是测试平台的意思。 任何一个被测模块&#xff0c;都有输入和输出&#xff0c;此模块是否合格的判断依据&#xff0c;就是在满足输入要求的情况下&#xff0c;能否得到符合预期的输出。我们把被测模块称作UUT&…...

Postman请求API接口测试步骤和说明

Postman请求API接口测试步骤 本文测试的接口是国内数智客&#xff08;www.shuzike.com&#xff09;的API接口手机三要素验证&#xff0c;验证个人的姓名&#xff0c;身份证号码&#xff0c;手机号码是否一致。 1、设置接口的Headers参数。 Content-Type&#xff1a;applicati…...

这是二叉搜索树吗?

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树&#xff1a;对于任一结点&#xff0c; 其左子树中所有结点的键值小于该结点的键值&#xff1b;其右子树中所有结点的键值大于等于该结点的键值&#xff1b;其左右子树都是二叉搜索树。 所谓二叉搜索树的“镜像”&#xf…...

5.82 BCC工具之tcpdrop.py解读

一,工具简介 tcpdrop工具打印被内核丢弃的 TCP 数据包或段的详细信息,包括导致丢弃的内核堆栈跟踪。 当网络出现拥堵、资源不足或其他原因导致数据包被内核丢弃时,tcpdrop可以帮助开发者和网络管理员识别并定位问题。 该工具通过钩住内核中处理TCP数据包的相关函数,捕获…...

JavaScript 基础知识

一、初识 JavaScript 1、JS 初体验 JS 有3种书写位置&#xff0c;分别为行内、内部和外部。 示例&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"wid…...

【判断是否为回文数】

法一&#xff1a;用字符串形式判断&#xff08;依次对比前面和后面的数是否相等&#xff09; #include<stdio.h> #include<string.h> int main() {char st[100];scanf("%s",st);int flag1,nstrlen(st);for(int i0,jn-1;i<n,j>0;i,j--){if(st[i]!…...

【C++】string进一步介绍

个人主页 &#xff1a; zxctscl 如有转载请先通知 文章目录 1. 前言2. 迭代器2.1 反向迭代器2.2 const对象迭代器 3. Capacity3.1 size和length3.2 max_size3.3 capacity3.4 clear3.5 shrink_to_fit &#xff08;了解即可&#xff09;3.6 reserve3.7 resize 4. Element access4…...

思科设备下面主机访问公网经常时好时坏延迟大丢包不稳定

环境: 思科防火墙ASA5555 Cisco Adaptive Security Appliance Software Version 9.4(2)6 Device Manager Version 7.5(2)153 内外为DMZ区域 思科交换机(C3560E-UNIVERSALK9-M), Version 12.2(55)SE5 主机 centos 7 问题描述: 思科设备下面主机访问公网经常时好时坏不稳定…...

nuxtjs 如何通过ecosystem.config.js配置pm2?

在 Nuxt.js 项目中&#xff0c;您可以通过 ecosystem.config.js 文件来配置 PM2&#xff0c;以便使用 PM2 来管理 Nuxt.js 应用的进程。ecosystem.config.js 是一个特殊的配置文件&#xff0c;它允许您定义应用的各种属性&#xff0c;如脚本路径、环境变量、日志设置等。 下面…...

个人博客系列-后端项目-用户注册功能(7)

介绍 用户注册API的主要流程&#xff1a;1.前端用户提交用户名&#xff0c;密码 2. 序列化器校验用户名&#xff0c;密码是否合法。3.存入数据库。4.签发token 创建序列化器 from rest_framework import serializers from rest_framework_simplejwt.serializers import Toke…...

vue项目因内存溢出启动报错

前端能正常启动&#xff0c;但只要一改动就报错启动出错。 解决办法&#xff1a; 安装依赖 npm install cross-env increase-memory-limit 然后再做两件事&#xff1a;在node 在package.json 里的 script 里进行配置 LIMIT是你想分配的内存大小&#xff0c;这里的8192单位…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...