【数据结构】排序(上)

在这里插入图片描述
个人主页~

堆排序看这篇~
还有这篇~


排序

  • 一、排序的概念及应用
    • 1、概念
    • 2、常见的排序算法
  • 二、常见排序的实现
    • 1、直接插入排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 2、希尔排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 3、选择排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 4、堆排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 5、冒泡排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 6、快速排序
      • (1)基本思想
      • (2)代码实现
        • ①hoare版本
        • ②挖坑法版本
        • ③前后指针版本
      • (3)时间复杂度
      • (4)空间复杂度

一、排序的概念及应用

1、概念

排序就是按照某一关键字递增和递减排列起来的操作
排序在生活中非常常用,成绩、排行等等一切跟数字字母等有关的都能够排序

2、常见的排序算法

常见的排序算法有
插入排序:直接插入排序,希尔排序
选择排序:选择排序,堆排序
交换排序:冒泡排序、快速排序
归并排序:归并排序

二、常见排序的实现

1、直接插入排序

(1)基本思想

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

(2)代码实现

//我们看做一个一个插入
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){//从0到end都有序,tmp插入排序int end = i - 1;//end存储插入前的最后一个元素的下标,也就是第i-1个数据int tmp = a[i];//tmp是插入的数据,也就是第i个数据while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}//如果前边比后边大,就交换并且--end,继续向前比较else{break;//直到后边比前边大}}a[end + 1] = tmp;//将此时end+1下标的位置赋值tmp,后边的数据全都往后移了一位}
}

封装一个打印数组的函数

void ArrPrint(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}

在这里插入图片描述

(3)时间复杂度

如果按照最坏的情况:
第一次排不需要比较
第二次需要比较一次
第三次需要比较两次

第N次需要比较N-1次
F(N)=0+1+2+3+…+N-1 = (N-1)*(N)/2
所以直接插入排序的最坏时间复杂度为O(N^2)
最好时间复杂度就是有序数组O(N)
所以直接插入排序是介于它们之间的,这才有了希尔排序这种优化算法,降低了时间复杂度

(4)空间复杂度

没有占用额外空间,O(1)

2、希尔排序

(1)基本思想

希尔排序可以说是高级的直接插入排序,它是希尔通过观察和实践在直接插入排序的基础上进行算法优化,将时间复杂度降低
希尔排序分为两步:
第一步:预排序,是将无序的数组排序至接近有序
第二步:直接插入排序
当gap越小越接近有序,gap越大预排序的速度会更快
当gap为1时,就是直接插入排序
简单来说希尔排序就是粗排后细排

(2)代码实现

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//分为三组,最后加一可以保证最后一次的while循环gap等于1,相当于直接插入排序for (int i = 0; i < n - gap; i++){int end = i;
//每组的最后一个数字(这里的最后一个是指一个一个往里面插的最后一个数字,并不是真正的最后一个数字)int tmp = a[end + gap];//记录待插入数字while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}elsebreak;}//同直接插入排序,差别是分了组,每次要对比的数字的下标差了gapa[end + gap] = tmp;}}
}

在这里插入图片描述

(3)时间复杂度

希尔排序的时间复杂度并不好计算,因为gap的取值很多,我们没办法通过简单的计算来得出结果,这是一个数学上的难以解答的问题,资料中显示,它的时间复杂度在O(n^1.25)到O(1.6*n ^1.25)之间,我们粗略表示成O(n ^1.3)

(4)空间复杂度

没有占用额外空间,O(1)

3、选择排序

(1)基本思想

遍历数组,每一次将最大和最小的数据挑出来放到数列的起始和末尾位置,知道所有元素全部排完
这是一种超级慢的排序方式,实际使用中很少用

(2)代码实现

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;}void SelectSort(int* a, int n)
{int right= n - 1;//定位到数组最后一个元素下标int left = 0;//定位到数组第一个元素下标while (left < right){int min = left;//先将left作为最开始的最小值int max = right;//先将right作为最开始的最大值for (int i = left; i <= right; i++){if (a[i] < a[min])min = i;if (a[i] > a[max])max = i;}//在left和right之间选出最大和最小的数Swap(&a[left], &a[min]);//交换a[left]与a[min]if (left == max)max = min;//这里注意,当最大值与left重叠时,将位置修正再交换Swap(&a[right], &a[max]);left++;right--;}
}

在这里插入图片描述

(3)时间复杂度

它的时间复杂度就是等差数列求和,可以很容易的看出来它的时间复杂度为O(N^2)

(4)空间复杂度

没有占用额外空间,O(1)

4、堆排序

在之前的文章中有详细的解释,我们可以来到二叉树-堆文章中来详细了解

(1)基本思想

利用堆的特性,即小堆堆顶最小,大堆堆顶最大的性质,来进行升序或降序排序

(2)代码实现

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void AdjustDown(int* a, int n,int parent)
{int child = parent * 2 + 1;while(child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}//调出值较大的那个孩子if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}//交换后让孩子当爹,使其跟它的孩子比较elsebreak;}
}void HeapSort(int* a, int n)
{//parent = (child-1) / 2,i的初始值是最后一个元素的父节点for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//调整出一个大堆int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//交换首尾元素AdjustDown(a, end, 0);end--;}
//每次调整都会将最大的一个数放在当前调整范围的最后一个位置,而调整范围的最后一个位置每次都会向前一个,直到成为升序数组
}

在这里插入图片描述

(3)时间复杂度

在前面链接中的文章中我们计算过它的时间复杂度,O(N*log₂N)

(4)空间复杂度

没有额外申请空间,O(1)

5、冒泡排序

(1)基本思想

冒泡排序是我们初识C语言时的接触到的第一个排序方式,也可以说是最鸡肋的排序方式,简单易懂但效率很低,就是两两元素相互比较,大的往后移动,遍历一遍下来最大的就到最后了,以此类推实现排序
这里我就不过多解释了

(2)代码实现

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}

(3)时间复杂度

相当于等差数组求和,n-1 + n-2 + … + 1
F(N) = (N-1+1)/2 * N/2
时间复杂度为O(N^2)

(4)空间复杂度

没有占用额外空间,空间复杂度为O(1)

6、快速排序

(1)基本思想

任取待排序序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素小于基准值,右子序列中所有元素大于基准值,然后在左右子序列中重复该过程,直到排序完成
这里我们每一次取的基准值都是左数第一个元素

(2)代码实现

①hoare版本
int PartSort1(int* a, int left, int right)
{int keyi = left;//将最左边的元素作为关键元素,即基准值,记录它的下标while (left < right){while (left < right && a[keyi] <= a[right]){right--;}while (left < right && a[keyi] >= a[left]){left++;}Swap(&a[left], &a[right]);
//左右两边向中间逼近,在右边找到小于基准值的数字,在左边找到大于基准值的数字,两者交换}Swap(&a[keyi], &a[left]);//循环出来之后,说明left与right相遇了,也就是说此时的这个位置左边的数字全部比基准值小,右边的数字都比基准值大,将这个位置的数字与基准值位置的数字交换位置return left;//将此时的基准值返回
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort1(a, left, right);//将区间分成三个部分:keyi,keyi左,keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//对剩下的区间继续排序
}

在这里插入图片描述
在这里插入图片描述

②挖坑法版本
int PartSort2(int* a, int left, int right)
{int key = a[left];//存下坑里的数字int hole = left;//把最左边的位置作为坑while (left < right){while (left < right && a[right] >= key)right--;//找到a[right] < key的位置跳出循环a[hole] = a[right];hole = right;//把这个位置挖新坑,将坑里的值存起来while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;//右边挖完左边挖,左边找大于基准值的}a[hole] = key;//将最开始存下来的基准值填到此时剩下的坑里return hole;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort2(a, left, right);//将区间分成三个部分:keyi,keyi左,keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//对剩下的区间继续排序
}

在这里插入图片描述
在这里插入图片描述

③前后指针版本
int PartSort3(int* a, int left, int right)
{int prev = left;//初始前指针为最左边的元素int cur = left + 1;//初始后指针为前指针的后一个元素int keyi = left;//存下前指针的下标作为基准值下标while (cur <= right){while (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);
//如果后指针指向的数字大小小于基准值,并且前指针的后一个指针不为后指针,那么前后指针指向位置的值交换
//当后指针指向的值小于基准值时,前指针都会往后走(这里的知识涉及到逻辑语句的短路)cur++;//后指针往后走}Swap(&a[prev], &a[keyi]);keyi = prev;//最后前指针所指向元素的大小一定大于基准值,将他们交换,此时的基准值左边除了第一个都比它小,右边都比它大return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort3(a, left, right);//将区间分成三个部分:keyi,keyi左,keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//对剩下的区间继续排序
}

在这里插入图片描述

在这里插入图片描述

(3)时间复杂度

快速排序是一种类二叉树类型的排序,所以它的时间复杂度为O(N*log₂N),计算方法同二叉树

(4)空间复杂度

递归创建类二叉树,空间复杂度为O(log₂N)


下期再见~
在这里插入图片描述

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

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

相关文章

基于小波样条框架的一维时间序列信号降噪方法(MATLAB R2018A)

1952年&#xff0c;DUFFIN在研究非调和Fourier级数时引入了Hilbert空间中框架的概念&#xff0c;然而并没有引起很大的反响。1986年&#xff0c;DAUBECHIES研究发现利用框架可以将L2(R)中的函数展开成类似标准正交基的级数&#xff0c;并且用框架研究函数时所需的条件要比用标准…

Vue 2看这篇就够了

Vue 2 技术文档 Vue.js 是一款用于构建用户界面的渐进式框架。与其他重量级框架不同的是&#xff0c;Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层&#xff0c;不仅易于上手&#xff0c;还便于与第三方库或既有项目整合。而 Vue.js 2&#xff08;以下简称 Vue…

北航第五次数据结构与程序设计编程题复习

北航第五次数据结构与程序设计编程题复习 树叶节点遍历&#xff08;树-基础题&#xff09;计算器&#xff08;表达式计算-表达式树实现&#xff09;服务优化词频统计&#xff08;树实现&#xff09; 树叶节点遍历&#xff08;树-基础题&#xff09; 【问题描述】 从标准输入中…

React的useState的基础使用

import {useState} from react // 1.调用useState添加状态变量 // count 是新增的状态变量 // setCount 修改状态变量的方法 // 2.添加点击事件回调 // userState实现计数实例import {useState} from react// 使用组件 function App() {// 1.调用useState添加状态变量// coun…

Qt——升级系列(Level Four):控件概述、QWidget 核心属性、按钮类控件

目录 控件概述 QWidget 核心属性 核心属性概览 enabled geometry windowTitle windowIcon windowOpacity cursor font toolTip focusPolicy styleSheet 按钮类控件 Push Button Radio Buttion Check Box Tool Button 控件概述 Widget 是 Qt 中的核⼼概念. 英⽂原义是 "…

运维一个宝塔面板的php项目的艰辛历程【解决了http3,ssl,quic】

在这个项目的环境 使用了宝塔面板 有4个php:php5.6,php7.3,php7.4,php8.0 nignx为1.20版本 升级计划&#xff1a; 升级nginx1.26.0版本&#xff0c;添加上http3协议&#xff0c;添加ssl证书 遇到的问题&#xff1a; 升级nginx1.26版本后 无法打开php5.6的后台 原因&#xff…

PromptPort:为大模型定制的创意AI提示词工具库

PromptPort&#xff1a;为大模型定制的创意AI提示词工具库 随着人工智能技术的飞速发展&#xff0c;大模型在各行各业的应用越来越广泛。而在与大模型交互的过程中&#xff0c;如何提供精准、有效的提示词成为了关键。今天&#xff0c;就为大家介绍一款专为大模型定制的创意AI…

Llama模型家族之Stanford NLP ReFT源代码探索 (二)Intervention Layers层

LlaMA 3 系列博客 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;一&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;二&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;三&#xff09; 基于 LlaMA…

QT error: allocation of incomplete type ‘Ui::Server‘

目录 前言 报错内容&#xff1a; 过程解析&#xff1a; 原因分析&#xff1a; daisy.skye的博客 QT合集http://t.csdnimg.cn/wEVbu 前言 最近又开始需要做上位机了&#xff0c;要知道qt上位机对我来说已经3年没有接触了&#xff0c;最开始接触还是毕业时工作中的简单学习和…

数据结构 -- 树状数组

前言 树状数组或二叉索引树&#xff08;Binary Indexed Tree&#xff09;&#xff0c;又以其发明者命名为 Fenwick 树。其初衷是解决数据压缩里的累积频率的计算问题&#xff0c;现多用于高效计算数列的前缀和、区间和。它可以以 O(logn) 的时间得到任意前缀和。并同时支持在 …

计算机毕业设计python+spark知识图谱音乐推荐系统 音乐数据分析可视化大屏 音乐爬虫 LSTM情感分析 大数据毕设 深度学习 机器学习

流程&#xff1a; 1.Python采集网易云音乐歌手、歌词、音乐、评论等约10-20万海量数据&#xff0c;存入mysql数据库&#xff1b; 2.使用pandasnumpy/MapReduce对mysql中四类数据进行数据清洗&#xff0c;写入.csv文件并上传至hdfs(含评论NLP文本分类/lsm情感分析); 3.使用hive建…

关于科技的总结与思考

文章目录 互联网时代有趣的数字数据驱动大数据的两个特性数据保护互联网免费模式的再探讨平台互联网的意义人工智能伦理的思考语言理性人梅特卡夫定律冲浪的神奇之处AR的恐怖之处叙词表、受控词表和大众分类法六度/十九度的解读知识图谱是真正的仿生智能幂次法则和优先连接现代…

MyBatis插件机制

MyBatis插件机制是该框架提供的一种灵活扩展方式&#xff0c;允许开发者在不修改框架源代码的情况下对MyBatis的功能进行定制和增强。这种机制主要通过拦截器&#xff08;Interceptor&#xff09;实现&#xff0c;使得开发者可以拦截和修改MyBatis在执行SQL语句过程中的行为。 …

【AI大模型】Transformers大模型库(五):AutoModel、Model Head及查看模型结构

目录​​​​​​​ 一、引言 二、自动模型类&#xff08;AutoModel&#xff09; 2.1 概述 2.2 Model Head&#xff08;模型头&#xff09; 2.3 代码示例 三、总结 一、引言 这里的Transformers指的是huggingface开发的大模型库&#xff0c;为huggingface上数以万计的预…

ChatGPT Prompt技术全攻略-总结篇:Prompt工程技术的未来发展

系列篇章&#x1f4a5; No.文章1ChatGPT Prompt技术全攻略-入门篇&#xff1a;AI提示工程基础2ChatGPT Prompt技术全攻略-进阶篇&#xff1a;深入Prompt工程技术3ChatGPT Prompt技术全攻略-高级篇&#xff1a;掌握高级Prompt工程技术4ChatGPT Prompt技术全攻略-应用篇&#xf…

DNS协议 | NAT技术 | 代理服务器

目录 一、DNS协议 1、DNS背景 2、DNS协议 域名 域名解析 二、NAT技术 1、NAT技术 2、NAPT技术 3、NAT技术的缺陷 三、代理服务器 1、正向代理服务器 2、反向代理服务器 一、DNS协议 域名系统&#xff08;Domain Name System&#xff0c;缩写&#xff1a;DNS&#…

20240605解决飞凌的OK3588-C的核心板刷机原厂buildroot不能连接ADB的问题

20240605解决飞凌的OK3588-C的核心板刷机原厂buildroot不能连接ADB的问题 2024/6/5 13:53 rootrootrootroot-ThinkBook-16-G5-IRH:~/repo_RK3588_Buildroot20240508$ ./build.sh --help rootrootrootroot-ThinkBook-16-G5-IRH:~/repo_RK3588_Buildroot20240508$ ./build.sh lun…

【学术小白成长之路】02三方演化博弈(基于复制动态方程)期望与复制动态方程

从本专栏开始&#xff0c;笔者正式研究演化博弈分析&#xff0c;其中涉及到双方演化博弈分析&#xff0c;三方演化博弈分析&#xff0c;复杂网络博弈分析等等。 先阅读了大量相关的博弈分析的文献&#xff0c;总结了现有的研究常用的研究流程&#xff0c;针对每个流程进行拆解。…

快速搭建rtsp server(Ubuntu)

在现代视频监控和实时视频流媒体应用中&#xff0c;实时流协议&#xff08;RTSP&#xff09;服务器扮演着至关重要的角色。无论是家庭安防系统、企业级监控还是流媒体服务&#xff0c;RTSP服务器都能提供高效、稳定的解决方案。然而&#xff0c;对于许多初学者或开发者来说&…

数学建模笔记

数学建模 定义角度 数学模型是针对参照某种事物系统的特征或数量依存关系&#xff0c;采用数学语言&#xff0c;概括地或近似地表述出的一种数学结构&#xff0c;这种数学结构是借助于数学符号刻画出来的某种系统的纯关系结构。从广义理解&#xff0c;数学模型包括数学中的各…