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

C语言:排序(1)

目录

一、排序的概念及应用

排序的概念

排序的运用

 二、常见排序算法

插入排序

基本思想

直接插入排序

希尔排序( 缩小增量排序 )

选择排序

基本思想

堆排序


一、排序的概念及应用

排序的概念

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

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

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

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

排序的运用

     类似于淘宝、京东这种商品排列就是用到了排序算法。

 二、常见排序算法

插入排序

基本思想

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

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

 

直接插入排序

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

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

1. 元素集合越接近有序,直接插入排序算法的时间效率越高

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

3. 空间复杂度:O(1),它是一种稳定的排序算法

4. 稳定性:稳定  

希尔排序( 缩小增量排序 )

    希尔排序法又称缩小增量法,希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个 组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工 作。当到达=1时,所有记录在统一组内排好序。

希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就 会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的 希尔排序的时间复杂度都不固定

4. 稳定性:不稳定

选择排序

基本思想

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

直接选择排序

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素

若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换

在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

 直接选择排序的特性总结:

1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用

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

3. 空间复杂度:O(1)

4. 稳定性:不稳定

堆排序

    堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种,它是 通过堆来进行选择数据,需要注意的是排升序要建大堆,排降序建小堆。

 直接选择排序的特性总结:

1. 堆排序使用堆来选数,效率就高了很多。

2. 时间复杂度:O(N*logN)

3. 空间复杂度:O(1)

4. 稳定性:不稳定


       本篇内容就先到这里,后续会继续写关于排序的内容,希望对各位有帮助,如果有错欢迎指出。


http://www.kler.cn/news/329614.html

相关文章:

  • 毕业设计选题:基于ssm+vue+uniapp的家庭记账本小程序
  • 在线远程考试|基于springBoot的在线远程考试系统设计与实现(附项目源码+论文+数据库)
  • 【C++】“list”的介绍和常用接口的模拟实现
  • 进程通信——内存映射
  • Java项目实战II基于Java+Spring Boot+MySQL的智能物流管理系统(文档+源码+数据库)
  • [大语言模型-论文精读] 阿里巴巴-通过多阶段对比学习实现通用文本嵌入
  • 从0开始实现es6 promise类
  • 【可答疑】基于51单片机的体温心率血氧检测系统(含仿真、代码、报告等)
  • I2C-Tools的安装与使用方法(详解,一篇教会你熟练使用)
  • 数据库索引和磁盘的关系大揭秘
  • Leetcode 3307. Find the K-th Character in String Game II
  • 无线通信系统仿真与原型设计:MATLAB实践指南
  • LDRA Testbed(TBrun)软件集成测试(部件测试)_操作指南
  • postgresql僵尸进程的处理思路
  • 一文带你入门客制化键盘,打造专属打字利器
  • 大数据常问八股文面试题【数据倾斜,现象、本质原因、解决方案】
  • OpenCV视频I/O(3)视频采集类VideoCapture之获取当前使用的视频捕获 API 后端的名称函数getBackendName()的使用
  • 【含文档】基于Springboot+微信小程序 的中心医院用户移动端(含源码+数据库+lw)
  • vim(1) -- 环境配置
  • 电脑usb接口封禁如何实现?5种禁用USB接口的方法分享!(第一种你GET了吗?)
  • PLMN NR cell
  • Nature Machine Intelligence 基于强化学习的扑翼无人机机翼应变飞行控制
  • 网盘能否作为FTP替代产品?企业该如何进行FTP国产化替代?
  • 深度优先搜索算法改进:分类与打印有向图中的每条边
  • 【Canvas与艺术】六鱼六燕铁艺壁画
  • 微服务 OpenFeign 解析部署使用全流程
  • PHP include和require的区别
  • TiDB 6.0 Book Rush | TiDB 和 Python 的 CRUD 应用开发实践
  • 使用ESP8266扫描WiFi列表
  • H.264编解码工具 - Intel Quick Sync Video