堆排序,快速排序

ops/2024/9/20 7:18:08/ 标签: 算法, java, 数据结构

目录

1.堆排序

2.快速排序

1.hoare版本

2.挖坑法

3.前后指针法

注意点


1.堆排序

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 + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);}else{break;}parent = child;child = parent * 2 + 1;}
}
void heapsort(int* a, int n)
{for (int i = (n - 1 -1) / 2; i >= 0; i--){adjustdown(a, n, i);}for (int i = n-1; i > 0; i--){Swap(&a[0], &a[i]);adjustdown(a, i, 0);}
}void printarr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
void heaptest()
{int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 };printarr(arr, sizeof(arr)/sizeof(int));heapsort(arr, sizeof(arr)/sizeof(int));printarr(arr, sizeof(arr)/sizeof(int));
}

        我们先用向下调整算法建堆。

        使用向下调整算法建堆的前提是,该节点的子树都是堆。那么我们从最后一个节点的父节点开始向下调整算法,这样因为两个子树都是叶子节点,因此满足条件。从后往前,一直遍历到父节点为根节点,那么就建好堆了。

        然后只需要不断将第一个和最后一个节点的值交换,把最大值放到末尾,然后不断从根节点向下建堆,即可每次都挑选出最大值,我们依次把他们放到末尾即可。 

2.快速排序

主逻辑,递归

1.hoare版本

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void printarr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}int partsort(int* a, int left, int right)
{int keyi = left;while (left < right){while (left < right &&a[left] <= a[keyi]){left++;}while (left < right && a[right] >= a[keyi]){right--;}Swap(&a[left], &a[right]);//如果是因为left==right结束,交换值也并不影响结果}Swap(&a[keyi], &a[left]);return left;
}void quicksort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = partsort(a, begin, end);quicksort(a, begin, keyi-1);quicksort(a, keyi + 1, end);
}void quicktest()
{int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 };printarr(arr, sizeof(arr) / sizeof(int));quicksort(arr,0, sizeof(arr) / sizeof(int)-1);printarr(arr, sizeof(arr) / sizeof(int));
}

我们以左边第一个下标为keyi,因此先从右边开始找

1.先从右往左找到比a【keyi】小的值

2.再从左往右找到比a【keyi】大的值

交换这两个值。

3.不断重复以上过程直到相遇left == right

4.交换a【keyi】和a【left】

注意点

        1.我们在移动下标时,判断条件是a[left] <= a[keyi]left++

                                                        a[right] >= a[keyi] right--

        这是为了防止遇到与a【keyi】相等的值的时候,陷入死循环

        2.我们在寻找下标的小循环中也加入left<right的判断是因为防止极端情况。

        如果不判断就会越界,而且如果是因为left==right结束,交换值也并不影响结果

        同时因为这个极端情况原因,我们遍历是从最左边keyi处开始遍历,不然会忽略掉这种情况。也是注意点1中判断条件需要加=的原因

 

 3.我们再来谈谈为什么从一边开始调整要从另一边开始找起

以上面的情况为例子,

因为这样可以保证他们相遇时候所处在的值一定比a【keyi】小

情况1、left不动,right先移动与left相遇,此时a【keyi】还在原位

情况2.  right移动后找到小值,left移动后与right相遇,此时该位置的值比a【keyi】小

情况3,left与right先各自移动并且交换一次,然后right再移动和left相遇,此时因为已经交换过,a【left】处储存的值小于a【keyi】因此也符合

综上

2.挖坑法

 

int partsort(int* a, int left, int right)
{int key = a[left];while (left < right){while (left < right && a[right] >= key){right--;}a[left] = a[right];while (left < right && a[left] <= key){left++;}a[right] = a[left];}a[left] = key;return left;}

 

 

 

 

 

把a【keyi】的位置先挖走,记录这个key值。

1.从右边往左找小,把这个值填入坑中,同时这个位置形成一个新的坑

2.从左边往右找大 把这个值填入坑中,同时这个位置形成一个新的坑

3.重复以上操作,直到left==right,然后把key值填入这个坑中,此时这个位置一定是坑,因为left和right永远有一个是坑

3.前后指针法

int partsort(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)//这里直接判断一下,相等就不交换,并且在判断条件 //的地方就更新prev{Swap(&a[prev], &a[cur]);}++cur;//cur就是一直往前走,直到结束,遇到相应位置才有操作,因此直接放到循环中}Swap(&a[keyi], &a[prev]);keyi = prev;return keyi;}

cur一直向后找小于key的位置

如果a【cur】< key

++prev,然后交换a【prev】和a【cur】

如果cur所在位置的值都比key小,那么cur和prev拉不开差距.++prev后和cur交换就是自身交换

        如果遇到比key大的值,就会拉开差距,此时如果cur遇到比key小的值,这个值就会和一个比key大的值交换,因为prev和cur原本中间隔着的都是大于key的值,++prev后再交换就会是这样的结果

 

这样相当于把大的往右推,小的往左推

 

cur走出数组结束,key与a【prev】交换即可 

注意点

        以上三种方法只是实现形式不同,时间复杂度是完全相同的,并且主逻辑的代码不需要更改,就是一个递归,只需要把部分排序修改即可


http://www.ppmy.cn/ops/112100.html

相关文章

raksmart的G口大流量服务器怎么样?

RAKsmart的G口大流量服务器以其高性能、高可用性、灵活配置和全球覆盖等特点&#xff0c;成为许多企业和个人用户的理想选择。以下是对raksmart G口大流量服务器的具体介绍&#xff1a; 1. 服务特点&#xff1a; RAKsmart提供多种类型的G口大流量服务器&#xff0c;包括流媒体专…

华为ensp中vlan与静态路由技术的实现

vlan 同一网段的设备&#xff0c;可以互通&#xff1b; 虚拟局域网&#xff1a;将局域网从逻辑上划分为多个局域网&#xff0c;不同通过vlan编号区分&#xff1b; 实现网络隔离。提高了网络安全性&#xff1b; vlan编号为12位&#xff1b; 范围1-4094可以用来配置 默认处于…

【Qt系列样式表】探索Qt Widget的艺术化设计与应用(Macos风格)(持续更新中...)

✨✨ Rqtz 个人主页 : 点击✨✨ &#x1f308;Qt系列专栏:点击 &#x1f388;PyQt系列专栏:点击&#x1f388; &#x1f388;Qt智能车上位机专栏: 点击&#x1f388; &#x1f388;Qt串口助手专栏:点击&#x1f388; &#x1f4ab;宗旨:共享IT之美,共创机器未来 目录 界面…

[羊城杯 2020]Blackcat1

知识点&#xff1a;数组加密绕过 进入页面熟悉的web三部曲&#xff08;url地址&#xff0c;web源代码&#xff0c;web目录扫描&#xff09; url地址没有什么东西去看看源代码. 这有一个mp3文件点一下看看. 在最后面发现了 PHP源码. if(empty($_POST[Black-Cat-Sheriff]) || em…

SpringMVC的初理解

1. SpringMVC是对表述层&#xff08;Controller&#xff09;解决方案 主要是 1.简化前端参数接收( 形参列表 ) 2.简化后端数据响应(返回值) 1.数据的接受 1.路径的匹配 使用RequestMapping(可以在类上或在方法上)&#xff0c;支持模糊查询&#xff0c;在内部有method附带…

【无人机设计与控制】四旋翼无人机俯仰姿态保持模糊PID控制(带说明报告)

摘要 为了克服常规PID控制方法在无人机俯仰姿态控制中的不足&#xff0c;本研究设计了一种基于模糊自适应PID控制的控制律。通过引入模糊控制器&#xff0c;实现了对输入输出论域的优化选择&#xff0c;同时解决了模糊规则数量与控制精度之间的矛盾。仿真结果表明&#xff0c;…

React Native防止重复点击

项目中遇到了点击按钮重复提交的问题&#xff0c;防止重复点击首先是想到的是给点击事件一个定时&#xff0c;下次触发的条件是要距离上一次点击的时间大于N秒的之后才能再执行。 // 防重复点击函数 export const preventRepeatPress {lastPressTi1me: 0, // 上次点击时间…

【Qt】Qt C++ Widget中嵌入qml

1. 效果 2. 方法 使用QQuickWidget方式 QQuickWidget *view new QQuickWidget;view->setSource(QUrl::fromLocalFile("myqmlfile.qml"));view->show();除了QQuickWidget方式还可以使用QQuickView方式&#xff0c;请自行查阅资料 3. 代码 3.1 工程目录 3.2 …

重生归来之挖掘stm32底层知识(1)——寄存器

概念理解 要使用stm32首先要知道什么是引脚和寄存器。 如下图所示&#xff0c;芯片通过这些金属丝与电路板连接&#xff0c;这些金属丝叫做引脚。一般做软件开发是不需要了解芯片是怎么焊的&#xff0c;只要会使用就行。我们平常通过编程来控制这些引脚的输入和输出&#xff0c…

小程序面试题七

一、微信小程序如何实现下拉刷新&#xff1f; 微信小程序实现下拉刷新的功能&#xff0c;并不是直接内置了一个下拉刷新的组件或API&#xff0c;但你可以通过监听页面的滚动事件来实现这一功能。以下是一个基本的实现步骤&#xff1a; 1. 监听页面的滚动事件 在小程序的页面配…

物联网之PWM呼吸灯、脉冲、LEDC

MENU 前言原理硬件电路设计软件程序设计analogWrite()函数实现呼吸灯效果LEDC输出PWM信号 前言 学习制作呼吸灯&#xff0c;通过LED灯的亮度变化来验证PWM不同电压的输出。呼吸灯是指灯光在单片机的控制之下完成由亮到暗的逐渐变化&#xff0c;感觉好像是人在呼吸。 原理 脉冲宽…

代码随想录 第九章 动态规划part07 198.打家劫舍 213.打家劫舍II 337.打家劫舍III

198.打家劫舍 class Solution { public:int rob(vector<int>& nums) {vector<int> dp(nums.size() 1, 0);nums.insert(nums.begin(), 0);dp[1] nums[1];int pre 1;for (int i 2; i < dp.size(); i){if (pre (i - 1)){if (dp[i - 1] < dp[i - 2] n…

Java笔记 【1】docker introduction

概述 为什么会有 docker 出现 Docker 理念 容器与虚拟机比较 容器发展简史 传统虚拟机技术 容器虚拟化技术 对比 优点 参考 概述 为什么会有 docker 出现 之前在服务器配置一个应用的运行环境&#xff0c;要安装各种软件&#xff0c;Java/RabbitMQ/MySQL/JDBC 驱动包等。安…

《C++》解密--顺序表

一、线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈...... 线性表在【逻辑上】是线性结构…

Git 中的refs

在 Git 中&#xff0c;refs 是用来存储 Git 对象&#xff08;如提交、树、标签等&#xff09;的引用。每个 ref 都是一个指针&#xff0c;指向一个特定的 Git 对象。以下是 Git 中几种常见的 refs 及其含义&#xff1a; 1. refs/heads/ 表示&#xff1a;本地分支。 用途&…

Python Web开发中的扩展与插件开发:从自定义到打包与发布

Python Web开发中的扩展与插件开发&#xff1a;从自定义到打包与发布 目录 ⚙️ Flask中的自定义扩展开发&#x1f6e0;️ Django中的自定义插件开发&#x1f4e6; 插件的打包与发布详解&#x1f504; 版本控制与依赖管理&#xff08;pipenv、poetry&#xff09; 1. ⚙️ Fla…

vulnhub(8):pWnOS(还没信息收集就已经成功打点)

端口 nmap主机发现 nmap -sn 192.168.89.0/24 ​ Nmap scan report for 192.168.89.116 Host is up (0.00020s latency). ​ 116是新出现的机器&#xff0c;他就是靶机 nmap端口扫描 nmap -Pn 192.168.89.116 -p- --min-rate 10000 -oA nmap/scan 扫描开放端口保存到 nmap/sca…

基于spring的ssm整合

目录 基于spring的ssm整合 Spring 框架 SpringMVC 框架 MyBatis 框架 1.创建项目 2.导入依赖 3.导入sql 4.创建jdbc.propries文件 1&#xff09;mysql8以下 2&#xff09;mysql8以上的 5.创建mybatis-config.xml配置文件 6.创建spring-Config.xml文件 7.创建项目所需包和类 1&a…

宝塔部署python项目

宝塔部署-python项目文章浏览阅读559次&#xff0c;点赞11次&#xff0c;收藏9次。在添加项目后&#xff0c;选择项目所在的路径&#xff0c;然后命令行启动主py文件。具体先看项目日志&#xff0c;根据日志在环境管理处下载包。首先下载项目需要的python版本。_宝塔部署python…

【ShuQiHere】探索人工智能核心:机器学习的奥秘

【ShuQiHere】 &#x1f4a1; 什么是机器学习&#xff1f; 机器学习&#xff08;Machine Learning, ML&#xff09;是人工智能&#xff08;Artificial Intelligence, AI&#xff09;中最关键的组成部分之一。它使得计算机不仅能够处理数据&#xff0c;还能从数据中学习&#x…