快速排序(2)
一、快速排序有三种方法:hoare版本、挖坑法、前后指针版本
但是三种方法的核心思想都是一样的,都是将该数组分为左右两半递归式的排序。
1.hoare版本

该方法是先保存a[keyi]位置的值,然后右边先开动找小,找到小后,左边开动找大,找到大之后,两数互换,最后,相遇位置与a[keyi]位置互换(即默认每次相遇位置都是小于a[keyi]):
int PartSort1(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}
那为什么默认相遇位置比a[keyi]小呢?

2.挖坑法
该方法是先把第一个数据存放在临时变量key中,形成一个坑位,然后r向左走(r--),直到找到比key小的,将r的值放入l中,r处形成一个坑位,然后l向右走(l++),直到找到比key大的……以此循环。

int PartSort2(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int key = a[begin];int hole = begin;while (begin < end){// 右边找小,填到左边的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左边找大,填到右边的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;
}
3.前后指针版本
该方法是将第一个数据保存至临时变量key中,利用两个指针,prev = begin,cur = prev + 1,cur向前进(cur++),遇到比key小时,让a[pre
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSortn(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
v+1]与a[cur]位置的数据进行交换,以此往复循环。

快排:
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSortn(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}
找三数中值:
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin midi end 三个数选中位数if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else // a[begin] > a[midi]{if (a[midi] > a[end])return midi;else if (a[begin] < a[end])return begin;elsereturn end;}
}
二、快排的非递归
为了实现快排的非递归,我们就需要借助基本数据结果栈来解决:
每次都可以插入头和尾(begin、end)的数据进入(STPush),由于后进先出原则,因此我们先插入end,再插入begin,取STTop赋值于left,Pop数据,再取STTop赋值于right,Pop数据,随后进行快排,这里其实就是一种递归思想的非递归。
代码:
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PartSort3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}}STDestroy(&s);
}
C语言中栈的实现:
//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* a;int top; // 标识栈顶位置的int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);bool STEmpty(ST* pst);
int STSize(ST* pst);
//Stack.c
#include"Stack.h"void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;// 表示top指向栈顶元素的下一个位置pst->top = 0;// 表示top指向栈顶元素//pst->top = -1;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}// 栈顶插入
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}//栈顶删除
void STPop(ST* pst)
{assert(pst);// 不为空assert(pst->top > 0);pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);// 不为空assert(pst->top > 0);return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)
{assert(pst);/*if (pst->top == 0){return true;}else{return false;}*/return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}相关文章:
快速排序(2)
一、快速排序有三种方法:hoare版本、挖坑法、前后指针版本 但是三种方法的核心思想都是一样的,都是将该数组分为左右两半递归式的排序。 1.hoare版本 该方法是先保存a[keyi]位置的值,然后右边先开动找小,找到小后,左…...
持续集成和持续交付
引言 CI/CD 是一种通过在应用开发阶段引入自动化来频繁向客户交付应用的方法。CI/CD 的核心概念是持续集成、持续交付和持续部署。作为一种面向开发和运维团队的解决方案,CI/CD 主要针对在集成新代码时所引发的问题(亦称:“集成地狱”&#…...
C#、JavaScript、VBScript解析JSON数据源码
本示例使用设备:WIFI/TCP/UDP/HTTP协议RFID液显网络读卡器可二次开发语音播报POE-淘宝网 (taobao.com) C#解析JSON数据 string dispstr "{" getChinesecode("扫码") ":}" data; //显示信息,注意中文汉字一定要转换为设备能显…...
JVM面试连环炮:你准备好迎接挑战了吗?
在Java开发领域,JVM面试一直是一个热门话题。作为一名优秀的开发者,你是否已经准备好迎接这场挑战了呢?今天,我们就来深度解析一下JVM面试的热点问题,帮助你更好地应对面试,一举拿下offer! 1、…...
Ansible通过kubernetes.core.k8s_info和kubernetes.core.k8s访问OCP
文章目录 环境OCPClient(Ansible控制节点) 步骤准备工作在client端配置ssh免密登录OCP端在client端安装Ansible kubernetes.core.k8s_info第1次尝试在OCP端安装python和pip3在OCP端安装kubernetes在OCP端安装PyYAML第2次尝试在OCP端配置config文件第3次尝…...
vscode汉化
安装插件 Chinese (Simplified) (简体中文) Language Pack for 重新打开,若还是没有汉化: 【CtrlShiftp】 输入“configure display language”,回车键 选择刚刚安装的 中文(简体)...
美易投资:美国圣诞树价格飙升,涨价的问题所在?
美国圣诞树价格飙升,商家称“拜登经济学”是导致涨价的罪魁祸首 随着圣诞节的临近,美国各地的家庭开始准备庆祝这一传统佳节。然而,今年美国的圣诞树价格却呈现出了明显的上涨趋势。据一些商家反映,这主要是由于“拜登经济学”所致…...
国内外聊天AI大比拼,你知道几个?一键了解最火聊天AI应用!
国内类ChatGPT的AI工具一网打尽 2022年,是一个不平凡的一年。ChatGPT迅速崭露头角,成为备受瞩目的热门话题。特别是在OpenAI发布了基于GPT-3.5模型的ChatGPT版本后,这一产品因其卓越的对话能力和广泛的应用潜力,很快引起了大众的…...
C++STL的vector模拟实现
文章目录 前言成员变量成员函数构造函数push_backpop_backinserterase析构函数拷贝构造 前言 成员变量 namespace but {template<class T>class vector{public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;}; }我们之前实…...
openssl 常用命令 pkcs12
openssl pkcs12 openssl pkcs12 官方文档 1. 描述 The pkcs12 command allows PKCS#12 files (sometimes referred to as PFX files) to be created and parsed. PKCS#12 files are used by several programs including Netscape, MSIE and MS Outlook. pkcs12 命令是用来创…...
2017下半年软工(桥接模式)
题目——桥接模式(抽象调用实现部分) package org.example.桥接模式;/*** 桥接模式的核心思想是将抽象部分与它的实现部分分离,使它们可以独立变化,就是说你在实现部分:WinImp、LinuxImp基础上还能加上RedHatImp&#…...
Hive 浅析
Hive是一个简单的LUA沙盒,除了基本的LUA解释器的功能以外,还提供了诸如热加载等功能。 了解HIVE的工作原理有利于了解Lua虚拟机的底层实现机理。 本文从是什么-怎么用-为什么三个维度介绍HIVE。 Hive Hive是什么 hive是一个简单的LUA应用框架,目前基于…...
C 语言中,结构体「.」与「->」的区别
简单来说 「 」的左边是结构体名字时用点符号「.」 「 」的左边是结构体指针时名字时用箭头「->」 对于要读取结构体种的数据时,有下面三种写法,操作是等价的。 struct ListNode a;struct ListNode *p1 &a;/*三种写法*/a.element 2333;p1->e…...
【Java Web学习笔记】5 - XML
项目代码 https://github.com/yinhai1114/JavaWeb_LearningCode/tree/main/xml 零、在线文档 XML系列教程 一、XML引出 1.为什么需要XML 1.需求1 :两个程序间进行数据通信? 2.需求2:给一台服务器,做一个配置文件,当服务器程序启动时,去…...
在jupyter notebook中修改其他文件的解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...
如何在Android中旋转屏幕时避免重新绘制Activity
如何在Android中旋转屏幕时避免重新绘制Activity 在Android开发中,设备旋转通常导致当前活动(Activity)被销毁并重新创建,这可能导致用户界面重置和不必要的资源重新加载。然而,有时我们希望避免这种行为,…...
离线环境下安装python库(推荐pip download)
离线环境下安装python库(推荐pip download) 目录 1.需求 2.失败操作(注意) 3.成功操作 4.其它参考 1.需求 机器部署web系统环境后,就不可再次联网,所以升级python web后端,需要离线安装pyt…...
ubuntu16.04安装ROS+Gazebo
ubuntu16.04安装ROS参考文章 ros安装(一键最简安装,吹爆鱼香ROS,请叫我鱼吹) ROS篇——Ubuntu快速一键安装ROS或ROS2(通用) ubuntu安装ROS melodic(最新、超详细图文教程) 配置ubuntu以及安装ros2必要环…...
手动搭建koa+ts项目框架(路由篇)
文章目录 前言一、安装koa-router二、引入koa-router并使用三、优化路由配置总结如有启发,可点赞收藏哟~ 前言 本文基于手动搭建koats项目框架(基础篇)配置接口路由 一、安装koa-router npm i -S koa-router二、引入koa-router并使用 ./sr…...
c语言:文件操作(1)
前言:为什么要使用文件 使用文件可以让程序在不同运行之间保存和读取数据。这样可以实现持久化存储,即使程序关闭后数据也不会丢失。文件也可以用于数据交换,允许不同程序之间共享信息。在 C 语言中,文件还可以用于读取配置信息&…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
