算法:排序

排序算法

  • 1. 简单排序
    • 1.1 直接插入排序
    • 1.2 冒泡排序
    • 1.3 简单选择排序
  • 2. 希尔排序
  • 3. 快速排序
  • 4. 堆排序
  • 5. 归并排序

将文件的内容按照某种规则进行排列。

排序算法的稳定判定:若在待排序的一个序列中, R i R_i Ri R j R_j Rj的关键码相同,即 k i = k j k_i=k_j ki=kj,且在排序前 R i R_i Ri领先于 R j R_j Rj,那么当排序后,如果 R i R_i Ri R j R_j Rj的相对次序保持不变, R i R_i Ri仍领先于 R j R_j Rj,则称此类排序方法为稳定的。若可能出现 R j R_j Rj领先于 R i R_i Ri的情况,则称此列排序是不稳定的。

排序可分为内部排序和外部排序,通过是否全部在内存中排序进行判定。

排序完成两个操作:

  1. 比较两个关键码的大小;
  2. 将记录从一个位置移动到另一个为止。

1. 简单排序

1.1 直接插入排序

将某个数据插入已经排好的队列中。

void insertSort(int data[], int n)
{int i, j;int temp;for (i = 1; i < n; i++){if (data[i] < data[i - 1]) {temp = data[i]; data[i] = data[i - 1];for (j = i - 2; j >= 0 && data[j] > temp; j--) data[j + 1] = data[j];data[j+1] = temp;}}
}

运行结果:

int array[8] = {12, 18184, 45, 78, 45, 555, 47, 36};insertSort(array, 8);for (int i = 0; i < 8; i++)
{printf("%d\n", array[i]);
}

在这里插入图片描述
直接插入排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。排序过程中仅需要一个元素的辅助空间,空间复杂度为 O ( 1 ) O(1) O(1)。直接插入排序是一种稳定的排序方法。

1.2 冒泡排序

顾名思义,冒泡法就是像气泡上浮一样把数据逐渐传递上去。

void bubbleSort(int data[], int n) 
{int i, j, tag = 1;   //tag表示排序过程中是否交换过元素值int temp;for (i = 1; tag && i < n; i++){tag = 0;for (j = 0; j < n - i; j++){if (data[j]>data[j+1]){temp = data[j];data[j] = data[j+1];data[j + 1] = temp;tag = 1;}}}
}
int array[8] = {12, 18184, 45, 78, 45, 555, 47, 36};
//insertSort(array, 8);
bubbleSort(array, 8);for (int i = 0; i < 8; i++)
{printf("%d\n", array[i]);
}

在这里插入图片描述
冒泡排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。排序过程中仅需要一个元素的辅助空间,空间复杂度为 O ( 1 ) O(1) O(1)。冒泡排序是一种稳定的排序方法。

1.3 简单选择排序

逐步找出最小的元素,依次放置。

void selectSort(int data[], int n)
{int i, j, k;int temp;for (i = 0;  i < n-1; i++){k = i;for ( j = i+1; j < n; j++){if (data[j] < data[k]) k = j;}if (k!=i){temp = data[i];data[i] = data[k];data[k] = temp;}}
}

算法结果:

int array[8] = {12, 18184, 45, 78, 45, 555, 47, 36};//insertSort(array, 8);
//bubbleSort(array, 8);
selectSort(array, 8);for (int i = 0; i < 8; i++)
{printf("%d\n", array[i]);
}

在这里插入图片描述
简单选择排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。排序过程中仅需要一个元素的辅助空间,空间复杂度为 O ( 1 ) O(1) O(1)。简单选择排序是一种不稳定的排序方法。

2. 希尔排序

希尔排序又称为“缩小增量排序”,是对直接插入排序方法的改进。
希尔排序的基本思想是:先将整个待排记录序列分割成若干子序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。具体做法是先取一个小于n的整数 d 1 d_1 d1作为第一个增量,将所有相距为 d 1 d_1 d1的记录放在同一个组中,从而把文件的全部记录分成 d 1 d_1 d1组,在各组内进行直接插入排序;然后取第二个增量 d 2 ( d 2 < d 1 ) d_2(d_2<d_1) d2(d2<d1),重复上述分组和排序工作,依此类推,直至所取的增量 d i = 1 ( d i < d i − 1 < . . . < d 2 < d 1 ) d_i=1(d_i<d_{i-1}<...<d_2<d_1) di=1(di<di1<...<d2<d1),即所有记录放在同一组进行直接插入排序,将所有记录排列有序为止。
在这里插入图片描述

/*************************************************Function:shellSort,希尔排序方法Description: 整数序列排序,从小到大Input:    data[]   排序数组n        数组大小delta[]  长度为m且递减有序的增量序列最后一个元素为1m   delta[]数组大小Output:输出转换结果Return: 0
*************************************************/
void shellSort(int data[], int n, int delta[], int m)
{int k, i, dk, j; int temp;for ( i = 0; i < m; i++){dk = delta[i];for (k = dk; k < n; ++k){if (data[k]<data[k-dk]){temp = data[k];for (j = k - dk; j>0&&temp<data[j]; j-=dk){data[j + dk] = data[j];}data[j + dk] = temp;}}}
}

希尔排序的时间复杂度为 O ( N 1.3 ) O(N^{1.3}) O(N1.3).希尔排序是不稳定的排序方法。

3. 快速排序

快速排序

一趟快速排序的过程称为一次划分,具体做法是:附设两个元素位置指示变量 i i i j j j,它们的初值分别指向待排序列的第一个记录和最后一个记录。设枢轴记录(通常是第一个记录)的关键码为 pivot,则首先从j所给位置起向前搜索,找到第一个关键码小于 pivot 的记录时停止,然后从i所给位置起向后搜索,找到第一个关键码大于pivot 的记录时停止,此时交换j所给位置和i所给位置的元素,重复该过程直至i与i相等为止,完成一趟划分。

//用data[low]的值作为枢轴元素pivot进行划分
//不断劈成两半之后排序
int partition(int data[], int low, int high)
{int i, j;int pivot;while (i<j){while (i<j&&data[j]>=pivot){j--;}data[i] = data[j];while (i < j && data[i] <= pivot){i++;}data[j] = data[i];}data[i] = pivot;return i;
}/*************************************************Function:quickSort,快速排序方法Description: 整数序列排序,从小到大Input:    data[]   排序数组low  数组最低位high 数组最高位Output:输出转换结果Return: 0
*************************************************/
void quickSort(int data[], int low, int high)
{if (low < high){int loc = partition(data, low, high);quickSort(data,low,loc-1);quickSort(data,  loc + 1, high);}
}

4. 堆排序

5. 归并排序

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

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

相关文章

Topaz Photo AI for Mac人工智能图像降噪软件 安装教程【保姆级教程,简单操作轻松上手】

Mac分享吧 文章目录 Topaz Photo AI for Mac人工智能图像降噪软件 安装完成&#xff0c;软件打开效果一、Topaz Photo AI 人工智能图像降噪软件 Mac电脑版——v3.3.0⚠️注意事项&#xff1a;1️⃣&#xff1a;下载软件2️⃣&#xff1a;安装软件&#xff0c;根据步骤完成操作…

k8s部署redis远程连接示例

一、环境 节点 IP 服务 master 192.168.126.46 docker、kubeadm、kubelet、kubectl、flannel、telnet node1 192.168.126.47 docker、kubeadm、kubelet、kubectl、flannel、telnet node2 192.168.126.48 docker、kubeadm、kubelet、kubectl、flannel、telnet ubunt…

ubuntu内核更新导致显卡驱动掉的解决办法

方法1&#xff0c;DKMS指定内核版本 用第一个就行 1&#xff0c;借鉴别人博客解决方法 2&#xff0c;借鉴别人博客解决方法 方法2&#xff0c;删除多于内核的方法 系统版本&#xff1a;ubuntu20.24 这个方法是下下策&#xff0c;如果重装驱动还是不行&#xff0c;就删内核在…

Apache Hive分布式容错数据仓库系统

Apache Hive™是一个分布式的、容错的数据仓库系统&#xff0c;它支持大规模的分析&#xff0c;并使用SQL方便地读取、写入和管理驻留在分布式存储中的pb级数据。 Apache Hive Apache Hive是什么 Apache Hive是一个分布式的、容错的数据仓库系统&#xff0c;支持大规模的分析…

运用AI视频拍摄技术生成3D场景:适用于建模、XR及文旅项目Demo制作

利用AI技术从拍摄的视频中生成3D场景&#xff0c;这种创新方法非常适合用于快速构建高质量的3D模型。生成的3D场景不仅能够用于建筑和设计行业的模型展示&#xff0c;还能应用于扩展现实&#xff08;XR&#xff09;技术的大空间体验开发。此外&#xff0c;在文化旅游领域&#…

论文提交步骤 | 2024年第五届MathorCup大数据竞赛

2024年第五届MathorCup数学应用挑战赛—大数据竞赛于2024年10月25日下午6点正式开赛。 论文和承诺书、支撑材料&#xff08;可选&#xff09;及计算结果文档由各参赛队队长电脑登录下方报名主页提交&#xff1a; https://www.saikr.com/vse/bigdata2024 初赛作品提交截止时间为…

11-Dockerfile

11-Dockerfile Dockerfile Dockerfile是用来构建Docker镜像的文本文件&#xff0c;是由一条条构建镜像所需的指令和参数构成的脚本。 构建步骤&#xff1a; 编写Dockerfile文件docker build命令构建镜像docker run依据镜像运行容器实例 构建过程 Dockerfile编写&#xff1a…

如何合并几个pdf文件?值得推荐几个PDF文件的方法

如何合并几个pdf文件&#xff1f;这些PDF文件既是智慧的宝库&#xff0c;也是错综复杂的迷宫&#xff0c;它们如同夜空中散落的繁星&#xff0c;虽然各自闪耀&#xff0c;却因缺乏联系而难以汇聚成照亮前行之路的璀璨星河。当我们急需从这片信息的海洋中捕捞到关键的智慧珍珠时…

rabbitmq高级特性(2)TTL、死信/延迟队列、事务与消息分发

目录 1.TTL 1.1.设置消息过期时间 1.2.设置队列过期时间 2.死信队列 2.1.介绍 2.2.演示 3.延迟队列 3.1.模拟实现延迟队列 3.2.延迟队列插件 4.事务与消息分发 4.1.事务 4.2.消息分发 1.TTL 所谓的ttl&#xff0c;就是过期时间。对于rabbitmq&#xff0c;可以设置…

Java集合常见面试题总结(5)

HashSet 如何检查重复? 当你把对象加入HashSet时&#xff0c;HashSet 会先计算对象的hashcode值来判断对象加入的位置&#xff0c;同时也会与其他加入的对象的 hashcode 值作比较&#xff0c;如果没有相符的 hashcode&#xff0c;HashSet 会假设对象没有重复出现。但是如果发…

二十二、MySQL 8.0 主从复制原理分析与实战

文章目录 一、复制&#xff08;Replication&#xff09;1、什么是复制2、复制的方式3、复制的数据同步类型3.1、异步复制3.2、半同步复制3.3、设计理念&#xff1a;复制状态机——几乎所有的分布式存储都是这么复制数据的 4、基于binlog位点同步的主从复制原理4.1、异步复制示例…

测试管理|如何做好质量管理、提高研发的代码质量?

以下为作者观点&#xff1a; 起因是领导一直在提的一个观点&#xff1a;测试不能只测试系统&#xff0c;重点要放到质量管理上&#xff0c;要管理、监督研发的开发质量。 公司是乙方&#xff0c;接项目过日子&#xff0c;算是外包企业吧。项目时间一般都比较紧张&#xff08;…

QT项目-仿QQ聊天(带宠物系统)

目录 一&#xff0c;项目介绍 二&#xff0c;开发环境 三&#xff0c;涉及技术 四&#xff0c;项目效果示例图 1&#xff0c;登录界面 2&#xff0c;主界面 3&#xff0c;聊天界面 4&#xff0c;功能界面 5&#xff0c;宠物界面 一&#xff0c;项目介绍 这是一个基于u…

vue打包项目通过docker部署nginx服务

一、构建前端代码 npm install nmp run build 确认自己的打包路径&#xff0c;默认是dist&#xff0c;这里也可以修改。 二、将打包的项目使用dockerfile构建 dockerfile 将dist文件复制到nginx的指定的路径&#xff0c;前端界面的路径&#xff0c;还需要两个conf文件 FR…

数据分析与效果评估的有效方法与实践探讨

内容概要 在现代社会中&#xff0c;数据分析与效果评估已成为各类项目管理和决策制定中的重要组成部分。首先&#xff0c;数据分析为我们提供了一种系统化的方法&#xff0c;以深入了解所收集数据的内涵与趋势。通过对数据进行整理、分类和分析&#xff0c;我们能够发现潜在的…

【Kettle的安装与使用】使用Kettle实现mysql和hive的数据传输(使用Kettle将mysql数据导入hive、将hive数据导入mysql)

文章目录 一、安装1、解压2、修改字符集3、启动 二、实战1、将hive数据导入mysql2、将mysql数据导入到hive 一、安装 Kettle的安装包在文章结尾 1、解压 在windows中解压到一个非中文路径下 2、修改字符集 修改 spoon.bat 文件 "-Dfile.encodingUTF-8"3、启动…

2024年NSSCTF秋季招新赛-WEB

The Beginning F12看源码&#xff0c;有flag http标头 黑吗喽 题目说要在发售时的0点0分&#xff0c;所以添加标头data Date: Tue, 20 Aug 2024 00:00:00 GMT然后改浏览器头 User-Agent: BlackMonkey曲奇就是Cookie cookieBlackMonkey这个一般就是Referer Referer:wukon…

【Python单元测试】pytest框架单元测试 配置 命令行操作 测试报告 覆盖率

单元测试&#xff08;unit test&#xff09;&#xff0c;简称UT。本文将介绍在Python项目中&#xff0c;pytest测试框架的安装&#xff0c;配置&#xff0c;执行&#xff0c;测试报告与覆盖率 pytest简介 pytest是一款流行的&#xff0c;简单易上手的单元测试框架&#xff0c;…

python之数据结构与算法(数据结构篇)-- 集合

一、集合的概念 所谓的编程中的”集合“&#xff0c;其实和高中数学中集合是一样的的。比如&#xff1a;羊村和狼堡分别看作两个集合&#xff0c;而狼堡中的"灰太狼"、"红太狼"、"小灰灰"则可看作狼堡中的元素&#xff0c;同理&#xff0c;羊村…

C# 企业微信机器人推送消息 windows服务应用程序的使用

C# 企业微信机器人推送消息 先添加一个机器人! 然后查看机器人就可以得到一个 webhook 特别特别要注意&#xff1a;一定要保护好机器人的webhook地址&#xff0c;避免泄漏&#xff01; 然后开始写代码 &#xff0c;只需要httpPost 调用一下这个地址就可以发送消息了。 首先我…