(搞定)排序数据结构(1)插入排序 选择排序+冒泡排序

news/2024/2/28 9:55:29

目录

本章内容如下  

 一:插入排序              

                1.1插入排序    

              1.2希尔排序    

二:选择排序     

              2.1选择排序

 三:交换排序      

             3.1冒泡排序


一:插入排序                    
 

        1.1直接插入排序
    

        说到排序,其实在我们生活中非常常见,比如当我们需要在网上买东西的时候,  我们可以按照价格排序,也可以按照销量进行排序,所以对于我们来说学习排序这个数据结构是非常重要的,在本文中,我会尽可能按照我的理解将目录中的排序给将清楚。

        

                     下面就是我在一个网购网站中进行截取的图片,我们可以看到排序无处不见。


    
        
        现在让我们进入排序的讲解!!
            
            首先我们讲解的是插入排序
                首先我们来认识一下插入排序这个算法,插入排序顾名思义就是插入到前(n-1)个有序
                数中
,这就像我们生活中经常玩扑克牌的时候的思想,我们玩扑克牌的时候有一种摸牌
                思路就是将第一张牌有序,然后让后面的牌进行插入使得我们的牌一直有序。
                 
                 下面我通过一群数字来进行讲解
                   比如说我们的数组中的值为   9   4    7   2   5   3   1  6   8  
                     这9个数字那么我们如何使得这个数组有序呢?
                     我们通过画图来进行讲解!!

        很明显我们对于插入排序的思想

 思路 :假设我们要插入第n个数,我们需要保证前n-1个数有序,然后再进行插入,没插入一个数我们就要将该数前面的数与要插入的数经行比较,如果大于这个要插入的数那我们就将他玩后面进行移动就可以了。
    
      
        

        

void InsertSort(int* a, int n)
{//使前n-1个数先有序,然后插入第n个数for (int  i = 0; i < n-1; i++){int end = i;int tmp = a[end + 1];//一趟插入排序的思路while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

        
    
            现在让我们来算一下插入排序的时间复杂度,与空间复杂度吧。
                时间复杂度最好:O(N),     最坏:O(n^2)
                首先我们不难发现它的空间复杂度为O(1)
                最坏时间复杂度:O(n^2),当一个数组为逆序的时候,就是插入排序的最坏的
                情况,在这种情况下我们一共有N个数字,插入一个数我们就需要将前面的
                数字全部像后面进行移动一次,然后在插入所以总共来说就是N*N.
                最好的情况是什么呢,最好的情况当然是当数组顺序有序的时候,每一个数
                只要插入就行了,而不需要移动元素,插入的时间复杂度为O(1),所以总共
                的时间复杂度为O(1*N)=O(N).



1.2希尔排序
    


            其实希尔排序的本质也是插入排序,希尔排序只是在插入排序上进行的一个优化的
            排序我们在上面的插入排序中不难发现,当数组有序的时候,我们的插入排序的
            时间复杂度是非常好的为O(N),而我们的希尔大佬就是看到了这个特点,
            所以就在插入排序中进行了优化,才有了我们著名的一个排序算法叫做希尔排序。
      

     希尔排序的思想是什么呢?
                其实希尔排序的思想其实也非常简单 先预排序,在直接插入排序
                1:先对数组进行多组预排序,使得数组中的一些子数组接近有序。
                2:在对数组进行插入排序。
            我们用图来讲解一组预排序

         我们不难看出在进行一组预排序完成后我们的数组相对于原来的数组就接近有序了
         且gap越小的时候我们的数组越接近有序,当gap==1的时候我们的,我们的预排序
         就是直接插入排序
                   代码如下:
                               

//版本一
void ShellSort(int* a, int n)
{int k = 0;int gap = n;while(gap!=1){gap /= 2;//最后一次gap一定等于1//多组预排序,也就是我们图中红黑绿三组进行预排序for (int j = 0; j < gap; j++){//一组预排序操作for (int i = 0; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}}``````c
```版本二:有点像优化的版本
void ShellSort(int* a, int n)
{int k = 0;int gap = n;while(gap!=1){gap=gap/3 +1;//最后一次gap一定等于1    //间距为gap的值从前往后直接进行交换for (int i = 0; i < n - gap; i ++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}



 


         希尔排序的时间复杂度是多少呢?
         其实书上也没有给出明确的证明,有很多种不同的看法,但是差不多是O(N^1.3),这个我也不会证明,需要涉及到高阶的数学。
       大家如果有兴趣的话可以去证明一下。

        到这里我们的插入排序就讲解完毕了,希尔排序需要大家自行的去画图,多思考
        
--------    


二:选择排序
    
        

其实我们的选择排序有两种,一种是直接选择排序,也是我们讲解的排序,还有一种就是堆排序,而堆排序我们之前已经讲解过了,如果你还没看的话建议先直接去补一下。

        堆排序链接:https://blog.csdn.net/2201_75964502/article/details/133017420?spm=1001.2014.3001.5501    

 在这里我们主要讲解选择排序的优化版本,就是我们遍历一边数组,选出两个值
        一个最大值我们往后面插入,还有一个最小值玩前面插入。
        直到我们将数组排序好就可以了。
        思想:遍历一遍选最大值与最小值,然后排序就行了。
        图:这里只写了1个步骤

        代码如下:
            

void SelectSort(int* a, int n)
{int begin = 0;int end = n-1;while (begin < end){int maxi = begin;int mini = begin;for(int i =begin;i<=end;i++){//选最小的下标if (a[mini] > a[i]){mini = i;}//选最大的下标if (a[maxi] < a[i]){maxi = i;}}Swap(&a[begin], &a[mini]);//防止最大值就在begin处if (begin == maxi){maxi = mini;}Swap(&a[maxi], &a[end]);begin++;end--;}
}


    选择排序的时间复杂度:O(^2)
          因为它的时间复杂度算法是一个等差数列:(n)+(n-2)_......+2+0
          每次都需要遍历数组选两个值,固定的        

          所以选择排序是很稳定的。


-------
三:交换排序


        
        其实我们的交换排序也有两种,一种是快速排序,另外一种就是我们本章所讲解的
        冒泡排序,而我们的快速排序由于有几种方法,且有点难,所以我会独自整理成一篇
        文章来进行讲解我们的快速排序。
        
            其实冒泡排序可能是我们见过最多的一种排序,它的思想并不难理解
            冒泡排序的思想是什么呢?
            思想:
                遍历一遍数组,两两相邻的元素进行比较,将数组中最大元素的值给冒到最
                后去,一直遍历,直到数组变成有序的数组

                
                代码如下:
                

        

void BubbleSort(int* a, int n)
{int i = 0;//一共冒泡几趟for (int  i = 0; i < n-1; i++){int exchange = 1;//一趟内部for (int j = 0; j < n-i-1; j++){if (a[j] > a[j + 1]){exchange = 0;Swap(&a[j], &a[j + 1]);}}if (exchange == 1){//说明原数组有序,就不需要进行排序了break;}}}


    冒泡排序的时间复杂度:O(N^2)
    它非常稳定。,因为时间复杂度是固定的

        感谢大家的观看,如果你觉得对你有帮助的话,可以给博主一个赞哦!!
            

    


http://www.ppmy.cn/news/1131450.html

相关文章

c++23中的新功能之十六std::forward_like

一、介绍 前面说过&#xff0c;c标准其实是分成两块推进的。一块是语言标准&#xff0c;另外一块是应用库标准。线程同步还麻烦呢&#xff0c;别说两个组的大佬&#xff0c;不同步的现象肯定会出现。在老的标准里还比较少&#xff0c; 在c11以后经常发现&#xff0c;后续版本会…

安卓修改ROM 修改固件中的一些基本常识 自己做rom注意事项

修改rom 制作rom 解包rom的一些问题解析 安卓系列机型如何内置app 如何选择so文件内置 修改设置里 添加选项 添加文字 修改图标 修改版本号等等 实例解析 最近有几个粉丝对修改rom有兴趣。今天主要给这些友友提供一些自己初学修改rom的一些建议和思路&#xff0c;可以供大家…

最新AI智能创作系统ChatGPT商业源码+详细图文搭建部署教程+AI绘画系统

一、AI系统介绍 SparkAi创作系统是基于国外很火的ChatGPT进行开发的Ai智能问答系统。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧&am…

Android 使用Kotlin封装RecyclerView

文章目录 1.概述2.运行效果图3.代码实现3.1 扩展RecyclerView 3.2 扩展Adapter3.3 RecyclerView装饰绘制3.3.1 以图片实现分割线3.3.2 画网格线3.3.3空白的分割线3.3.4 不同方向上的分割线 3.4 使用方法 1.概述 在一个开源项目上看到了一个Android Kotlin版的RecyclerView封装…

整型提升——(巩固提高——字符截取oneNote笔记详解)

文章目录 前言一、整型提升是什么&#xff1f;二、详细图解1.图解展示 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 整型提升是数据存储的重要题型&#xff0c;也是计算机组成原理的核心知识点。学习c语言进阶的时候,了解内存中数据怎么存&#…

【AI视野·今日NLP 自然语言处理论文速览 第四十二期】Wed, 27 Sep 2023

AI视野今日CS.NLP 自然语言处理论文速览 Wed, 27 Sep 2023 Totally 50 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Attention Satisfies: A Constraint-Satisfaction Lens on Factual Errors of Language Models Authors Mert …

Backblaze发布2023中期SSD故障数据质量报告

作为一家在2021年在美国纳斯达克上市的云端备份公司&#xff0c;Backblaze一直保持着对外定期发布HDD和SSD的故障率稳定性质量报告&#xff0c;给大家提供了一份真实应用场景下的稳定性分析参考数据。 本文我们主要看下Backblaze最新发布的2023中期SSD相关故障稳定性数据报告。…

安防监控/视频汇聚平台EasyCVR云端录像不展示是什么原因?该如何解决?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。音视频流媒体视频平台EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、…

高数:第二章:一元函数微分学

文章目录 一、导数与微分1.导数的概念(1)导数的定义(2)左右导数(3)定理&#xff1a;可导与左右导数的关系(4)可导三要素(5)用导数定义判断可导性 2.微分的概念(1)微分的定义(2)微分与可导的关系 3.导数与微分的几何意义(1)导数 f ′ ( x 0 ) f(x_0) f′(x0​)的几何意义&#x…

基于PYQT5的GUI开发系列教程【二】QT五个布局的介绍与运用

目录 本文概述 作者介绍 创建主窗口 水平布局 垂直布局 栅格布局 分裂器水平布局 分裂器垂直布局 自由布局 取消原先控件的布局的方法 尾言 本文概述 PYQT5是一个基于python的可视化GUI开发框架&#xff0c;具有容易上手&#xff0c;界面美观&#xff0c;多平台…

数据结构——堆(C语言)

本篇会解决一下几个问题&#xff1a; 1.堆是什么&#xff1f; 2.如何形成一个堆&#xff1f; 3.堆的应用场景 堆是什么&#xff1f; 堆总是一颗完全二叉树堆的某个节点总是不大于或不小于父亲节点 如图&#xff0c;在小堆中&#xff0c;父亲节点总是小于孩子节点的。 如图&a…

Docker和Docker compose的安装使用指南

一&#xff0c;环境准备 Docker运行需要依赖jdk&#xff0c;所以需要先安装一下jdk yum install -y java-1.8.0-openjdk.x86_64 二&#xff0c;Docker安装和验证 1&#xff0c;安装依赖工具 yum install -y yum-utils 2&#xff0c;设置远程仓库 yum-config-manager --add-r…

2023-9-30 JZ34 二叉树中和为某一值的路径

题目链接&#xff1a;二叉树中和为某一值的路径 import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、…

定义现代化实时数据仓库,SelectDB 全新产品形态全面发布

导读&#xff1a;9 月 25 日&#xff0c;2023 飞轮科技产品发布会在线上正式召开&#xff0c;本次产品发布会以 “新内核、新图景” 为主题&#xff0c;飞轮科技 CEO 马如悦全面解析了现代化数据仓库的演进趋势&#xff0c;宣布立足于多云之上的 SelectDB Cloud 云服务全面开放…

设置小数点后2位,随机保存财富txt,生成随机富翁数

如果想要将生成的随机财富数据保留小数点后两位&#xff0c;可以在写入文件之前使用格式化字符串的方法来控制小数点的位数。以下是修改后的代码示例&#xff1a; import random# 生成随机财富数据 total_people 100 average_wealth 200 * 10**8 # 平均财富 200亿# 5个人的…

Mendix中的依赖管理:npm和Maven的应用

序言 在传统java开发项目中&#xff0c;我们可以利用maven来管理jar包依赖&#xff0c;但在mendix项目开发Custom Java Action时&#xff0c;由于目录结构有一些差异&#xff0c;我们需要自行配置。同样的&#xff0c;在mendix项目开发Custom JavaScript Action时&#xff0c;…

宝塔反代openai官方API接口详细教程,502 Bad Gateway问题解决

一、前言 宝塔反代openai官方API接口详细教程&#xff0c;实现国内使用ChatGPT502 Bad Gateway问题解决&#xff0c; 此方法最简单快捷&#xff0c;没有复杂步骤&#xff0c;不容易出错&#xff0c;即最简单&#xff0c;零代码、零部署的方法。 二、实现前提 一台海外VPS服务…

我们是否真的需要k8s?

文章目录 背景k8s相关的讨论为什么要用k8sk8s带来了什么当前业务使用到k8s的核心优势了吗直接自己买服务器会不会更便宜&#xff1f;其他QA没有人可以说出来为什么一定要用k8s而不是其他的没有人可以解释为什么成本核算困难以及成本这么高的原因没有人给出面向C端&#xff0c;面…

Source Insight 工具栏图标功能介绍

这篇文章并不介绍 Source Insight 的具体使用方法&#xff0c;这类教程网上有很多&#xff0c;这里只分析 Souce Insight 工具栏图标的功能。 文章目录 Source Insight 简介Souce Insight 工具栏文件操作新建&#xff08;CtrlN&#xff09;打开&#xff08;CtrlO&#xff09;保…

【网络安全】网络安全之信息收集和信息收集工具讲解,告诉你黑客是如何信息收集的

一&#xff0c;域名信息收集 1-1 域名信息查询 可以用一些在线网站进行收集&#xff0c;比如站长之家 域名Whois查询 - 站长之家站长之家-站长工具提供whois查询工具&#xff0c;汉化版的域名whois查询工具。https://whois.chinaz.com/ 可以查看一下有没有有用的信息&#xf…
最新文章