首页 > 其他分享 >快速排序的三种实现及简单优化(内附代码实现)

快速排序的三种实现及简单优化(内附代码实现)

时间:2024-03-04 19:44:32浏览次数:26  
标签:right 实现 内附 基准 元素 指针 int 排序 left

概念

​ 先贴一段百度:快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素key,利用key将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。

步骤

1.从待排序的数列中选择一个基准值,称为key值

2.重新排列数列,所有比基准值小的数放到基准左边,所有比基准值大的数放到基准右边,(相同的数随意放那边都行)。在这一次排序过后,该基准就处于数列的中间位置。这个称为分区操作

3.递归的重复执行上一步基准值的左右数列,递归到最后,数组的长度是1时,也就是已经排好序。

补充

1、快速排序采取的是分治法的思想,可以看到每次分区操作都是将一个序列分解为两个序列,当序列长度为0或者1时,则此序列是排好序的。

2、快速排序算法是不稳定的,何为不稳定,何为稳定,不稳定指对于在序列中两个相同的元素,在排序后他们的前后顺序发生了变化,而稳定则相反,有些人可能会想,我两个元素都是相同的,谁前谁后不都一样吗?但在实际的开发中,真实情况往往是复杂的,比如:对一组学生元素进行排序,要求先按照学号进行排序,再按照成绩进行排序,如果第二次排序采用的是不稳定的排序算法,将导致成绩相同的学生学号不是有序的。

待排序序列

image-20240304154125719

左右指针法

1、选取基准,例如选取第一个元素作为基准,申明左右指针分别指向数组的头尾

image-20240304183250045

2、将右指针向左移动,当当前元素小于基准时停下

image-20240304183250045

3、将左指针向右移动,当当前元素大于基准时停下

image-20240304183440865

4、将两个指针的值进行交换

image-20240304183647499

5、循环2-4步骤,直到左右指针相遇

image-20240304183803883

6、将基准值跟指针指向位置的值进行交换

image-20240304183912924

至此,基准的左边元素都小于等于基准,基准的右边元素都大于等于基准,再递归将左右子数组也按照刚才的步骤处理即可。

实现代码如下:

void Swap(int* tmp1, int* tmp2)
{
	int tmp = *tmp1;
	*tmp1 = *tmp2;
	*tmp2 = tmp;
}

void PartSort(int* a, int left, int right)
{
	//递归终止条件
	if (left >= right)
	{
		return;
	}
	//单次快排
	int begin = left, end = right;
    //取基准值
	int keyi = begin;
	while (begin < end)
	{
		//从右指针开始向左找比基准值小的数
		while (begin < end && a[end] >= a[keyi])
		{
			end--;
		}
		//从左指针开始向右找比基准值大的数
		while (begin < end && a[begin] <= a[keyi])
		{
			begin++;
		}
		//交换两个指针找到的数
		Swap(&a[begin], &a[end]);
	}
	//最后交换,将基准值换到两个指针的位置
	Swap(&a[begin], &a[keyi]);

	//递归放好位置的基准值左右边即可
	PartSort(a, left, begin);
	PartSort(a, begin + 1, right);
}

挖坑法

1、选取基准,例如选取第一个元素作为基准(把基准挖掉),申明左右指针分别指向数组的头尾

image-20240304190443831

2、将右指针向左移动,当当前元素小于基准时停下,并将当前元素挖走,填到左指针指向的位置(坑)

image-20240304190553594

3、将左指针向右移动,当当前元素大于基准时停下,并将当前元素挖走,填到右指针指向的位置(坑)

image-20240304190632743

4、继续走第2跟第3步,直到左指针跟右指针相等

image-20240304190903848

5、再将基准填到指针指向的位置

image-20240304190926607

至此,基准的左边元素都小于等于基准,基准的右边元素都大于等于基准,再递归将左右子数组也按照刚才的步骤处理即可。

代码实现如下:

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	int povit = begin;
    //q
	int key = a[begin];

	while (begin < end)
	{
		//从右边找比key小的放到左边坑里
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		//右边的放到左边坑,因此右边有坑了
		a[povit] = a[end];
		povit = end;
		//从左边找比key大的值放到右边坑里
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		//左边的放到右边坑里,坑更新到左边
		a[povit] = a[begin];
		povit = begin;
	}
	//将基准值放到两指针交界处
	a[begin] = key;

	QuickSort(a, left, povit - 1);
	QuickSort(a, povit + 1, right);
}

快慢指针法

1、选取基准,例如选取第一个元素作为基准,申明pre指针(前指针)指向序列开头(index=0),cur指针(后指针)则为pre+1

image-20240304191750983

2、将cur指针向右移动,直到遇到比基准小的元素

image-20240304191833580

3、将pre指针向右移动一位(+1),如果pre跟cur不相等,则交换两个指针的元素

image-20240304191933699

4、继续重复2-3步骤,直到cur指针到序列尾

image-20240304192059373

5、将pre指针位置的元素跟基准进行交换

image-20240304192154816

至此,基准的左边元素都小于等于基准,基准的右边元素都大于等于基准,再递归将左右子数组也按照刚才的步骤处理即可。

代码实现如下:

void Swap(int* tmp1, int* tmp2)
{
	int tmp = *tmp1;
	*tmp1 = *tmp2;
	*tmp2 = tmp;
}

void PartSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
    //取基准值
	int keyi = left;
	int cur = left, prev = left;

	//终止条件为cur指针到尾部
	while (cur < right)
	{
		//快指针先走
		cur++;
		//找到比基准值小的数
		while (a[cur] < a[keyi])
		{
			//慢指针向右移动
			prev++;
			//交换
			Swap(&a[cur], &a[prev]);
		}

	}
	//交换基准值和pre指针指向的值
	Swap(&a[keyi], &a[prev]);

	PartSort(a, left, keyi);
	PartSort(a, keyi + 1, right);
}

优化

第一种是取随机值做下标
第二种是获取这三个数中不是最大,也不是最小的那个值的下标,这种情况下不会有最坏情况,因为有三数组取中。

我们只需将取基准值时的方法改为三数取中即可达到优化效果。

int MidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

将之前的代码的取基准值替换为此即可。

标签:right,实现,内附,基准,元素,指针,int,排序,left
From: https://www.cnblogs.com/dwinternet/p/18052492

相关文章

  • 接口自动化中实现【参数化】以及【测试数据】可以放在哪里
    一、在接口自动化测试中,参数化可以实现多组数据反复调用一个测试脚本,从而简化测试过程和减少重复劳动。常见的参数化方式包括:1、数据驱动数据驱动是将测试数据集合放入外部存储(如Excel、CSV等),然后使用专门的库或工具(如Pandas)来读取数据并将其预处理、转换为代码可以理解的语言格......
  • 常用的盘点表格式及其在VeryReport报表软件中的实现
    在现代企业中,盘点表是不可或缺的管理工具,它能够帮助企业对资产、库存、人员等资源进行全面、准确的统计和分析。随着信息技术的不断发展,越来越多的企业开始采用电子化的盘点表来替代传统的纸质表格,以提高工作效率和准确性。而在众多的报表软件中,VeryReport以其强大的功能和灵活性,......
  • WIFI&蓝牙(ESP32)转CAN总线&串口TTL模块-B1-设备作为TCP客户端连接TCP服务器,实现RS48
    <p><iframename="ifd"src="https://mnifdv.cn/resource/cnblogs/ESP32_CAN"frameborder="0"scrolling="auto"width="100%"height="1500"></iframe></p>说明这节测试的是让设备连接路由器,然后设备以......
  • 千卡利用率超98%,详解JuiceFS在权威AI测试中的实现策略
    2023年9月,AI领域的权威基准评测MLPerf推出了 StorageBenchmark。该基准测试通过模拟机器学习I/O负载的方法,在不需要GPU的情况下就能进行大规模的性能压测,用以评估存储系统的在AI模型训练场景的适用性。目前支持两种模型训练:BERT(自然语言模型)和Unet3D(3D医学成像)......
  • time模块实现进度条
    显示进度条defmyprocess(percent):ifpercent>1:percent=1#打印对应的#号数量*"#"=>字符串#号效果strvar=int(percent*50)*"#"#进行打印%%=>%print("\r[%-50s]%d%%"%(strvar,percent*100),end="")接受数据rec......
  • Graphics2D的属性有哪些,分别实现什么功能?
    Graphics2D对象有6种属性,包括paint、stroke、font、transform、clip和composite。(1)paint—该属性确定所绘制线条的颜色,以及填充图形的颜色和图案等。(2)stroke—该属性可以确定线条的类型以及粗细,还有线段端点的形状。(3)font—该属性可以确定所显示字符串的字体。(4)......
  • 智能升级:AntSK教你如何让聊天机器人实现智能联网操作
        随着人工智能技术的飞速发展,智能体已经逐步融入到我们的日常生活中。不过,要想让智能体不仅能聊天,还能接入网络实时获取信息,为我们提供更多便利,所需技术的复杂性不得不让人瞩目。今天,我将和各位分享如何在基于.NET开发的AI知识库/智能体项目AntSK中,利用SemanticKernel......
  • 使用setmetatable和__call元方法来实现根据字符串名字调用对应的函数
    cc.lualocalCMD={}--定义两个函数functionCMD.func1()print("Function1called")endfunctionCMD.func2()print("Function2called")endreturnCMD test.lualocalfunctions=require"cc"--设置表的元表和__call元方法se......
  • 如何通过ETL实现快速同步美团订单信息
     一、美团外卖现状美团作为中国领先的生活服务电子商务平台,其旗下的美团外卖每天承载着大量的订单信息。这些订单信息需要及时入库、清洗和同步,但由于数据量庞大且来源多样化,传统的手动处理方式效率低下,容易出错。比如,不同渠道的数据格式不一致,需要进行数据清洗和格式转换;数据量......
  • 腾讯云sdk实现短信发送
    uu为传入的手机号码defsendsms(uu):try:#必要步骤:#实例化一个认证对象,入参需要传入腾讯云账户密钥对secretId,secretKey。#这里采用的是从环境变量读取的方式,需要在环境变量中先设置这两个值。#您也可以直接在代码中写死密钥对,但是小心不要将代码复制、上传或者分享给他......