【数据结构与算法】归并排序(详解:递归与非递归的归并排序 | 赠:冒泡排序和选择排序)

前言

本篇博客会对排序做一个收尾,将最经典的七大排序介绍完毕。

这次的重点正如标题,主要讲的是归并排序,还会带过相对简单很多的冒泡排序和选择排序。在最后还会给这七大排序做出一个时间复杂度和稳定性展示的总结收尾。同时,这也是初阶数据结构的最后一篇。待到再次与数据结构见面时,就会用C++来讲解,因为进阶数据结构相对复杂,用C++会相对轻松一些。话不多说,开始我们今天的内容。

归并排序

归并的思想逻辑

思想:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序核心步骤:

主要可以分为三个步骤: 

  1. 分解
    • 归并排序开始于将待排序的数组不断地“一分为二”,直到每个子数组只包含一个元素。这个过程是递归进行的,即每个子数组也会继续被分解成更小的子数组,直到每个子数组只包含一个元素。
  2. 递归排序与合并
    • 在分解过程完成后,递归地开始合并这些子数组。合并时,会取出两个相邻的子数组,并将它们合并成一个有序的新数组。
    • 合并过程中,会比较两个子数组中的元素,并按照大小顺序依次放入新数组中,直到两个子数组中的所有元素都被考虑完毕。
    • 这个合并过程是递归进行的,每次合并两个子数组,生成的新有序数组又会被视为新的子数组,继续参与后续的合并过程。
  3. 结束条件
    • 当所有子数组都合并完毕,最终得到的数组就是完全有序的。

这个过程可以想象成不断地拆分和组合:首先把一个大问题(排序整个数组)拆分成许多小问题(排序单个元素的子数组),然后解决这些小问题(它们实际上已经是有序的),最后把这些小问题的解(有序的子数组)合并起来,形成最终的大问题的解(完全有序的数组)。这也就是所谓的分治法。

为了更好的理解,这里有一份动图:

在上面的动图中,不知道大家有没有发现一点,归并排序算法并没有直接在原数组上执行,而是借助了一个malloc出来的临时数组。归并排序的核心在于将两个已排序的子数组合并成一个有序的数组。合并过程中,我们需要同时比较两个子数组的元素,并将它们按照大小顺序放入一个新的序列中。这个新的序列通常就是一个临时数组,它用于存储合并后的结果,并且在合并完成后会覆盖或者替换原来的子数组。

如果不使用临时数组,我们就没有一个独立的空间来存储合并后的结果。尝试直接在原数组上进行合并操作会导致数据覆盖和丢失的问题。具体来说,当我们从两个子数组中取出元素并放入原数组时,会破坏那些尚未参与合并的元素的顺序,使得整个排序过程变得混乱。

归并排序的递归性质也要求我们在每个递归层级上都有一个独立的临时空间来存储合并后的结果。如果没有这个临时空间,递归过程将无法进行。基于归并排序的原理和特性,我们必须使用临时数组来实现合并操作。当然,有些优化或变种的排序算法可能会尝试减少临时空间的使用,但它们通常会在算法的其他方面做出妥协,比如增加算法的复杂度或降低排序的稳定性等。

不使用临时数组是无法实现标准的归并排序算法的。临时数组在归并排序中起到了至关重要的作用,它保证了合并操作的正确性和高效性。

归并排序合并代码

这合并代码是归并排序中最底层最重要的逻辑,以图中两段合并为例:

合并过程中,比较两个子数组中的元素,并按照大小顺序依次放入新数组中,直到两个子数组中的所有元素都被考虑完毕。下面为此过程实现代码:

int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end, tmpn = begin;
while (begin1 <= end1 && begin2 <= end2) {
	if (a[begin1] <= a[begin2]) tmp[tmpn++] = a[begin1++];
	else tmp[tmpn++] = a[begin2++];
}
while (begin1 <= end1)tmp[tmpn++] = a[begin1++];
while (begin2 <= end2)tmp[tmpn++] = a[begin2++];
//这部分排完之后,将排好的数从临时tmp数组移回原数组
memmove(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

归并排序递归实现

快速排序中,是先由大组开始排序,再慢慢细分排至无法再细分的小组,类似于二叉树的前序遍历;而归并恰恰相反,在归并排序中,在逻辑上是从末尾开始,将无法细分的小组排成有序,在由有序的小组集合一步步排列成一个有序的大组,最终完成排序,类似于二叉树的后序遍历。有了以上的思考,就会发现归并排序可以用后续的递归来完成这一过程。由于归并的排序思路需要我们创建一个临时数组,我们可以先写一个归并排序框架

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc fail:");
		exit(1);
	}
    //归并排序实现
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

上面代码的_MergeSort()是正真完成归并排序的函数,接下来我们可以看看其中的实现:

void _MergeSort(int* a, int begin, int end, int* tmp)
{
    //当无法再细分时判断退出
	if (begin >= end)return;
	int mid = (begin + end) / 2;
    //递归过程
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end, tmpn = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] <= a[begin2]) tmp[tmpn++] = a[begin1++];
		else tmp[tmpn++] = a[begin2++];
	}
	while (begin1 <= end1)tmp[tmpn++] = a[begin1++];
	while (begin2 <= end2)tmp[tmpn++] = a[begin2++];
	memmove(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

以上就是归并排序递归实现的所有代码。

归并排序非递归实现

见到非递归,你可能会想像实现快速排序非递归那样用栈或者队列实现归并排序的非递归,但可能你需要仔细思考一下,用栈或者队列似乎不好解决二叉树的后序遍历,也就是归并排序这一过程。

  • 首先看队列,队列是先入先出(FIFO)的数据结构,这意味着最早进入队列的元素会最先被取出。在后序遍历中,我们需要在访问根节点之前先访问其左右子树。但是,如果我们使用队列,根节点会先于其子节点被访问,这与后序遍历的顺序不符。因此实现后序先pass掉队列。
  • 再来看栈,栈的结构虽然是后进先出(LIFO)的数据结构,但如果想要找到左右结点,就需要找到其父节点。假使你能通过栈找到,但父节点层可能会有很多同类父节点,想要控制子节点都在父节点之前遍历,是个极其困难的过程,无法单纯通过简单的栈来实现。

所以,我们这里给出的方案是:不使用栈或队列的非递归归并排序实现,可以通过一种自底向上的方式来完成。这种方法通常被称为“迭代归并排序”或“自底向上归并排序”。简单说,就是通过控制循环来实现这一过程。

  1. 初始化
    • 确定待排序数组的长度n
    • 设定一个子数组的大小gap,初始值为1,这表示每个子数组最初只包含一个元素,因此它们自然是有序的。
  2. 合并子数组
    • gap小于n时,重复以下步骤:
      a. 遍历数组,每次以gap为步长,选择两个相邻的子数组进行合并。
      b. 对于每一对相邻的子数组,使用标准的归并过程将它们合并成一个有序数组。
      c. 如果只剩下一个子数组,或者两个子数组的大小不同(因为可能到达数组的末尾),如果end1>=n或者begin2>=n,跳出循环;如果只是end2>=n则改变end2的值为n - 1。
  3. 递增子数组大小
    • gap翻倍,准备在更大的子数组上进行合并操作。
  4. 重复
    • 重复步骤2和3,直到整个数组排序完成。

归并排序非递归代码实现:

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc fail:");
		exit(1);
	}
	int gap = 1;
	while (gap < n) {
		for (int i = 0; i < n; i += gap * 2){
			int begin1 = i, end1 = begin1 + gap - 1, tmpn = begin1;
			int begin2 = end1 + 1, end2 = begin2 + gap - 1;
            //越界处理
			if (end1 >= n || begin2 >= n)break;
			if (end2 >= n) end2 = n - 1;
            //-------
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] <= a[begin2])tmp[tmpn++] = a[begin1++];
				else tmp[tmpn++] = a[begin2++];
			}
			while (begin1 <= end1)tmp[tmpn++] = a[begin1++];
			while (begin2 <= end2)tmp[tmpn++] = a[begin2++];
            //这里需要根据gap和end1的变化控制memmove的空间大小
			memmove(a + i, tmp + i, sizeof(int) * (gap + end2 - end1));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

这个算法的关键在于,它从一个已排序的子数组开始(即单个元素),并通过不断合并相邻的子数组来逐步构建更大的有序数组,直到整个数组排序完成。

这种非递归方法避免了递归调用栈的开销,并且对于大数据集来说可能更加高效。然而,它需要额外的空间来执行归并操作,这与递归版本的归并排序是一样的。

除了需要通过gap控制每一组的间隔,越界处理以及tmp临时数组与原数组之间的空间拷贝大小,其他大部分的内容和递归的实现没什么大的不同。

归并排序特性总结

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4.  稳定性:稳定

以上就是归并排序的所有内容了,接下来两个排序的难度大大降低。

冒泡排序

冒泡排序的思想逻辑

冒泡排序(Bubble Sort)是一种简单的排序算法,其基本思想是通过相邻元素之间的比较和交换,使得每一轮循环后最大(或最小)的元素能够“浮”到数组的一端。这个过程就像气泡一样,逐步将较大的元素“浮”到数组的末尾,因此得名“冒泡排序”。

冒泡排序的逻辑:

  1. 比较相邻的元素:从数组的第一个元素开始,比较相邻的两个元素。如果前一个元素大于后一个元素,则交换它们的位置。
  2. 逐步推进:每一对相邻元素进行比较和可能的交换后,最大的元素就会像气泡一样“浮”到当前序列的末尾。这个过程在每一轮循环中都会发生。
  3. 多轮比较:由于每轮循环只能确保一个最大(或最小)的元素移到正确的位置,因此需要对整个数组进行多轮比较,直到整个数组排序完成。
  4. 优化:为了提高效率,可以在每一轮循环后检查是否有过交换操作。如果在某一轮循环中没有进行过任何交换,说明数组已经是有序的,此时可以提前终止排序过程。

这里有一份动图帮助理解:

冒泡排序的步骤:

  1. 从数组的第一个元素开始,比较相邻的两个元素。
  2. 如果前一个元素大于后一个元素,则交换它们的位置。
  3. 继续比较下一对相邻元素,直到到达数组的末尾。
  4. 完成一轮比较后,最大的元素将被放置在数组的末尾。
  5. 重复上述步骤,但忽略已经排序好的末尾部分,直到整个数组排序完成。

冒泡排序代码实现

作为最简单好理解的排序方式之一,这里直接附上代码。

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++) {
		int exchange = 0; // 优化,如果判断无交换则排序结束
		for (int i = 1; i < n - j; i++) {
			if (a[i - 1] > a[i]) {
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)break;
	}
}

冒泡排序特性总结

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2) 
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

选择排序(直接选择排序)

选择排序思想逻辑

直接选择排序(Straight Select Sorting),也叫简单选择排序,是一种简单直观的排序算法。其工作原理是,每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

对于直接选择排序每次只选一个最小值,我们给出一种优化方案,每次遍历选两个数,一个最大值和一个最小值,可以看下其运行逻辑:

  1. 初始化
    • 设定两个变量来记录当前遍历过程中的最小值和最大值,以及它们对应的索引位置。
  2. 查找最大和最小值
    • 遍历整个序列,比较每个元素,更新最小值和最大值的记录。
    • 记录最小值和最大值对应的索引位置。
  3. 交换位置
    • 将起始预留位置和最小下标索引处交换。
    • 将末尾预留位置与最大下标索引处交换。
    • 如果最大值索引正好在刚才最小值索引的位置,则需要在交换最小值之后改变最大值索引的位置,再进行交换。
  4. 缩减范围并重复
    • 排除已经放置好的最大值和最小值,缩减查找范围,然后重复步骤2和3,直到整个序列有序。

注:

  • 每一轮排序后,最大值和最小值分别被放置在了序列的两端,因此下一轮的查找范围可以缩小。
  • 如果最大值和最小值相邻,并且最小值位于序列的开始位置,交换最大值到末尾后,需要改变最小值的索引,因为它已经被移动到了原本最大值的位置。

选择排序代码实现

也是作为最简单好理解的排序方式之一,这里直接附上代码。

void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right) {
		int mini = left, maxi = right;
		for (int i = left; i <= right; i++) {
			if (a[i] < a[mini])mini = i;
			if (a[i] > a[maxi])maxi = i;
		}
		Swap(&a[mini], &a[left]);
		if (left == maxi) maxi = mini;
		Swap(&a[maxi], &a[right]);
		left++;
		right--;
	}
}

选择排序特性总结

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

关于直接选择不稳定的原因,我们拿一趟排一个数的思路来举例:

如果我们有一个序列[5, 8, 5, 2, 9],在第一轮排序后,第一个5会和2交换位置,导致原本在后面的5排到了前面,从而破坏了稳定性。

尽管直接选择排序在算法逻辑上相对简单,但由于其时间复杂度较高,在处理大规模数据时可能不是最优选择。在实际应用中,更高效的排序算法如归并排序、快速排序等通常会被优先考虑。

七大排序算法复杂度及稳定性

 什么?你说我还没讲堆排序?看看这篇博客:初阶数据结构之---堆的应用(堆排序和topk问题)-CSDN博客

你问我什么是稳定性?好吧,这里再回顾一下。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

简单来说就是:在一定的规则下,两个值相等的元素,在排序算法处理前后的相对位置是否发生变化,如果相对位置变化,称这种排序算法是稳定的,否则为不稳定的。

结语

本篇博客对归并排序,冒泡排序和直接插入排序做了深入分析和讲解,最后展示了七大经典排序的算法复杂度和稳定性。掌握排序是一个程序员的基本素养,对开拓思维也有很大的帮助。数据结构初阶相关的所有内容到这里就结束了,在进入进阶数据结构之前,我会写一些关于C++的基础语法的内容做一个过度,希望能帮助到大家。

感谢支持,博主后续会产出更多有意思的内容!♥

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

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

相关文章

钉钉事件订阅前缀树算法gin框架解析

当钉钉监测到发生一些事件&#xff0c;如下图 此处举例三个事件user_add_org、user_change_org、user_leave_org&#xff0c;传统的做法是&#xff0c;我们写三个if条件&#xff0c;类似下图 这样字符串匹配效率比较低&#xff0c;于是联想到gin框架中的路由匹配算法&#xff0…

非写代码无以致远

标题党一下&#xff0c;本篇文章主要汇总了一些代码题&#xff0c;让大家写一些代码练习一下吧&#xff01; 变种水仙花_牛客题霸_牛客网 (nowcoder.com) #include<stdio.h> int main() {for (int i 10000; i < 99999; i) {int sum 0;for (int j 10; j < 1000…

码农失业倒计时?全球首个大厂AI程序员来了

进入互联网时代&#xff0c;程序员作为高收入职业的代表&#xff0c;长久以来一直是众多求职者梦寐以求的工作方向。程序员们凭借其对计算机科学的深刻理解和技术创新能力&#xff0c;不仅推动了科技的进步&#xff0c;也为自己赢得了可观的经济回报。 然而&#xff0c;随着人…

AD20全流程的使用笔记

目录 首先一个完整的AD工程文件需要我们自己建立的文件有这些&#xff1a; 新建工程&#xff1a; 从现有的工程文件中将元件添加到原理图库&#xff1a; 元件的摆放&#xff1a; 器件的复制及对齐&#xff1a; 导线、Netlabe、端口的添加&#xff1a; Value值的校对&…

可视化大屏 - 项目1

文章目录 技术栈echarts 可视化需求分析代码实现 技术栈 flexible.js rem 实现不同终端下的响应式布局&#xff0c;根据不同屏幕宽度&#xff0c;自适配布局&#xff1b; html中引入index.js&#xff0c;可以改名为flexible.js&#xff1b;默认划分10份&#xff0c;可以自己修…

HarmonyOS 应用开发之TaskPool和Worker的对比 (TaskPool和Worker)

TaskPool&#xff08;任务池&#xff09;和Worker的作用是为应用程序提供一个多线程的运行环境&#xff0c;用于处理耗时的计算任务或其他密集型任务。可以有效地避免这些任务阻塞主线程&#xff0c;从而最大化系统的利用率&#xff0c;降低整体资源消耗&#xff0c;并提高系统…

日期专题:做题笔记 (时间显示/星期计算/星系炸弹/第几天/纪念日)

目录 时间显示 代码 星期计算 代码 星系炸弹 代码 第几天 纪念日 代码 时间显示 时间显示 这道题主要是单位换算。 ①单位换算 ②输出格式&#xff1a; a. 不足两位补前导零。利用printf输出 b. 注意 long long 输出格式应该是 %lld 长整型 代码 #include <…

Day66-企业级防火墙iptables精讲2

Day66-企业级防火墙iptables精讲2 1. iptables项目案例2&#xff1a;局域网共享上网&#xff1a;2. iptables项目案例3&#xff1a;外网IP的端口映射到内网IP的端口3. 老男孩教育iptables项目案例4&#xff1a;IP一对一映射&#xff08;DMZ&#xff09;4. 老男孩教育iptables项…

Java常用类和基础API

文章目录 1. 字符串相关类之不可变字符序列&#xff1a;String1.1 String的特性1.2 String的内存结构1.2.1 概述1.2.2 练习类型1&#xff1a;拼接1.2.3 练习类型2&#xff1a;new1.2.4 练习类型3&#xff1a;intern() 1.3 String的常用API-11.3.1 构造器1.3.2 字符串对象的比较…

【THM】Protocols and Servers(协议和服务器)-初级渗透测试

介绍 这个房间向用户介绍了一些常用的协议,例如: HTTP协议文件传输协议POP3邮件传输协议IMAP每个协议的每个任务都旨在帮助我们了解底层发生的情况,并且通常被优雅的GUI(图形用户界面)隐藏。我们将使用简单的 Telnet 客户端来使用上述协议进行“对话”,以充分了解GUI客户…

Unity开发一个FPS游戏之三

在前面的两篇博客中&#xff0c;我已实现了一个FPS游戏的大部分功能&#xff0c;包括了第一人称的主角运动控制&#xff0c;武器射击以及敌人的智能行为。这里我将继续完善这个游戏&#xff0c;包括以下几个方面&#xff1a; 增加一个真实的游戏场景&#xff0c;模拟一个废弃的…

5.2 通用代码,数组求和,拷贝数组,si配合di翻转数组

5.2 通用代码&#xff0c;数组求和&#xff0c;拷贝数组&#xff0c;si配合di翻转数组 1. 通用代码 通用代码类似于一个用汇编语言写程序的一个框架&#xff0c;也类似于c语言的头文件编写 assume cs:code,ds:data,ss:stack data segmentdata endsstack segmentstack endsco…

刘小光本就疑心赵本山与他媳妇李琳有染,赵本山为证实清白便想起蛋糕上的字,结果呢?

刘小光本就疑心赵本山与他媳妇李琳有染&#xff0c;赵本山为证实清白便想起蛋糕上的字&#xff0c;结果呢&#xff1f; ——小品《生日快乐》&#xff08;中5&#xff09;的台词 &#xff08;接上&#xff09; 赵本山&#xff1a;噢!对对!那谁&#xff0c;老四&#xff0c;是…

GEE错误——土地分类中出现Line 126:composite.select(...).classify is not a function

错误 Line 126:composite.select(...).classify is not a function 出现 "GEE在土地分类中出现的一个问题... is not a function" 的主要原因可能有几种 1. 变量或函数名拼写错误:检查代码中的该函数或变量名是否正确拼写,包括大小写。 2. 函数或变量未声明:检查…

Docker,anaconda环境的部署与迁移

功能上线将提上日程&#xff0c;但是如何将我windows环境下的程序放到linux服务器的测试环境跑通呢&#xff1f;这是我这整个清明假期将要解决的一件事&#xff0c;最蠢的办法就是看自己的环境下有哪些依赖&#xff0c;如何到服务器上一个一个下&#xff0c;但是首先这个方法很…

Brain.js 的力量:构建多样化的人工智能应用程序

机器学习&#xff08;ML&#xff09;是人工智能 (AI) 的一种形式&#xff0c;旨在构建可以从处理的数据中学习或使用数据更好地执行的系统。人工智能是模仿人类智能的系统或机器的总称。 机器学习&#xff08;ML&#xff09;与复杂的数学纠缠在一起&#xff0c;让大多数初学者…

逻辑代数点

文章目录 与或非与非 或非 与或非异或同或布尔恒等式代入定理例子例子 反演定理例子例子:例子: 真值表 与 逻辑式&#xff1a;逻辑式 与 逻辑图最小项例子:最小项编号最小项性质最小项之和 最大项最大项性质最大项编号 逻辑代数的化简公式化简法卡诺图化简法表示逻辑代数用卡诺…

【蓝桥备赛】异或和——树状数组、DFS

题目链接 异或和 思路分析 树上每个点都有一个点权&#xff0c;对树上的更新操作是修改指定点的点权&#xff0c;查询操作是查询指定点为根结点的子树点权异或和。 这里的这些操作都和树状数组的单点修改和区间查询非常相似&#xff0c;即我们在修改一个点时&#xff0c;同时…

Three.js——scene场景、几何体位置旋转缩放、正射投影相机、透视投影相机

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…

医院云HIS系统源码,二级医院、专科医院his系统源码,经扩展后能够应用于医联体/医共体

基于云计算技术的B/S架构的HIS系统&#xff0c;为医疗机构提供标准化的、信息化的、可共享的医疗信息管理系统&#xff0c;实现医患事务管理和临床诊疗管理等标准医疗管理信息系统的功能。 系统利用云计算平台的技术优势&#xff0c;建立统一的云HIS、云病历、云LIS&#xff0…