c语言数据结构(10)——冒泡排序、快速排序

欢迎来到博主的专栏——C语言数据结构
博主ID:代码小豪

文章目录

    • 冒泡排序
    • 冒泡排序的代码及原理
    • 快速排序
    • 快速排序的代码和原理
    • 快速排序的其他排序方法
    • 非递归的快速排序

冒泡排序

相信冒泡排序是绝大多数计科学子接触的第一个排序算法。作为最简单、最容易理解的排序算法,冒泡排序虽然效率不高,但是冒泡排序的思路给了其他排序算法一些启发。

冒泡排序的思路如下:
(1)从第一个数据开始,向后继元素比较大小、若满足条件(大于或小于),则交换数据的位置,然后从后一个位置开始继续比较。
(2)当N-1与N进行数据比较后、完成一趟冒牌排序,然后从头开始继续进行冒牌排序
(3)完成N-1趟排序后、冒牌排序结束。

在这里插入图片描述
在这里插入图片描述
可以发现、在第一趟冒泡排序结束后,最大值7排到了最后一位,而升序数组中的7也是排到最后一位。这一趟冒泡排序就确定了升序数组中的一位。

当第二趟冒泡排序开始时,由于最后一位的数据已经确定了,因此不再需要参与排序,将end向前移动一位,以此类推。
在这里插入图片描述

冒泡排序的代码及原理

void Swap(int* e1, int* e2)//交换函数
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)//共计排n-1趟
	{
		int end = n - i - 1;
		for (int begin = 0;//每趟冒泡排序从0开始
			begin < end;//当begin=end时结束
			begin++)
		{
			if (a[begin] > a[begin + 1])//满足条件交换数据
			{
				Swap(&a[begin], &a[begin + 1]);
			}
		}
	}
}

冒牌排序的原理如下:
每一趟冒泡排序都能使至少一个数据处于正确的升降序的位置。即每趟排序都能让当前范围的最大值,位于最后一个位置,好比水中的鱼吐出的泡泡,从水底到水面渐渐变大。
在这里插入图片描述

快速排序

快速排序和冒泡排序都有一个相似之处,或者是一种排序的思路,即一趟排序完成单个或多个数据的定位(将数据排在最终确定的位置上),多次排序后将所有数据都完成定位,最终完成排序操作。

冒泡排序的思路是每次确定最后一位,因此每趟排序都需要将整个数组遍历一遍,导致时间复杂度非常高。快速排序作为最著名昭著的排序算法,以高效率深受程序员喜爱,这里讲讲快排的优化之处。

先来了解一下快速排序的步骤:
(1)选取数组中的任意一个数据作为关键数据(key)
(2)让key左边的数据小于(大于)key,右边的数据大于(小于)key
(3)将整体分割为两部分,一部分是key左边,另一部分是key右边,以这些部分作为一个整体,重复(1)(2)(3)操作,直到所以数据不可分割为止。

这个思路单凭讲述时很难理解其中奥义的。我们先拆分步骤逐渐讲解。
(1)选取key可以选择区间中的任意数据,选取方法通常有三种:取队首、取队尾、随机值取中间数,通常来说结合三数取中(即在队首、队尾、随机之间选择中间数作为key)是最合理的。但这里为了方便讲解,选择取队首作为key

(2)中让key左边的数据小于key,右边的数据大于key有多种方法,总体而言对效率影响不大,我们先来了解快排发明者霍尔的方法。

首先将待排序的区间选出,队首第一个值为key值。区间最左边设置一个left,最右边设置一个right。如图:
在这里插入图片描述

让right往左边遍历,若遍历的数据小于key,则right停留在该数据处。
在这里插入图片描述

当right找到比key小的数后,让left向右遍历找到比key大的数。找到比key大的数后,停留在该数据处。
在这里插入图片描述
当left和right都停留时,交换left和right
在这里插入图片描述
交换结束后,重复上述步骤,让right向左遍历。
在这里插入图片描述
此时left继续向右遍历,left与right重合,此时将key与重合位置的数据交换。
在这里插入图片描述
以key为分割线,将这段区间分为两个区间。
在这里插入图片描述
再对这两个区间进行快排。以此类推。
在这里插入图片描述
当某个区间的left和right重合,数据不可再分割,不再需要排序。
在这里插入图片描述

快速排序的代码和原理

快速排序的原理如下:
和冒泡排序有个类似的点,每一趟冒泡排序都有一个数据被定位,快速排序也是如此,key位置的左边小于key,右边大于key,那么key这个位置就是符合排序要求的位置的。那么快速排序比冒泡排序有效率的点在哪呢?

冒泡排序每趟排序都需要将整个数组遍历一遍。快速排序使用了一种分治的方法,将区间分割成多个小区间进行排序,减少了需要遍历的元素个数。
在这里插入图片描述
此时快速排序就不再需要遍历整个数组了,而是遍历小区间,遍历区间1只用遍历4个数据,定位一个,区间2只需遍历2个数据,定位1,当数据数量变得很多时,快速排序的优势更加明显,效率更快。

代码如下:

void QuickSort(int* a, int begin, int end)
{
	int left = begin;
	int right = end-1;
	if (left >= right)//区间不可再分割,结束递归
	{
		return;
	}
	int key = left;//队首取key
	while (left < right)//遍历条件
	{
		while (left < right && a[key] < a[right])//right向左寻找比key小的值
		{
			right--;
		}
		while (left < right&&a[key]>a[left])//left向右寻找比key大的值
		{
			left++;
		}
		Swap(&a[left], &a[right]);//找到之后交换
	}
	Swap(&a[key], &a[left]);//left与right相等,与key交换。
	key = left;
	QuickSort(a, begin, key);//分割
	QuickSort(a, key + 1, end);//分割
}

快速排序的其他排序方法

这里介绍另外一种排序方式——前后指针法。霍尔使用left和right的找寻方法非常巧妙,但是代码较复杂。这里讲一种较为简洁的找寻方法(对效率影响不大)。

定义一个prev和cur指向队首与队首的后一个元素,key值仍取队首。

步骤如下:
(1)判断cur的值是否大于prev
若大于:cur往前移动一位,prev不变。
若小于:prev往前移动一位,与cur交换数据,cur再往前移动一位。(若prev指针与cur相遇,不交换)。
(2)当cur超出区间后,让key与prev交换数据。
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
剩下也是将key分割两个区间继续分治,只是找寻方法改变了。

为什么这种方法能完成key的左边比key小,右边比key大呢?
首先,我们可以发现,cur与prev之间的元素都是比key大的。我们重新回顾一下步骤。

(1)最初开始时,prev与cur之间不存在任何数据(因为他们相邻)。
(2)cur与prev最初是挨着的,当cur遍历到比key大的树据才会有所距离(此时距离之间的数据都是比key大到数)。
(3)为了保持cur与key之间的数都是大于key值,需要将prev后一位的数据(一定大于key),与小于key值的cur进行交换
(4)最后prev的值一定是小于key的(因为此时prev的值是从小于key的cur值里交换而来的)。所以prev一定小于key。

如果prev和cur中间的数据保持比key大,那么当cur超出范围时,key左边一定小于key,右边一定大于key

代码如下:

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)//区间不可分割时,停止递归
	{
		return;
	}
	int prev = begin;
	int cur = begin + 1;
	int key = begin;

	while (cur < end)//cur没超出区间
	{
		if (a[cur] <= a[key])//当cur小于key的值时
		{
			prev++;
			if (prev != cur)
			{
				Swap(&a[prev], &a[cur]);
			}
		}
		cur++;//不管是大于key还是小于key,cur最后都要++
	}
	Swap(&a[prev], &a[key]);
	key = prev;
	QuickSort(a, begin, key);
	QuickSort(a, key+1, end);
}

非递归的快速排序

前面讲了快排的递归形式,但是递归就说明需要大量的调用堆栈,一旦递归深度过高,就会导致栈溢出,因此有人想出了快速排序的非递归方法。

想要替代递归的作用,就得先找到为什么使用递归以及递归是为了实现什么。

快速排序中的递归起的作用是为了记录分割的区间的起始点与结束点

QuickSort(a, begin, key);
QuickSort(a, key+1, end);

如果我们有办法将每趟快速排序的分割区间记录下来。就能取代递归的作用。

我们可以创建一个栈,用来记录快速排序的区间。这样子就不再需要递归了。

记录的步骤如下:
(1)将左区间和右区间压入栈中
(2)将左区间和右区间弹出。将弹出的数据作为一个区间进行一趟快速排序
(3)完成快速排序后,将新分割好的节点压入栈中
(4)若取出的左右区间不构成新区间,不执行这个操作。
循环往复,直到栈变成空栈。

代码如下:

void QuickSort(int* a, int begin, int end)
{
	stack s1;
	StackInit(&s1);//初始化栈
	StackPush(&s1,begin);//压入左区间
	StackPush(&s1,end);//压入右区间

	while (!StackEmpty(&s1))
	{
		int right = StackTopData(&s1);//出栈
		StackPop(&s1);
		int left = StackTopData(&s1);//出栈
		StackPop(&s1);


		int cur = left+1;
		int prev = left;
		int key = left;

		while (cur < right)
		{
			if (a[cur] < a[key])
			{
				prev++;
				if (prev != cur)
				{
					Swap(&a[cur], &a[prev]);
				}
			}
			cur++;
		}
		Swap(&a[prev], &a[key]);
		key = prev;
		
		//[left,key],[key+1,right]
		if (left < key)
		{
			StackPush(&s1, left);//压入分割后的左区间
			StackPush(&s1, key);//压入分割后的右区间
		}
		if (key + 1 < right)
		{
			StackPush(&s1, key + 1);//压入分割后的左区间
			StackPush(&s1, right);//压入分割后的右区间
		}
	}
	StackDestory(&s1);
}

栈的实现函数

void StackInit(stack* ps)//栈的初始化
{
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackPush(stack* ps, datatype n)//压栈
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		datatype* tmp = (datatype*)realloc(ps->data, sizeof(stack) * newcapacity);
		assert(tmp);
		ps->data = tmp;
		ps->capacity = newcapacity;
	}

	ps->data[ps->top] = n;
	ps->top++;
}

void StackPop(stack* ps)//出栈
{
	if (StackEmpty(ps))
	{
		perror("Stack is empty\n");
		return;
	}

	ps->top--;
}

bool StackEmpty(stack* ps)//判断是否空栈
{
	return ps->top == 0;
}

datatype StackTopData(stack* ps)//取栈顶
{
	if (StackEmpty(ps))
	{
		perror("Stack is empty\n");
		exit(1);
	}
	return ps->data[ps->top - 1];
}

void StackDestory(stack* ps)//销毁栈
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

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

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

相关文章

【软件测试】测试常见知识点汇总

测试常见知识点汇总 一、什么是测试1.1 测试和调试的区别1.2 什么是需求1.2.1 用户需求1.2.2 软件需求 1.3 测试用例要素1.4 软件的生命周期及各阶段概述1.5 开发模型和测试模型&#xff08;记住特点和适用场景&#xff09;1.5.1 开发模型1.5.1.1 瀑布模型&#xff08;自上而下…

解密项目管理工具数据安全:防火防盗,保密有招

相关数据显示&#xff0c;2021年中国数字经济规模总量达到45.5万亿元&#xff0c;占到国内GDP总量的39.8%。数字经济已经渗入我们工作生活的方方面面&#xff0c;项目管理工具就是其中之一&#xff0c;在数据安全备受重视的今天如何保证项目管理工具的数据安全性&#xff1f;Zo…

Linux+HA高可用24X7的安全保证

一&#xff0e; 介绍作为服务器&#xff0c;需要提供一定的24X7的安全保证&#xff0c;这样可以防止关键节点的宕机引起系统的全面崩溃。利用OpenSource开源软件&#xff0c;完成系统的高可靠双机热备方案。基于linux的 HA软件可靠稳定&#xff0c;比使用商业版本的HA软件降低成…

微信小程序python+uniapp高校图书馆图书借阅管理系统ljr9i

根据日常实际需要&#xff0c;一方面需要在系统中实现基础信息的管理&#xff0c;同时还需要结合实际情况的需要&#xff0c;提供图书信息管理功能&#xff0c;方便图书管理工作的展开&#xff0c;综合考虑&#xff0c;本套系统应该满足如下要求&#xff1a; 首先&#xff0c;在…

人工智能基础概念5:使用L1范数惩罚进行Lasso回归(正则化)解决机器学习线性回归模型幻觉和过拟合的原理

一、引言 在老猿CSDN的博文《人工智能基础概念3&#xff1a;模型陷阱、过拟合、模型幻觉》中介绍了通过L1或L2正则化来限制模型的复杂度来解决过拟合的问题&#xff0c;老猿当时并不了解这背后的原理&#xff0c;这2天通过查阅资料终于明白了相关知识&#xff0c;在此一L1正则…

Linux故障排查(亲身经历),Linux运维开发6年了

这里输入数字时注意不要按小键盘&#xff0c;要按键盘字母区上面的那排数字键&#xff1b; 比如我们要关闭pid为2的进程&#xff0c;输入2后按回车&#xff0c;会出现以下提示&#xff0c;此时再按回车就ok 注意 如果执行top命令后&#xff0c;发现没有cpu占用率较高的进程&a…

如何在Linux中安装软件

文章目录 一、Linux应用程序基础1.Linux软件安装包分类2.应用程序和系统命令的关系3.常见的软件包的封装类型 二、安装软件的方式1.RPM包管理工具2.yum安装3.编译 一、Linux应用程序基础 1.Linux软件安装包分类 Linux源码包&#xff1a; 实际上&#xff0c;源码包就是一大堆源…

基于JAVAEE技术校园车辆管理系统论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本校园车辆管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…

python_web1(前端开发之HTML、CSS、Bootstap、Javascript、JQuery)

文章目录 一、Flask网页开发1.1创建一个名为web1.py的python文件1.2 templates目录创建文件index.html 二、html标签2.1 编码2.2title < head >2.3 标题< h>2.4 div和span2.5超链接1.在index.xml文件中补充。2.修改web1.py文件3.添加get_self.html4.效果 2.6图片1.…

Python常用算法思想--回溯算法思想详解【附源码】

通过回溯算法解决“组合”问题、“排序”问题、“搜索”之八皇后问题、“子集和”之0-1背包问题、字符串匹配等六个经典案例进行介绍: 一、解决“组合”问题 从给定的一组元素中找到所有可能的组合,这段代码中的 backtrack_combinations 函数使用了回溯思想,调用 backtrack…

【论文精读】Detecting Out-of-Distribution Examples with Gram Matrices 使用Gram矩阵检测分布外实例

文章目录 一、文章概览&#xff08;一&#xff09;Gram矩阵1、Gram&#xff08;格朗姆&#xff09;矩阵的定义2、Gram矩阵计算特征表示3、风格迁移中的Gram矩阵 &#xff08;二&#xff09;ood检测&#xff08;三&#xff09;核心思路&#xff1a;扩展 Gram 矩阵以进行分布外检…

DHCP工作过程以及抓包分析

从PC1的e0/0/1接口进行抓包 客户端基于UDP、源端口68、目标端口67进行广播请求&#xff0c;源IP0.0.0.0&#xff0c;&#xff08;无效地址&#xff0c;代表本地无地址&#xff09;目标IP255.255.255.255&#xff1b; 从下面截图可以看出&#xff1a; 源mac为电脑mac&#xff…

steam和epic的使用

steam和epic的使用 介绍 这俩都是游戏平台。 登录注册 steam 使用网吧uu加速器打开steam 点击启动游戏&#xff1a;&#xff08;网吧实例&#xff0c;接着点启动&#xff09; 两种方法&#xff1a; 1.直接点内个“创建免费账户”。然后直接注册就行&#xff08;我在网…

论文笔记:UNDERSTANDING PROMPT ENGINEERINGMAY NOT REQUIRE RETHINKING GENERALIZATION

ICLR 2024 reviewer评分 6888 1 intro zero-shot prompt 在视觉-语言模型中&#xff0c;已经取得了令人印象深刻的表现 这一成功呈现出一个看似令人惊讶的观察&#xff1a;这些方法相对不太受过拟合的影响 即当一个提示被手动工程化以在给定训练集上达到低错误率时&#xff0…

【测开求职】校招生在面测开前需要了解的信息

博主在2021年拿到了字节测开实习的offer&#xff0c;实习时长4个月&#xff0c;并于2023年秋招拿到了字节测开的校招offer&#xff0c;仅以本专栏记录对该岗位的所思所想。 目录 1. 测试开发需要做什么工作2. 为什么选择测试开发3. 测试开发不如开发吗4. 如何准备测试开发 1. …

如何使用 Viggle AI 生成模特动作视频

Viggle AI 是一款基于骨骼动画的 AI 工具&#xff0c;可以将图片转换为流畅且一致的角色动画。 这意味着您可以上传一张模特全身照&#xff0c;然后指定该模特要执行的动作&#xff0c;Viggle AI 会自动生成一段由该模特执行该动作的视频。 步骤 1&#xff1a;准备工作 首先&…

【mysql 第3-10条记录怎么查】

mysql 第3-10条记录怎么查 在MySQL中&#xff0c;如果你想要查询第3到第10条记录&#xff0c;你通常会使用LIMIT和OFFSET子句。但是&#xff0c;需要注意的是&#xff0c;LIMIT和OFFSET是基于结果集的行数来工作的&#xff0c;而不是基于记录的物理位置。这意味着它们通常与某种…

栈、队列-栈的概念及结构/栈的实现/栈的顺序存储结构-队列的概念及结构、队列的实现(链式存储结构))

一、栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last In First Out)的原则。 压栈&#xff1a;栈的插入操作…

数学建模----MATLAB----forwhile循环(进阶)

目录 1.for循环的运用 &#xff08;1&#xff09;求和计算 &#xff08;2&#xff09;闰年的判断 &#xff08;3&#xff09;斐波那契数列的计算 &#xff08;4&#xff09;一列数的5个数据一样&#xff0c;删除&#xff0c;5个数据不一样&#xff0c;就保留下来&#xff1…

深入解析:如何使用Xcode上传苹果IPA安装包至App Store?

目录 引言 摘要 第二步&#xff1a;打开appuploader工具 第二步&#xff1a;打开appuploader工具&#xff0c;第二步&#xff1a;打开appuploader工具 第五步&#xff1a;交付应用程序&#xff0c;在iTunes Connect中查看应用程序 总结 引言 在将应用程序上架到苹果应用商…