排序1——C语言

排序

  • 1. 复杂度
  • 2. 插入排序
    • 2.1 直接插入排序
    • 2.2 希尔排序
  • 3. 选择排序
    • 3.1 直接选择排序
    • 3.2 堆排序

排序在生活中很常见,比如在网购时,按价格排序,按好评数排序,点餐时,按评分排序等等。而排序有快和慢,快的排序效率高,慢的排序效率低,需要的时间也多。下面就一一介绍各种排序。介绍排序算法时,统一以 升序为例。

1. 复杂度

当一个算法编写完成后,运行时需要消耗时间和空间资源。因此,衡量一个算法的好坏,需要从时间和空间两个维度来衡量,即时间复杂度和空间复杂度。

时间复杂度是衡量快慢的,空间复杂度是衡量该算法运行所需的额外空间。现如今,计算机的内存空间已经很大了,因此空间复杂度已经不是特别关注了。

时间复杂度是一个函数,一个算法的基本操作的执行次数就是该算法的时间复杂度。

void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}
}

比如这段代码主要执行的是++count语句,计算该语句的执行次数。

可以看到,++count外套了两层循环,外循环每执行一次,内循环执行N次,而外循环执行了N次,因此++count语句执行了N^2次。算法的执行次数最多的语句一般在循环内部。因此计算时间复杂度,首要计算的就是循环内的。而这个函数可能是若干多项式的和,我们不可能把这个算法的时间复杂度算的非常清楚,只需要知道大概就可以了。因此时间复杂度采用大O渐进表示法

大O渐进表示法:
1.在这个运行次数的函数中,只保留最高阶的那一项,比如10N^2+2N+2---->10N^2
2.如果最高阶存在并且不是1,那么将该项的系数化为1,比如10N^2 —>N^2

最终我们就得到了一个很简单的函数。此外,有些算法的时间复杂度在不同情况下会有不同,因此需要计算最坏情况和最好情况,有些排序算法就存在这种情况。

空间复杂度也是一个函数,是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。空间复杂度计算的是额外使用的空间的大小,不包括本身对变量开辟的空间。

复杂度主要有以下几种
在这里插入图片描述

其中含有对数的主要是以2为底数的。

2. 插入排序

2.1 直接插入排序

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

什么意思呢?我们举一个例子,比如将排序5,9,7,6,2
排序过程如下。
在这里插入图片描述
当数组遍历完,得到的就是有序的数组了。

void InsertSort(int* array, int numsArr)//待排序数组和数组大小
{//插入numsArr-1次for (int i = 0; i < numsArr - 1; i++){int end = i;int tmp = array[end + 1];while (end >= 0){//后移if (array[end] > tmp){array[end + 1] = array[end];--end;}else{break;}}array[end + 1] = tmp;}
}

直接插入排序的时间复杂度分最好情况和最坏情况,最好情况是数组本就有序,不需要插入,但是需要遍历一遍数组,所以时间复杂度为O(N);最坏情况是数组逆序,插入的次数是1,2,3,4…N-3,N-2,N-1次,数据是一个等差数列,计算出来为**(N^2-N)/2** 根据大O渐进表示法最终化简为O(N^2);

结论:最坏情况O(N^2)最好情况O(N)
空间复杂度O(1),表示没有用到额外空间。

2.2 希尔排序

希尔排序又称为缩小增量排序,希尔排序对直接插入排序进行了优化,先进行若干次预排序,在进行一次直接插入排序,预排的作用是使得所有记录更快的接近有序。

基本思想是:先选定一个整数(假设为K),把待排序的所有记录分成K个
,所有距离为K的记录分在同一组内,并对每一组内的记录进行插入排序。然后缩小K的值,重复上述分组和排序的工作。当K=1时,所有记录在一组内排好序。

这里举例将10,9,8,7,6,5,4,3,2,1进行第一轮的排序,假设K=3;
排序过程如图
在这里插入图片描述
可以看到,第一轮的排序结果,已经很接近有序了,缩小K的值,在进行分组和排序,当K=1时,所有数据为一组,此时进行的就是直接插入排序。

将数据分组进行预排,可以将更小的数据更快的插入到前面更大的数据更快的移到后面,减少了插入和移动的次数。

整数的选择也是一个问题,太小了会导致预排效果不明显,太大了会导致预排次数变多,因此整数的每次选取方式为缩小三倍在加1,加1会使得最后一次这个整数一定为1。即最后一次的排序一定是直接插入排序。

代码如下

void ShellSort(int* array, int numsArr)
{int gap = numsArr;while (gap > 1){//间隔gap的数据作为一组,一共gap组//gap=1时是直接插入排序gap = gap / 3 + 1;    for (int i = 0; i < numsArr - gap; i++){int end = i;int tmp = array[end + gap];while (end >= 0){//往后挪数据if (array[end] > tmp){array[end + gap] = array[end];end -= gap;}else{break;}}array[end + gap] = tmp;}}
}

希尔排序的时间复杂度比较难算,因为预排和gap的选择会影响结果,并且每一次的预排都会对下一次的预排产生影响。这里直接说结论,希尔排序的时间复杂度大约为N^1.3。

3. 选择排序

3.1 直接选择排序

思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(或末尾)位置,直到全部待排序的数据元素排完 。

这里进行一个小的优化,同时选出最大和最小的元素,分别放到末尾和起始位置。

但也会产生一个小问题,我们先看代码。

void SelectSort(int* array, int numsArr)
{int begin = 0, end = numsArr - 1;while (begin < end){//最大最小值的下标int minIndex = begin, maxIndex = begin;for (int i = begin + 1; i <= end; i++){//找最小值并更新下标if (array[i] < array[minIndex]){minIndex = i;}//找最大值并更新下标if (array[i] > array[maxIndex]){maxIndex = i;}}swap(&array[begin], &array[minIndex]);//最大值和起始位置重复了if (maxIndex == begin)maxIndex = minIndex;swap(&array[end], &array[maxIndex]);begin++;end--;}
}

问题是会产生数据重复,看下面这组数据。
9,2,3,4,5,6,8,1
如果没有这两条语句会产生什么情况。

if (maxIndex == begin)
maxIndex = minIndex;

在这里插入图片描述
当最大值的下标和起始位置的下标重复,就会产生上面的情况,解决办法就是加上判断语句。

时间复杂度:O(N^2)
空间复杂度:O(1)

3.2 堆排序

关于堆排序在之前已经介绍过了,这里就不在赘述了,大家可以看这篇进行了解:堆的应用
代码如下

void HeapSort(int* array, int numsArr)
{//向下调整建堆,复杂度O(N)for (int i = (numsArr - 2) / 2; i >= 0; i--){AdJustDown(array, numsArr, i);}//升序建大堆;降序建小堆//复杂度O(N*logN)int i = numsArr - 1;while (i > 0){swap(&array[0], &array[i]);//交换首尾元素AdJustDown(array, i, 0);i--;}
}
void AdJustDown(int* array, int num_array, int parent)//建大堆
{//假设左孩子符合条件int child = parent * 2 + 1;while (child < num_array){//存在右孩子且右孩子符合条件if (child + 1 < num_array && array[child + 1] > array[child]){++child;}if (array[child] > array[parent]){//交换数据swap(&array[child], &array[parent]);//更新下标parent = child;child = parent * 2 + 1;}else{break;}}
}

这里对堆排序的时间复杂度进行一个计算。
如下图,这是建堆的时间复杂度

在这里插入图片描述
根据大O渐进表示法,最终建堆的时间复杂度为O(N)

而进行排序时,时间复杂度为
在这里插入图片描述
建堆的时间复杂度为O(N),排序的时间复杂度为O(NlogN),最大项为NlogN,因此堆排序的时间复杂度为O(N*logN)

关于其他排序,后续会依次介绍。

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

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

相关文章

【排序 贪心】3107. 使数组中位数等于 K 的最少操作数

算法可以发掘本质&#xff0c;如&#xff1a; 一&#xff0c;若干师傅和徒弟互有好感&#xff0c;有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二&#xff0c;有无限多1X2和2X1的骨牌&#xff0c;某个棋盘若干格子坏了&#xff0c;如何在没有坏…

C语言中抽象的编译和链接原理

今天04.12&#xff0c;身体小有不适&#xff0c;但是睡不着觉&#xff0c;秉着不能浪费时间的原则&#xff0c;现在就简单写一下有关我们C语言中编译和链接的大体过程吧&#xff0c;因为编译和链接是比较抽象的&#xff0c;而且内容是比较底层&#xff0c;我们这里就简单了解它…

Chatgpt掘金之旅—有爱AI商业实战篇|SEO 咨询业务|(十七)

演示站点&#xff1a; https://ai.uaai.cn 对话模块 官方论坛&#xff1a; www.jingyuai.com 京娱AI 一、AI技术创业在SEO 咨询业务有哪些机会&#xff1f; 人工智能&#xff08;AI&#xff09;技术作为当今科技创新的前沿领域&#xff0c;为创业者提供了广阔的机会和挑战。随…

策略模式(知识点)——设计模式学习笔记

文章目录 0 概念1 使用场景2 优缺点2.1 优点2.2 缺点 3 实现方式4 和其他模式的区别5 具体例子实现5.1 实现代码 0 概念 定义&#xff1a;定义一个算法族&#xff0c;并分别封装起来。策略让算法的变化独立于它的客户&#xff08;这样就可在不修改上下文代码或其他策略的情况下…

蓝桥杯 每天2题 day6

碎碎念&#xff1a;哇咔咔 要不是中间缺勤一天就圆满day7了&#xff01;最后一晚上&#xff01;写题复习哇咔咔 唉&#xff0c;睡了一觉就看不下去了&#xff0c;&#xff0c;&#xff0c;看看之前的笔记洗洗睡觉&#xff0c;&#xff0c;&#xff0c; 记得打印准考证带好东西…

Java面试篇9——并发编程

并发编程知识梳理 提示&#xff0c;此仅为面试&#xff0c;若想对线程有跟完整了解&#xff0c;请点击这里 提示&#xff1a;直接翻到最后面看面试真题&#xff0c;上面的为详解 面试考点 文档说明 在文档中对所有的面试题都进行了难易程度和出现频率的等级说明 星数越多代表…

LeetCode34:在排序数组中查找元素的第一个和最后一个位置(Java)

目录 题目&#xff1a; 题解&#xff1a; 方法一&#xff1a; 方法二&#xff1a; 题目&#xff1a; 给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&…

3D场景编辑方法——CustomNeRF

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 摘要Abstract文献阅读&#xff1a;3D场景编辑方法——CustomNeRF1、研究背景2、提出方法3、CustomNeRF3.1、整体框架步骤3.2、对特定问题的解决 4、实验结果5、总结…

一辆汽车的节拍时间是怎样的?

节拍时间&#xff0c;又称 takt time&#xff0c;是德语中“节奏”的意思。在汽车制造业中&#xff0c;它指的是按照客户需求和生产计划&#xff0c;生产一辆汽车所需的时间。这个时间是固定的&#xff0c;它决定了生产线上每个工序的操作速度和节奏&#xff0c;是生产线上所有…

配置交换机 SSH 管理和端口安全

实验1:配置交换机基本安全和 SSH管理 1、实验目的 通过本实验可以掌握&#xff1a; 交换机基本安全配置。SSH 的工作原理和 SSH服务端和客户端的配置。 2、实验拓扑 交换机基本安全和 SSH管理实验拓扑如图所示。 3、实验步骤 &#xff08;1&#xff09;配置交换机S1 Swit…

liunx系统发布.net core项目

liunx系统发布.net core项目 准备.net6程序运行环境部署nginx&#xff0c;通过一个地址既能访问web api&#xff0c;又能访问web项目有一个客户把web api放到docker中&#xff0c;想通过nginx转发&#xff0c;nginx也支持配置多个程序api接口的其它 liunx系统&#xff1a;cento…

SQL执行流程图文分析:从连接到执行的全貌

SQL执行总流程 下面就是 MySQL 执行一条 SQL 查询语句的流程&#xff0c;也从图中可以看到 MySQL 内部架构里的各个功能模块。 MySQL 的架构共分为两层&#xff1a;Server 层和存储引擎层&#xff0c; Server 层负责建立连接、分析和执行 SQL。MySQL 大多数的核心功能模块都在…

STM32利用软件I2C通讯读MPU6050的ID号

今天的读ID号是建立在上篇文章中有了底层的I2C通讯的6个基本时序来编写的。首先需要完成的就是MPU6050的初始化函数 然后就是编写 指定地址写函数&#xff1a; 一&#xff1a;开始 二&#xff1a;发送 从机地址读写位&#xff08;1&#xff1a;读 0&#xff1…

Eureka-搭建Eureka步骤

简介&#xff1a; Eureka是Netflix开发的服务发现框架&#xff0c;本身是一个基于REST的服务&#xff0c;主要用于定位运行在AWS域中的中间层服务&#xff0c;以达到负载均衡和中间层服务故障转移的目的。SpringCloud将它集成在其子项目spring-cloud-netflix中&#xff0c;以实…

ReactRouter

React-Router 概念&#xff1a;一个路劲path对应一个组件component 当我们在浏览器中访问一个path的时候&#xff0c;path对应的组件会在页面中进行渲染路由语法&#xff1a; import {createBrowserRouter, RouterProvider} from react-router-dom// 1. 创建router实例对象并…

ArcGIS Desktop使用入门(三)图层右键工具——标注要素、将标注转换为注记

系列文章目录 ArcGIS Desktop使用入门&#xff08;一&#xff09;软件初认识 ArcGIS Desktop使用入门&#xff08;二&#xff09;常用工具条——标准工具 ArcGIS Desktop使用入门&#xff08;二&#xff09;常用工具条——编辑器 ArcGIS Desktop使用入门&#xff08;二&#x…

解决vue3更新chunk包后,点击页面报错

出现错误 解决思路 试了好多方法&#xff0c;跳了很多坑&#xff0c;router版本对不上&#xff0c;解决方案不实用。最后我直接捕获异常&#xff0c;刷新页面&#xff0c;解决最快最有效。 // vue-rotuer版本 "vue-router": "^4.0.3"解决方案 在router/…

数模 初见数建

文章目录 初见数学建模1.1 数学建模是什么1.2 数学建模的概述1.3 如何学习数学建模---分模块化1.4 数学建模前提了解1.5 数学建模的六个步骤1.6 如何备战建模比赛1.7 数学建模赛题类型1.8 数学建模算法体系概述 初见数学建模 1.1 数学建模是什么 1.原型与模型 原型&#xff…

5G Frequency Bands 频率分布

连接&#xff1a;https://www.5g-networks.net/5g-technology/5g-frequency-bands/

【Canvas与艺术】绘制黄色三角生化危险标志

【关键点】 系统函数arcTo函数的用法及自编函数createRegTriArr的灵活运用。 【成果图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head>&…