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

【C/C++数据结构 - 2】:稳定性与优化揭秘,揭开插入排序、希尔排序和快速排序的神秘面纱!

文章目录

  • 排序的稳定性
  • 插入排序
    • 插入排序的优化
  • 希尔排序
  • 快速排序

排序的稳定性

稳定排序:排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同。(比如:冒泡、插入、基数、归并)

非稳定排序:排序前2个数的相对位置在排序后会发生改变。(比如:选择、快速、希尔、堆等)

插入排序

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。

插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。

在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

void Insertion_Sort(int a[], int len)
{//外层循环 - 插入数据量for (int i = 1; i < len; i++){//内层循环 - 每一趟需要做的事情for (int j = i - 1; j > -1; j--){if (a[j]>a[j + 1]){int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}

插入排序的优化

在下面函数中,通过使用一个临时变量temp来保存当前需要插入的元素。外层循环通过对整个待排序序列进行遍历,从第二个元素开始(下标为1),将当前元素保存在temp中。

然后,内层循环从当前元素的前一个元素开始向前遍历,直到找到合适的位置插入temp。在内层循环中,如果当前遍历到的元素大于temp,就将该元素后移一位,给temp腾出位置。

内层循环结束后,将temp插入到合适的位置,即将其赋值给a[j+1],这样就完成了一次元素的插入。

通过这种方式,不断地将元素逐个地插入到已排序的序列中,最终得到一个完全有序的序列。

void Insertion_Sort(int a[], int len)
{int temp, i, j;//外层循环 - 插入数据量for (i = 1; i < len; i++){temp = a[i];//内层循环 - 每一趟需要做的事情for (j = i - 1; j > -1 && a[j] > temp; j--){a[j + 1] = a[j];}//移动结束a[j + 1] = temp;}
}

希尔排序

希尔排序(Shell Sort)是一种改进的插入排序算法,也被称为“缩小增量排序”(Diminishing Increment Sort)。希尔排序通过将待排序序列分割成多个子序列来进行排序,最终将这些子序列逐步合并为一个有序序列。

希尔排序的核心思想是通过定义一个增量序列(也称为间隔序列),将待排序序列划分成若干个子序列,并对这些子序列分别进行插入排序。随着排序的进行,增量序列会不断减小,直到变为1,此时对整个序列进行一次插入排序,最终完成排序。

希尔排序的步骤如下:

  • 首先确定一个增量序列,一般选择初始增量为序列长度的一半,然后每次将增量折半,直到增量变为1。

  • 对每个增量进行插入排序,即将待排序序列划分成若干个子序列,对每个子序列进行插入排序。

  • 在每次插入排序中,按照增量的大小,将元素分组,对每组进行插入排序。

  • 不断缩小增量,重复步骤2和步骤3,直到增量为1,进行最后一次插入排序,完成排序。

举个例子:

  • 如下图所示,现有一序列:8、5、7、3、6、1、2、8,选择初始增量为序列长度的一般,即初始增量为4(分为四个组,标红数字所示)。
    在这里插入图片描述
  • 第一次交换(组别增量为4)
    • 8和6为一组,5和1为一组……,队每组中的数比较排序,(例:第一组排序,8比6大,则8、6互换位置,以此类推)排序后的结果如下图所示。
      在这里插入图片描述
  • 第二次交换(组别增量由4变为2)如下图所示。
    在这里插入图片描述
    • 先对1组进行比较,首先6作为已序。
    • 第一次比较:1组的第一个数(6)与第二个数(2)进行比较,2<6小,插入到6的位置,6换到2的位置。
    • 第二次比较:1组的第二个数(6)与第三个数(8)进行比较,6<8,则不进行插入。
    • 第三次比较:1组的第三个数(8)与第4个数(7)进行比较,8>7,所以7插入到8的位置,8换到7的位置。
    • 最终1组排序的结果如下:
      在这里插入图片描述
    • 同理,对2组进行比较后的结果如下图所示。
      在这里插入图片描述
  • 第三次交换(组别增量从2变为1)
    在这里插入图片描述
    • 组别增量变为1之后,对整体做插入排序,结果如下。
      在这里插入图片描述

希尔排序函数:

//希尔排序
void Shell_Sort(int a[], int len)
{int temp, i, j, n = 0;//增量分组int jump = len >> 1;while (jump != 0){//外层循环 - 插入数据量for (i = jump; i < len; i++){temp = a[i];//内层循环for (j = i - jump; j >= 0 && a[j]>temp; j -= jump){a[j + jump] = a[j];n += 1;}//移动结束a[j + jump] = temp;}//增量更新jump >>= 1;}
}

分别在优化后的插入排序函数和希尔排序中定义一个变量n,用来统计各自进行数据交换的次数,结果如下:

在这里插入图片描述

插入排序交换的次数约是希尔排序交换次数的两倍!

快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。

快速排序的核心思想是通过分治法将一个大的待排序序列逐步地分割成小的子序列,然后对这些子序列进行排序,最终得到一个有序序列。具体步骤如下:

  1. 选择一个基准元素(pivot),可以是序列中的任意一个元素。
  2. 将序列分为两部分,小于等于基准元素的部分和大于基准元素的部分。可以通过两个指针 i 和 j 来实现,开始时 i 指向序列的第一个元素,j 指向序列的最后一个元素。
    • 从左向右找出第一个大于基准元素的元素,记为 a。
    • 从右向左找出第一个小于等于基准元素的元素,记为 b。
    • 如果 i < j,则交换 a 和 b 的位置,然后继续找下一对 a 和 b。
    • 如果 i >= j,则停止查找。
  3. 将基准元素与 j 所指向的元素交换位置,即将基准元素放在合适的位置。
  4. 递归地对基准元素左边和右边的子序列进行快速排序。

以下是一个使用 C 语言实现的快速排序代码示例:

#include <stdio.h>// 交换两个元素的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 快速排序的递归函数
void quickSort(int arr[], int low, int high)
{if (low < high) {int pivot = arr[low];  // 选择第一个元素作为基准元素int i = low, j = high;while (i < j){while (i < j && arr[j] > pivot) {j--;}while (i < j && arr[i] <= pivot) {i++;}if (i < j) {swap(&arr[i], &arr[j]);}}swap(&arr[low], &arr[i]);quickSort(arr, low, i - 1);  // 对左边子序列进行快速排序quickSort(arr, i + 1, high); // 对右边子序列进行快速排序}
}// 打印数组元素
void printArray(int arr[], int size) 
{for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() 
{int arr[] = {8, 5, 7, 3, 6, 1, 2, 8};int size = sizeof(arr) / sizeof(arr[0]);printf("原始数组:");printArray(arr, size);quickSort(arr, 0, size - 1);printf("排序后数组:");printArray(arr, size);return 0;
}

输出结果:

在这里插入图片描述

分析程序:
代码首先定义了一个 swap 函数用于交换两个元素的值。然后,quickSort 函数使用递归实现了快速排序的具体操作。最后,在 main 函数中创建一个待排序的数组,并调用 quickSort 函数对数组进行排序。最终,通过调用 printArray 函数打印排序后的数组。

相关文章:

【C/C++数据结构 - 2】:稳定性与优化揭秘,揭开插入排序、希尔排序和快速排序的神秘面纱!

文章目录 排序的稳定性插入排序插入排序的优化 希尔排序快速排序 排序的稳定性 稳定排序&#xff1a;排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同。&#xff08;比如&#xff1a;冒泡、插入、基数、归并&#xff09; 非稳定排序&#xff1a;排…...

PCL点云处理之基于强度特征的SIFT关键点提取法 (二百一十五)

PCL点云处理之基于强度特征的SIFT关键点提取法 (二百一十五) 一、算法介绍二、具体实现1.代码2.效果一、算法介绍 继续SIFT关键点的提取介绍,之前已经基于高程和颜色分别提取了关键点,这里是基于强度信息,若遇到文件无法读取强度问题,请参考上一篇博文,下面是具体的实现…...

uniapp打包配置

安卓&#xff1a; 首先不管是什么打包都需要证书&#xff0c;安卓的证书一般都是公司提供或者自己去申请。然后把包名等下图框住的信息填上&#xff0c;点击打包即可。 ios&#xff1a;ios需要使用mac到苹果开发者平台去申请证书&#xff0c;流程可以参考下边的链接 参考链接…...

人大金仓分析型数据库最大量限制

数据库支持的最大量限制&#xff1a; 维度 限制 数据库大小 无限 表大小 无限 行大小 1.6 TB 域大小 1 GB 每个表的行数 281474976710656 (2^48) 每个表 / 视图的列数 1600 每个表的索引数 无限 每个索引的列数 32 每个表的表级约束 无限 表名长度 63 字节 列出的“无限”…...

centos 里面的service自启动app.jar,出现两个java进程,app是同一个端口

当使用jps -lv查看java虚拟机进程 app.jar启动后&#xff0c;居然出现两个启动进程&#xff0c;而且他们的端口都一样&#xff0c;同一端口&#xff0c;是不允许启动两个相同app的。 使用进程ps查看进程工具 #ps -aux 参数说明&#xff1a; a: 显示跟当前终端关联的所有进…...

【算法|双指针系列No.7】leetcodeLCR 007. 三数之和

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

ubuntu修改IP地址

参考&#xff1a;ubuntu修改配置IP地址和DNS的方法总结&#xff08;4种&#xff09;_ubuntu设置ip地址-CSDN博客 面对ubuntu18以上的版本&#xff0c;主要有两种界面&#xff1a;图形化界面和纯命令行界面。 图形化界面配置比较简单&#xff0c;命令行配置稍许复杂&#xff0c…...

java springboot 通过ConfigurationProperties给第三方bean注入属性

之前我们的文章 java boot将一组yml配置信息装配在一个对象中 讲过了 通过ConfigurationProperties将配置文件中的内容默认装配进属性类 但 这建立在 bean是自己定义的 如果 这是个第三方的类呢&#xff1f; 就比如 我们在 application 中写了一套数据源的加载规则 但需要用第…...

windows系统安装openssl并且转换证书格式

概述 碎碎念&#xff0c;如果你有MAC电脑&#xff0c;就别折腾了&#xff0c;直接用MAC电脑吧,不用安装直接用openssl 本文主要讲到了openssl的基本使用方法&#xff0c;开发环境为windows&#xff0c;开发工具为VS2019.本文主要是说明openssl如何使用&#xff0c;不介绍任何理…...

【GO】基础速成

简单介绍一下go好处 编译语言&#xff0c;可以提前报错同时又有python的一些优点&#xff0c;自带多线程 开始学习 学习网站&#xff1a;学习网站 值 包含&#xff1a;字符串、整型、浮点型、布尔型等等 字符串可以 进行拼接。 需要注意的是布尔型在go里面不自动转化为in…...

五子棋(C语言实现)

目录 构思 1、主程序 2、初始化 3、游戏菜单 4、打印棋盘 6、玩家下棋 7、判断输赢 8、功能整合 人机下棋 完整版&#xff1a; game.h game.c text.c 测试功能代码 构思 五子棋不必多介绍了&#xff0c;大家小时候都玩过哈。 我们要通过程序实现这个小游戏&…...

thymeleaf,bootstrap-fileinput 多文件上传

组件遍历上传 一、前端 <!DOCTYPE html> <html lang"zh" xmlns:th"http://www.thymeleaf.org" > <head><th:block th:include"include :: header(修改固定资产信息)" /><th:block th:include"include :: date…...

爬虫 | 基础模块了解

文章目录 &#x1f4da;http协议&#x1f4da;requests模块&#x1f4da;re模块&#x1f407; re.I 或 re.IGNORECASE&#x1f407;re.M或 re.MULTILINE&#x1f407;re.S 或 re.DOTALL&#x1f407; re.A 或 re.ASCII&#x1f407; re.X 或 re.VERBOSE&#x1f407;特殊字符类…...

CSS复习笔记

CSS 文章目录 CSS1.概念2.CSS 引入方式3.选择器基础选择器:标签选择器类选择器id 选择器通配符选择器 复合选择器:**后代选择器****子代选择器****并集选择器****交集选择器-了解****伪类选择器** 结构伪类选择器&#xff1a;**:nth-child&#xff08;公式&#xff09;**伪元素…...

编译linux的设备树

使用make dtbs命令时 在arch/arm 的目录Makefile文件中有 boot : arch/arm/boot prepare 和scripts是空的 在文件scripts/Kbuild.include中 变量build : -f $(srctree)/scripts/Makefile.build obj build变量虽然没有在arch/arm 的目录Makefile文件中定义&#xff0c;但…...

⛳ MyBatis 中 Mapper 接口工作原理实例解析

&#x1f38d;目录 ⛳ MyBatis 中 Mapper 接口工作原理实例解析&#x1f3a8; 一、Mapper 接口是怎么找到实现类的&#xff1f;&#x1f43e; 二、从一段代码看起&#x1f69c; 三、Mapper 接口&#x1f3ed; 四、Mapper 接口的动态代理类的生成&#x1f381; 五、总结 ⛳ MyBa…...

Android 音频可视化

Android音频可视化&#xff0c;指的是将音频的频率绘制到屏幕上&#xff0c;达到一种视觉效果&#xff0c;使播放或录制过程更加生动形象。 在Android进行视频可视化涉及的三个主要知识点,其中比较难以理解的傅里叶变换公式。 Android原生的Visualizer使用&#xff08;获取频…...

刷机与救砖避坑指南

提示&#xff1a;快速进行刷机和救砖学习理解 文章目录 一、刷机1.什么是刷机&#xff0c;需要进行那些准备&#xff1f;2.刷机1.解开bl&#xff08;bootloader&#xff09;锁2.刷入TWRP和Magsik3.刷入第三方ROM 二、救砖&#xff08;9008&#xff09;1.手机售后一键线刷包&…...

软件建模知识点

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 例如&#xff1a;…...

WSL 配置 Linux

WSL 配置 Linux Windows 启动 Linux 子系统 控制面板 -> 程序和功能&#xff0c; 将 适用于 Linux 的 Windows 子系统 勾选。 安装 Terminal 在 Microsoft Store 市场上搜索 Terminal 安装 Windows Terminal。 安装 编译工具链 sudo apt update # 更新软件包 sudo apt i…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

k8s从入门到放弃之Pod的容器探针检测

k8s从入门到放弃之Pod的容器探针检测 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;容器探测是指kubelet对容器执行定期诊断的过程&#xff0c;以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...

计算机系统结构复习-名词解释2

1.定向&#xff1a;在某条指令产生计算结果之前&#xff0c;其他指令并不真正立即需要该计算结果&#xff0c;如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方&#xff0c;那么就可以避免停顿。 2.多级存储层次&#xff1a;由若干个采用不同实现技术的存储…...