排序 “叁” 之交换排序

目录

1. 基本思想

2.冒泡排序

2.1 基本思想

2.2 代码示例

2.3 冒泡排序的特性总结

3.快速排序

3.1 基本思想

🌵hoare版本

🌵挖坑法

​编辑

🌵前后指针版本

​编辑

3.2 快速排序优化

🌻三数取中法选key

3.4 快速排序的特性总结

1. 基本思想

        所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.冒泡排序

2.1 基本思想

冒泡排序是一种简单直观的排序算法，其基本思想是通过不断比较相邻的元素并交换位置，将最大（或最小）的元素逐步“冒泡”到最后（或最前）。

冒泡排序的具体步骤：

  1. 比较相邻元素：从数组的第一个元素开始，依次比较相邻的两个元素，如果顺序不对则交换它们的位置，确保较大的元素向后移动。
  2. 一轮冒泡：经过一轮比较和交换操作，最大的元素会沉到数组的最后位置。重复这个过程，直到没有需要交换的元素为止。
  3. 多轮冒泡：重复进行上述步骤，每次冒泡操作都会将当前未排序部分的最大元素移动到正确的位置。经过多轮冒泡，整个数组就会逐步有序。
  4. 优化：可以在每一轮冒泡中记录是否有元素交换的标志，如果某一轮没有元素交换，说明数组已经有序，可以提前结束排序。

下面是一个简单的示例，演示冒泡排序的步骤：

假设要排序的数组为：[5, 3, 8, 2, 1]

  • 第一轮冒泡：比较并交换，数组变为 [3, 5, 2, 1, 8]
  • 第二轮冒泡：比较并交换，数组变为 [3, 2, 1, 5, 8]
  • 第三轮冒泡：比较并交换，数组变为 [2, 1, 3, 5, 8]
  • 第四轮冒泡：比较并交换，数组变为 [1, 2, 3, 5, 8]

经过四轮冒泡排序，数组变为有序状态：[1, 2, 3, 5, 8]。

2.2 代码示例

//交换
void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//标志位，用于记录本轮是否发生了元素交换
		bool flag = false;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j + 1] < a[j])
			{
				//交换相邻元素
				Swap(&a[j + 1], &a[j]);
				flag = true;
			}
		}
		//如果本轮没有发生元素交换，说明数组已经有序，提前结束排序
		if (!flag)
			break;
	}
}

//打印
void PrintSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//测试
int main()
{
	int a[] = { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintSort(a, sizeof(a) / sizeof(int));

	return 0;
}

2.3 冒泡排序的特性总结

  1. 时间复杂度：冒泡排序的平均时间复杂度为O(n^2)，最坏情况下为O(n^2)，最好情况下为O(n)。因此，冒泡排序对于大规模数据集并不是一个高效的选择。
  2. 空间复杂度：冒泡排序的空间复杂度为O(1)，因为它只需要一个额外的临时变量来进行元素交换。
  3. 稳定性：冒泡排序是一种稳定的排序算法，相同元素的相对位置在排序前后不会改变。
  4. 适用场景：由于冒泡排序的效率较低，通常不推荐在实际应用中使用。但对于小规模数据集或者教学目的，冒泡排序是一个很好的入门算法。
  5. 优缺点：冒泡排序的优点是实现简单，代码易于理解；缺点是效率低下，不适用于大规模数据集。

3.快速排序

3.1 基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，它的核心思想是通过分治法来实现排序。

具体步骤如下：

  1. 选择一个基准值（通常选择第一个元素）。
  2. 将小于基准值的元素移到基准值的左边，将大于基准值的元素移到基准值的右边。
  3. 对基准值左右两侧的子数组分别递归地进行快速排序。

将区间按照基准值划分为左右两半部分的常见方式有：

🌵hoare版本

思想步骤：

  1. 选择一个基准元素（通常选择数组的中间元素）。
  2. 使用两个指针，一个指向数组的起始位置，另一个指向数组的末尾位置。
  3. 右指针向左移动，直到找到一个小于基准元素的元素。
  4. 左指针向右移动，直到找到一个大于基准元素的元素。
  5. 左右指针分别找到元素后，交换它们各自位置的数值。
  6. 重复步骤3到步骤5，直到左指针和右指针相遇，将该位置的值与基准元素位置的值交换。
  7. 此时基准元素左边的元素都小于等于它，右边的元素都大于等于它。
  8. 递归地对基准元素左右两边的子数组进行快速排序。

//交换
void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

//快速排序
void QuickSort(int* a, int begin, int end)
{
	//如果子数组长度为1或0，则直接返回
	if (begin >= end)
		return;

	//初始化左右指针和基准值
	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[right], &a[left]);
	}
	//将基准元素放到正确的位置上
	Swap(&a[left], &a[keyi]);
	keyi = left;
	//递归的对基准元素左右两侧的子数组进行快速排序
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

//打印
void PrintSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//测试
int main()
{
	int a[] = { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintSort(a, sizeof(a) / sizeof(int));

	return 0;
}

🌵挖坑法

思想步骤：

  1. 先将第一个数据存放在临时变量key中，形成一个坑位。
  2. right开始向前移动，找比key位置小的值，找到后将right位置的值放进坑里，此时right位置作为新的坑。
  3. left开始向后移动，找比key位置大的值，找到后将left位置的值放进坑里，此时left位置作为新的坑。
  4. right接着向前找，left接着向后找，直到left与right相遇。
  5. 将key放入相遇时的坑里，排序完毕。

// 挖坑法
int PartSort(int* a, int begin, int end)
{

	//选择第一个元素作为基准元素
	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;
}

void QuickSort(int* a, int begin, int end)
{
	//如果子数组长度为1或0，则直接返回
	if (begin >= end)
		return;

	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

//打印
void PrintSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


//测试
int main()
{
	int a[] = { 1, 5, 7, 9, 0, 1, 2, 4, 8, 1, 3, 8, 6 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintSort(a, sizeof(a) / sizeof(int));

	return 0;
}

 

🌵前后指针版本

思想步骤：

  1. 选择一个基准元素作为key（通常选择数组的第一个元素）。
  2. 使用两个指针，前指针prev指向序列开头，后指针cur指向prev指针的后一个位置。
  3. 判断cur指针指向的数据是否小于key，若小于，则prev指针后移一位（注意：prev只有在cur找到比key小的数时才加1），并将cur指向的内容与prev指向的内容交换，然后cur指针++。若大于，则cur指针++。
  4. 依次类推直到cur遍历完整个数组，最后将prev位置的值与key位置的值进行交换，则完成单趟排序。

//交换
void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

//前后指针法
int PartSort(int* a, int begin, int end)
{
	int key = begin;

	int prev = begin;
	int cur = prev + 1;

	while (cur <= end)
	{
		//如果cur位置的值小于key位置的值，
		//并且prev位置++后的值如果和cur位置的值不相等，
		//就交换prev位置和cur位置的值
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}

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

	return key;
}


void QuickSort(int* a, int begin, int end)
{
	//如果子数组长度为1或0，则直接返回
	if (begin >= end)
		return;

	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}


3.2 快速排序优化

🌻三数取中法选key

三数取中法是在快速排序算法中用于选择基准元素的一种策略。它的思想是从待排序数组中随机选择三个元素，然后取它们的中间值作为基准元素，这样可以尽量避免选择到极端的值作为基准元素，从而提高快速排序的效率。

使用三数取中法选择基准元素的具体步骤：

  1. 从待排序数组中随机选择三个元素，通常是选择数组的第一个元素、中间元素和最后一个元素。
  2. 比较这三个元素，找到它们的中间值作为基准元素。可以使用简单的比较排序或者其他方法来找到中间值。
  3. 将选定的基准元素放置在数组的最左边（或者其他位置），并记录其值。
  4. 接下来的快速排序过程中，使用这个选定的基准元素进行分区操作，将小于基准元素的元素放在左边，大于基准元素的元素放在右边。

使用三数取中法选择基准元素可以有效地避免选择到极端值作为基准元素，从而提高快速排序的效率，减少最坏情况下的时间复杂度。这种方法在实际应用中被广泛采用，用以提高快速排序的性能。

🍂代码示例：

//交换
void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

//三数取中
int GetMidi(int* a, int begin, int end)
{
	//选择三个元素的中间值作为基准元素
	int midi = (begin + end) / 2;

	//确保 a[begin] <= a[midi] <= a[end]
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else //a[begin] > a[midi]
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}

//快速排序
void QuickSort(int* a, int begin, int end)
{
	//如果子数组长度为1或0，则直接返回
	if (begin >= end)
		return;

	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[right], &a[left]);
	}
	//将基准元素放到正确的位置上
	Swap(&a[left], &a[keyi]);
	keyi = left;
	//递归的对基准元素左右两侧的子数组进行快速排序
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

//测试
int main()
{
	int a[] = { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintSort(a, sizeof(a) / sizeof(int));

	return 0;
}

3.4 快速排序的特性总结

  1. 时间复杂度：平均时间复杂度为O(N*logN)，最坏情况下为O(N^2)，最好情况下为O(N*logN)。
  2. 空间复杂度：快速排序是一种原地排序算法，不需要额外的存储空间，空间复杂度为O(1)。
  3. 稳定性：快速排序是一种不稳定的排序算法，即相同元素的相对位置可能会发生变化。
  4. 分治思想：快速排序使用分治思想，将数组分为两部分，分别对左右子数组进行排序。

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

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

相关文章

HAL STM32 SSI/SPI方式读取MT6701磁编码器获取角度例程

HAL STM32 SSI/SPI方式读取MT6701磁编码器获取角度例程

HAL STM32 SSI/SPI方式读取MT6701磁编码器获取角度例程 &#x1f4cd;相关篇《HAL STM32 I2C方式读取MT6701磁编码器获取角度例程》&#x1f4cc;当前最新MT6701数据手册&#xff1a;https://www.magntek.com.cn/upload/MT6701_Rev.1.8.pdf&#x1f4dc;SSI协议读角度&#xff…
阅读更多...
flutter 实现表单的封装包含下拉框和输入框

flutter 实现表单的封装包含下拉框和输入框

一、表单封装组件实现效果 //表单组件 Widget buildFormWidget(List<InputModel> formList,{required GlobalKey<FormState> formKey}) {return Form(key: formKey,child: Column(children: formList.map((item) {return Column(crossAxisAlignment: CrossAxisAlig…
阅读更多...
4月21日Linux运维用户相关的添加，分组，修改权限等shell脚本开发第一天

4月21日Linux运维用户相关的添加，分组，修改权限等shell脚本开发第一天

4月21日运维用户相关的添加&#xff0c;分组&#xff0c;修改权限等shell脚本开发第一天 第一天主要实现前2个功能 ​ 主要卡在了&#xff1a; 正确的写法如下&#xff0c;注意[]中的空格&#xff0c;要求很严格&#xff01;&#xff01;&#xff01; #!/bin/bash # 先查看已…
阅读更多...
LIUNX系统编程：文件系统

LIUNX系统编程：文件系统

目录 1.创建文件的本质 1.1目录本身也是一个文件&#xff0c;也有他自己的inode 1.2LINUX创建文件&#xff0c;一定是在目录中创建文件。 2.重谈文件的增删查改 2.1为什目录没有写权限&#xff0c;就不能新建文件。 2.2.文件的查找 3.路径 3.1挂载 3.2如何理解挂载 1.创…
阅读更多...
【QT学习】8.qt事件处理机制，事件过滤器，自定义事件

【QT学习】8.qt事件处理机制，事件过滤器，自定义事件

1.qt事件处理机制 事件处理&#xff1a; 当用户移动鼠标的时候 &#xff0c;创建一个 鼠标移动事件对象 然后把这个对象放到 事件队列里面去&#xff0c;事件管理器 从队列中 取出事件&#xff0c;然后 调用其对应的事件处理函数。 多态机制&#xff1a; &#x…
阅读更多...
2023年图灵奖颁发给艾维·维格森（Avi Wigderson），浅谈其计算复杂性理论方面做出的重要贡献

2023年图灵奖颁发给艾维·维格森（Avi Wigderson），浅谈其计算复杂性理论方面做出的重要贡献

Avi Wigderson是一位以色列计算机科学家&#xff0c;他在计算复杂性理论方面做出了重要的贡献&#xff0c;并对现代计算产生了深远的影响。 Wigderson的主要贡献之一是在证明计算复杂性理论中的基本问题的困难性方面。他证明了许多经典问题的困难性&#xff0c;如图论中的图同构…
阅读更多...
Day08React——第八天

Day08React——第八天

useEffect 概念&#xff1a;useEffect 是一个 React Hook 函数&#xff0c;用于在React组件中创建不是由事件引起而是由渲染本身引起的操作&#xff0c;比如发送AJAx请求&#xff0c;更改daom等等 需求&#xff1a;在组件渲染完毕后&#xff0c;立刻从服务器获取频道列表数据…
阅读更多...
每天五分钟机器学习：神经网络模型参数的选择

每天五分钟机器学习：神经网络模型参数的选择

本文重点 在深度学习和人工智能的浪潮中，神经网络作为其中的核心力量，发挥着举足轻重的作用。然而，神经网络的性能并非一蹴而就，而是需要经过精心的参数选择和调优。 神经网络由大量的神经元组成，每个神经元之间通过权重进行连接。这些权重，以及神经元的偏置、激活函数…
阅读更多...
Adobe Acrobat PDF 2024

Adobe Acrobat PDF 2024

Adobe Acrobat PDF 2024正式发布&#xff01;支持Windows和macOS系统&#xff0c;新界面做了轻微调整。 下载地址 Windows客户端&#xff1a;https://www.123pan.com/s/f43eVv-GKZKd.html macOS客户端&#xff1a;https://www.123pan.com/s/f43eVv-PKZKd.html
阅读更多...
idea在controller或者service使用ctrl+alt+b进入方法后，如何返回到 进入前的那一层

idea在controller或者service使用ctrl+alt+b进入方法后，如何返回到 进入前的那一层

idea在controller或者service使用ctrlaltb进入方法后&#xff0c;如何返回到进入方法的最外层 解决方案使用 ctrlalt ← /→← /→ 键盘上的左右键盘
阅读更多...
数据结构练习-算法与时间复杂度

数据结构练习-算法与时间复杂度

----------------------------------------------------------------------------------------------------------------------------- 1. 设n是描述问题规模的非负整数&#xff0c;下列程序段的时间复杂度是( )。 x0;while(n>(x1)*(x1)xx1; A.O(logn) B.O(n^(1/2)) C.O(n)…
阅读更多...
【周总结】总结下这周的工作、（hashmap)知识巩固等

【周总结】总结下这周的工作、（hashmap)知识巩固等

总结 这周开发任务已经全部结束&#xff0c;主要是在修改一些 jira 问题 需要反思的是&#xff0c;中间改造接口时&#xff0c;数据库表需要新增一个字段&#xff0c;这个 sql 脚本忘记加到 basetable.sql 脚本里面了&#xff0c;这样如果是新建的项目&#xff0c;创建的时候不…
阅读更多...
百万级别mysql性能耗时自测

百万级别mysql性能耗时自测

注&#xff1a;实际情况会因建表语句和服务器的配置造成偏差 测试环境 &#xff1a;8核CPU 16G运行内存 建表语句&#xff1a; CREATE TABLE user (id bigint(11) NOT NULL AUTO_INCREMENT,username varchar(255) COLLATE utf8mb4_bin DEFAULT NULL,birthday varchar(255)…
阅读更多...
AppWizard的软件开发GUI的使用记录

AppWizard的软件开发GUI的使用记录

前言 这个软件是针对于EmWin6.0以上的这个软件在emWin的基础上又封装了一层,也只提供的API函数.基于消息事件为核心&#xff08;个人理解&#xff09;一些组件的之间的交互可以通过软件界面进行配置,比较方便本次是基于模拟器进行测试记录,观察api 按键和文本之间的关联 通过…
阅读更多...
软考141-上午题-【软件工程】-杂题+小结

软考141-上午题-【软件工程】-杂题+小结

一、杂题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 真题6&#xff1a; 真题7&#xff1a; 真题8&#xff1a; 真题9&#xff1a; 真题10&#xff1a; 真题11&#xff1a; 真题12&#xff1a; 真题13&#xff1a; 真题14&a…
阅读更多...
深入剖析Spring框架：循环依赖的解决机制

深入剖析Spring框架：循环依赖的解决机制

你好&#xff0c;我是柳岸花开。 什么是循环依赖&#xff1f; 很简单&#xff0c;就是A对象依赖了B对象&#xff0c;B对象依赖了A对象。 在Spring中&#xff0c;一个对象并不是简单new出来了&#xff0c;而是会经过一系列的Bean的生命周期&#xff0c;就是因为Bean的生命周期所…
阅读更多...
05集合-CollectionListSet

05集合-CollectionListSet

Collection体系的特点、使用场景总结 如果希望元素可以重复&#xff0c;又有索引&#xff0c;索引查询要快? 用ArrayList集合, 基于数组的。(用的最多) 如果希望元素可以重复&#xff0c;又有索引&#xff0c;增删首尾操作快? 用LinkedList集合, 基于链表的。 如果希望增…
阅读更多...
亚马逊测评自养号策略：手机与PC结合的重要性

亚马逊测评自养号策略：手机与PC结合的重要性

亚马逊测评的核心关键技术在于精心培养买家账号&#xff0c;之所以称之为核心关键&#xff0c;原因在于测评下单的首要条件是拥有一个活跃的买家账号。买家账号并非一次性使用&#xff0c;因此&#xff0c;养号过程显得至关重要。然而&#xff0c;在养号的过程中&#xff0c;很…
阅读更多...
Python基础03-深入探索Python字典操作

Python基础03-深入探索Python字典操作

在Python中&#xff0c;字典是一种非常强大和灵活的数据结构&#xff0c;可以存储键值对&#xff0c;并提供了许多方法来操作这些键值对。本文将深入探讨Python字典的各种操作&#xff0c;包括如何创建、修改、合并和查找字典中的元素。 1. 创建字典 要创建一个字典&#xff…
阅读更多...
【数字电路与系统】【北京航空航天大学】实验：时序逻辑设计——三色灯开关（三）、功能仿真测试

【数字电路与系统】【北京航空航天大学】实验：时序逻辑设计——三色灯开关（三）、功能仿真测试

本次实验&#xff08;一&#xff09;见博客&#xff1a;【数字电路与系统】【北京航空航天大学】实验&#xff1a;时序逻辑设计——三色灯开关&#xff08;一&#xff09;、实验指导书 本次实验&#xff08;二&#xff09;见博客&#xff1a;【数字电路与系统】【北京航空航天…
阅读更多...
最新文章

Copyright @ 2022~2023