快速排序的实现

目录

一、递归

        1、霍尔法：

2、挖坑法：

3、前后指针法：

二、非递归

三、完整代码：

基本思想：

先取这个待排序元素序列中的某一个元素最为key值，然后通过这个key值将这个序列分为两边，一边小于这个key，另一边大于这个key，然后接着对这个左边的序列和右边的序列进行相同的操作，直到所有的元素都在相应的位置上。

一、递归

        1、霍尔法：

思路：

这里排序为升序

我们这里找最左边的元素作为key

定义一个变量指向最右边right，再来一个变量指向最左边left（注意，如果key在左边，那么就要从右边开始先走，如果key在右边，那么就要从左边开始走，这样才能保证这两个相遇的位置一定比key要小）

来个循环遍历这个序列：

right开始向左走找一个比key还要小的，

找到后left向右走找到一个比key还要大的，

接着交换这两个位置的元素。

所以结束条件就是left<right。

结束后交换此时这两个所在的共同位置和key的位置，key也要换到这个位置

最后再来递归即可（所以可以在最开始用两个变量begin和end记录left和right的位置）

OK！思路一出直接开写：

在写之前要两个函数，一个是交换函数：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

另外一个为优化这个快速排序的代码：三数取中，也就是说在三个数中取中间大的那个数字

。这样可以使单趟排序后左边的和右边的元素个数差不多，进而减小递归的深度。

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

OK！现在可以开始写了

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;

	//三数取中
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		//右边先走找小的
		while (left < right && a[right] >= a[keyi])
			right--;
		//左边走找大的
		while (left < right && a[left] <= a[keyi])
			left++;
		if (left == right)
			break;

		Swap(&a[right], &a[left]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;

	QuickSort1(a, begin, keyi - 1);//这里为左边的区间
	QuickSort1(a, keyi + 1, end);//这里为右边的区间
}

2、挖坑法：

思路：

首先，将第一个元素存放在临时变量key中，此时将第一个元素定义为hole，这个时候这个hole就可以随便改了。

接着像霍尔法一样，right向左走找比key小的位置，此时将这个位置的元素赋值给hole，然后将hole改到这个right所在的位置。

然后left向右走找比key大的位置，找到后将这个位置的元素赋值给hole，然后将hole改到这个left所在的位置。

直到left == right后退出循环，此时将最开始的变量key放在hole中

最后左递归的区间为[begin, hole - 1]

        右递归的区间为[ hole + 1, end]

OK！思路一出，直接开写：

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;

	//三数取中
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int begin = left, end = right;

	int hole = left;
	while(left < right)
	{
		while (left < right && a[right] >= key)
			right--;
		//Swap(&a[hole], &a[right]);
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
			left++;
		//Swap(&a[hole], &a[left]);
		a[hole] = a[left];
		hole = left;
		
	}
	a[hole] = key;
	QuickSort2(a, begin, hole - 1);
	QuickSort2(a, hole + 1, end);
}

3、前后指针法：

思路：

首先：定义最左边为key，然后最左边为prev，prev的下一个为cur

然后如果cur所在的值小于key，那么++prev，然后将cur所在的值和prev所在的值相交换，在cur++。

如果cur的值不小于key，那么就cur++。

退出循环的条件为cur小于right。

最后交换此时prev所在的元素和最左边的元素。

 

理解：

prev和cur之间要么紧跟着，要么prev和cur中间间隔着比key大的一段区间。

OK！思路一出，直接开写

int QuickSort3(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;

	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
        {
	        prev++;
	        Swap(&a[cur], &a[prev]);
	        cur++;
        	continue;
        }
        else
        {
	        cur++;
        	continue;
        }
    }

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = QuickSort3(a, left, right);
	QuickSort3(a, left, keyi - 1);
	QuickSort3(a, keyi + 1, right);
}

这里QuickSort3返回值与上面不同为后面非递归的完成做铺垫。

二、非递归

思路：

因为递归可能会存在栈溢出，那么就需要把这个程序修改为非递归。

那么就需要栈和循环来帮助我们实现递归转非递归。

1、首先将这个序列的right先入栈，再将left入栈（顺序其实是无伤大雅的），

2、然后来个循环，结束条件为这个栈为空

3、在循环中定义begin访问栈顶的元素，就是上面的left（left后入栈的）

定义end访问栈顶元素的下一个为right。

4、接着用QuickSort3来进行单趟排序，返回值记录在keyi中。

所以里面区间就变成了：[begin,keyi-1] keyi [keyi+1, end]（左边比keyi小，右边比keyi大）

5、接着判断，如果keyi+1小于end，那么依次将end和keyi+1入栈，

                        如果keyi-1大于begin，那么将依次将keyi-1和begin入栈。       

所以此时循环上去就继续访问栈顶元素和栈顶元素的下一个来作为begin和end继续排序。

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = QuickSort3(a, begin, end);
		// [begin,keyi-1] keyi [keyi+1, end]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi+1);
		}

		if (begin < keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

三、完整代码：

栈的代码：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define N 10

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//打印无法保证后进先出
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//判断栈里面元素的个数
int STSize(ST* ps);
//判断栈顶元素是否为空
bool STEmpty(ST* ps);
//访问栈顶元素
STDataType STTPop(ST* ps);

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void STInit(ST* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;//代表栈顶元素的下一个位置
	//ps->top = -1;//代表栈顶元素
}
//销毁栈
void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STDataType* newnode = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
		if (newnode == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = newnode;
		ps->capacity *= 2; 
	}
	ps->a[ps->top] = x;
	ps->top++;
}
//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;

}
//判断栈里面元素的个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
//判断栈顶元素是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//访问栈顶元素
STDataType STTPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top-1];
}

快排代码：

#pragma once
#include<stdio.h>
#include<stdlib.h>

void QuickSort1(int* a, int left, int right);
void QuickSort2(int* a, int left, int right);
int QuickSort3(int* a, int left, int right);
int GetMidNumi(int* a, int left, int right);

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;
	//随机选keyi
	/*int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);*/

	//三数取中
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		//右边先走找小的
		while (left < right && a[right] >= a[keyi])
			right--;
		//左边走找大的
		while (left < right && a[left] <= a[keyi])
			left++;
		if (left == right)
			break;

		Swap(&a[right], &a[left]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;

	//三数取中
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int begin = left, end = right;

	int hole = left;
	while(left < right)
	{
		while (left < right && a[right] >= key)
			right--;
		//Swap(&a[hole], &a[right]);
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
			left++;
		//Swap(&a[hole], &a[left]);
		a[hole] = a[left];
		hole = left;
		
	}
	a[hole] = key;
	QuickSort2(a, begin, hole - 1);
	QuickSort2(a, hole + 1, end);
}

int QuickSort3(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;

	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
        {
	        prev++;
	        Swap(&a[cur], &a[prev]);
	        cur++;
        	continue;
        }
        else
        {
	        cur++;
        	continue;
        }
    }

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = QuickSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort3(a, begin, end);
		// [begin,keyi-1] keyi [keyi+1, end]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi+1);
		}

		if (begin < keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vue-2

vue-2

vue-cli的安装 vue-cli是一个脚手架工具&#xff0c;它集成了诸多前端技术&#xff0c;包括但不仅限于&#xff1a; webpack、 babel、eslint、http-proxy-middleware、typescript、css pre-prosessor、css module、… 这些工具&#xff0c;他们大部分都要依赖两个东西&…
阅读更多...
访问限制

访问限制

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 在类的内部可以定义属性和方法&#xff0c;而在类的外部则可以直接调用属性或方法来操作数据&#xff0c;从而隐藏了类内部的复杂逻辑。但是Python并…
阅读更多...
HALCON-从入门到入门-花式读取图片的N种方式

HALCON-从入门到入门-花式读取图片的N种方式

1.废话 很多时候我们不止读取一张图片-读取文件夹下的多张 甚至我们可能想在多个文件夹中读取多张图片。 再变态点我们想再任意若干路径下读取任意若干张图片。 没关系&#xff0c;这些halcon开发人员都替我们考虑到了。 只需要使用下面一个算子 list_files (, files, Fi…
阅读更多...
【CMake】CMake入门（五）打包安装程序 使用CMake管理库 打包调试版和发行版

【CMake】CMake入门（五）打包安装程序 使用CMake管理库 打包调试版和发行版

本篇文章不是新手入门教学文章&#xff0c;主要是记录笔者个人的学习笔记 CMake入门&#xff08;五&#xff09; 一、打包二、使用CMake管理库三、打包调试版和发行版 一、打包 发布程序可以有多种形式&#xff0c;比如安装包、压缩包、源文件等。CMake也提供了打包程序cpack可…
阅读更多...
电脑数据恢复，6个方法，恢复文件很简单！

电脑数据恢复，6个方法，恢复文件很简单！

“我在使用电脑时&#xff0c;一个不小心就误删了部分重要数据&#xff0c;现在想恢复电脑数据却不知怎么操作了&#xff0c;希望大家帮帮我&#xff01;” 在数字化时代&#xff0c;电脑数据不仅是工作和学习的重要载体&#xff0c;更是我们生活中珍贵的记忆和情感的存储地。然…
阅读更多...
二叉树创建和遍历(及相关OJ题)

二叉树创建和遍历(及相关OJ题)

个人主页 &#xff1a;敲上瘾-CSDN博客二叉树介绍&#xff1a;二叉树(详解)-CSDN博客 目录 一、二叉树的创建 二、二叉树的遍历 1.前序遍历 2.中序遍历 3.后序遍历 4.层序遍历 三、相关计算 1.总节点个数计算 2.叶子节点个数计算 3.深度计算 一、二叉树的创建 关于…
阅读更多...
❤机器学习正则化算法的总结。耗时10个小时完成。❤

❤机器学习正则化算法的总结。耗时10个小时完成。❤

❤纯 干 货~❤ 目录 纯干货 1、L1 正则化&#xff08;Lasso 正则化&#xff09; 2、L2 正则化&#xff08;岭正则化&#xff09; 3、弹性网络正则化&#xff08;Elastic Net 正则化&#xff09; 4、Dropout 正则化&#xff08;用于神经网络&#xff09; 5、贝叶斯Rid…
阅读更多...
风力发电机常见故障分析

风力发电机常见故障分析

风力发电机常见故障分析 风力发电机是风电机组中的核心部件&#xff0c;其运行的可靠性和稳定性对整个风电系统的发电效率至关重要。然而&#xff0c;由于复杂的机械结构和长期暴露在严酷环境中&#xff0c;风力发电机在运行过程中可能会出现各种故障。本文将详细介绍风力发电…
阅读更多...
【Linux】深入理解文件操作：从C语言接口到系统调用与缓冲区管理

【Linux】深入理解文件操作：从C语言接口到系统调用与缓冲区管理

文章目录 前言&#xff1a;1. 铺垫2. 重新使用C文件接口&#xff1a;对比一下重定向2.1. 什么叫当前路径&#xff1f;2.2. 写入文件2.3. 读文件2.4. 程序默认打开的文件流2.5. 输出2.6. 输入 3. 系统调用提供的文件接口3.1. open 打开文件3.2. open函数返回值 4. 缓冲区问题总结…
阅读更多...
MongoDB~索引使用与优化

MongoDB~索引使用与优化

Study by&#xff1a; https://docs.mongoing.com/indexeshttps://www.cnblogs.com/Neeo/articles/14325130.html#%E5%85%B6%E4%BB%96%E7%B4%A2%E5%BC%95 作用 如果你把数据库类比为一本书&#xff0c;那书的具体内容是数据&#xff0c;书的目录就是索引&#xff0c;所以索引…
阅读更多...
【随笔】Git 实战篇 -- 开心 commit 之后，发现有一处bug还需要改，只能 reset 撤销然后再次提交 -- git reset --（四十三）

【随笔】Git 实战篇 -- 开心 commit 之后，发现有一处bug还需要改，只能 reset 撤销然后再次提交 -- git reset --（四十三）

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…
阅读更多...
RabbitMQ小结

RabbitMQ小结

MQ分类 Acitvemq kafka 优点&#xff1a;性能好&#xff0c;吞吐量高百万级&#xff0c;分布式&#xff0c;消息有序 缺点&#xff1a;单机超过64分区&#xff0c;cpu会飙高&#xff0c;消费失败不支持重试 &#xff0c; Rocket 阿里的mq产品 优点&#xff1a;单机吞吐量也…
阅读更多...
如何赋予LLM多模态能力（MLLM）

如何赋予LLM多模态能力（MLLM）

基本概念 多模态大型语言模型&#xff08;MLLMs&#xff09;是人工智能领域的一项前沿技术&#xff0c;旨在设计能够理解和生成跨越多种形式数据输入&#xff08;如文本和图像&#xff09;内容的模型。 链接文本和视觉模态&#xff1a;MLLMs能够整合文本和视觉数据源的信息。…
阅读更多...
众汇：外汇狙击指标如何使用？

众汇：外汇狙击指标如何使用？

对于投资者来说&#xff0c;我们各位交易的目的是什么?WeTrade众汇认为那就是盈利。所以来说有一个指标对各位投资者来说那是相当有帮助的。这是因为对于交易者而言&#xff0c;利用这些指标可以快速识别盈利的买卖时机。当我们选择一个指标之后&#xff0c;深入了解其适用范围…
阅读更多...
【机器学习】机器学习与AI大数据的融合：开启智能新时代

【机器学习】机器学习与AI大数据的融合：开启智能新时代

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 机器学习与AI大数据的融合 &#x1f4d2;1. 引言&#x1f4d5;2. 机器学习与大数据&#x1f3a9;机器学习与大数据的特征&#x1f388;大数据如…
阅读更多...
基于全志T507-H的Linux-RT实时性测试案例分享

基于全志T507-H的Linux-RT实时性测试案例分享

本文将为各位工程师演示全志T507-H工业评估板&#xff08;TLT507-EVM&#xff09;基于IgH EtherCAT控制伺服电机方法&#xff0c;生动说明Linux-RT Igh EtherCAT的强大之处&#xff01; Linux-RT系统的优势 内核开源、免费、功能完善。 RT PREEMPT补丁&#xff0c;使Linux内…
阅读更多...
树形结构获取所有直属父级节点

树形结构获取所有直属父级节点

递归获取 let arr [{name: "/",meta: {},children: [{name: "home",},{name: "home2",},{name: "common-components",children: [{name: "form-component",}]},{name: "multilevel-menu",children: [{name: &qu…
阅读更多...
【数据结构】复杂度的重要性—–决定程序运行的效率

【数据结构】复杂度的重要性—–决定程序运行的效率

【数据结构】复杂度的重要性—–决定程序运行的效率 前言 在我们写算法的时候&#xff0c;常常会需要考虑一个问题&#xff1a;这个算法好不好&#xff1f;而这个“好”实际上就取决于是算法的复杂度。 算法复杂度&#xff08;Algorithmic Complexity&#xff09;是指算法在编…
阅读更多...
粒子系统技术在AI绘画中的创新应用

粒子系统技术在AI绘画中的创新应用

引言&#xff1a; 随着人工智能技术的飞速发展&#xff0c;AI绘画已经成为艺术创作和数字媒体领域的一大热点。粒子系统作为一种模拟复杂物理现象的技术手段&#xff0c;其在AI绘画中的应用为创作过程带来了前所未有的灵活性和创新性。本文将深入探讨粒子系统技术的原理、特点以…
阅读更多...
Nvidia Jetson/Orin +FPGA+AI大算力边缘计算盒子：人工智能消防应用

Nvidia Jetson/Orin +FPGA+AI大算力边缘计算盒子：人工智能消防应用

青鸟消防股份有限公司成立于2001年6月&#xff0c;于2019年8月在深圳证券交易所挂牌上市&#xff0c;成为中国消防报警行业首家登陆A股的企业。公司始终聚焦于消防安全与物联网领域&#xff0c;主营业务为“一站式”消防安全系统产品的研发、生产和销售。公司产品已覆盖了火灾报…
阅读更多...
最新文章

Copyright @ 2022~2023