c语言-快速排序

目录

一、实现快速排序三种方法

 1、hoare法

2、挖坑法

3、双指针法

4、快速排序的优化

5、测试对比

结语：

前言：

        快速排序作为多种排序方法中效率最高的一种，其底层原理被广泛运用，他的核心思想与二叉树结构中的递归逻辑相似，首先标记一个元素作为基准点，然后利用该基准点把数组分成左右两个区间，并且使小于该基准点的元素放在左区间，大于该基准点的元素放在右区间，如此反复递归，直到数组为一个有序数组。

        实现快速排序的原理有三种方法：hoare方法，挖坑方法，双指针方法。

一、实现快速排序三种方法

 1、hoare法

        比如将一个数组的起始位置记成left，最后一个元素位置记成right，那么标记left的位置的元素，把该元素看成基准点（key）。

        .这时候right要不断的向左移动，若right所在位置的元素是小于key位置的元素，那么right停止移动。left要不断的向右移动，若left所在位置的元素是大于key位置的元素，那么left停止移动。总结就是：left找大，right找小。（注意：若将left设置为key，则先移动right然后才能移动left）

         当left和right都停下来后，把他们的元素进行交换，交换过后继续移动。

        如此反复操作，最后left会走到right的位置，这时候left和right是处于同一位置的，把该位置的元素和key位置的元素进行交换，更新key的位置。

        可以观察到，此时数组有了一个特点：以key为中心点，左边区间的元素都是小于基准点key元素的，右边区间的元素都是大于key元素的。

        但是此时数组并不是一个有序的数组，所以要通过多重递归，因此将左边区间又看成一个小数组，右边区间也看成一个小数组。此时左边区间的left就是下标为0的位置，左边区间的right是key-1的位置。右边区间的left是key+1的位置，right是整个大数组的末尾处，既大数组的right。通过递归不断让每个小数组变得有序，最后整个数组也就有序了。

        递归逻辑图如下：

        hoare版本快速排序代码实现：



#include<stdio.h>

void swap(int* p1, int* p2)//交换函数
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
int PatrSort1(int* a, int left, int right)//hoare法
{
	int key = left;//定义基准点key
	while (left < right)//当left<right说明还没相遇，继续数组内元素的交换
	{
		while (left < right && a[right] >= a[key])//right找小
		{
			right--;
		}
		while (left < right && a[left] <= a[key])//left找大
		{
			left++;
		}
		swap(&a[right], &a[left]);//交换left和right位置的元素
	}
	swap(&a[key], &a[left]);//跳出循环说明他们相遇了，将他们位置的元素与key位置的元素交换
	key = left;//更新key的位置
	return left;//返回key元素当前的下标
}

void Qsort(int* a, int begin, int end)//快速排序（递归法），这里的begin=left，end=right
{
	if (begin >= end)//
	{
		return;
	}
	int key = PatrSort1(a, begin, end);//每次递归都会找到一个属于该数组的key

	Qsort(a, begin, key - 1);//递归左右区间
	Qsort(a, key + 1, end);
}

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

void Test_Qsort()//快排（递归）测试
{
	int arr[] = { 5,10,6,1,2,4,3,9 };
	int sz = sizeof(arr) / sizeof(int);
	PrintArr(arr, sz);
	Qsort(arr, 0, sz - 1);
	printf("hoare法：");
	PrintArr(arr, sz);
}

int main()
{
	Test_Qsort();
	return 0;
}

        运行结果：

2、挖坑法

        思路：和hoare法一样先定义一个基准点，只不过把这个基准点叫做“坑”，“坑”里的元素是要被抹除的（也就是“坑”里不能有元素），因此先用一个变量key来保存“坑”里的元素。right向左移动找到小于该基准点（“坑”）的元素就把这个元素填到“坑”里，这时候“坑”里有了元素，可以表示“坑”被填满了，但是right位置的就变成了新的“坑”，因为right位置的元素被用来“填坑”了。

        下一次就是left找大的元素给到right位置的”坑“，然后left的位置就成了新坑，如此反复，直到left和righ相遇，待到他们相遇的位置必然是一个”坑“，这时候把key存储的元素放到这个”坑“里，此时会发现数组也以5（key）为中心点分成了两个区间，而且左区间的元素都是小于key的，右区间的元素都是大于key的。

        挖坑法代码实现快速排序：



#include<stdio.h>

void swap(int* p1, int* p2)//交换函数
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
int PatrSort2(int* a, int left, int right)//挖坑法
{
	int key = a[left];//把基准点元素的值保存起来
	int hole = left;//设置hole更加形象表示坑
	while (left < right)//相遇前进行相互“填坑”
	{
		if (left < right && a[right] >= key)//right找小
		{
			right--;
		}
		a[left] = a[right];//填坑
		hole = right;//right处变成新坑

		if (left < right && a[left] <= key)//left找大
		{
			left++;
		}
		a[right] = a[left];//填坑
		hole = left;//left处变成新坑
	}
	a[hole] = key;//最后left处是一个坑，把key存的元素给到此处，此处作为基准点
	return hole;//返回基准点的下标
}


void Qsort(int* a, int begin, int end)//快速排序（递归法）
{
	if (begin >= end)//
	{
		return;
	}
	int key = PatrSort2(a, begin, end);//每次递归都会找到一个属于该数组的key

	Qsort(a, begin, key - 1);//递归左右区间
	Qsort(a, key + 1, end);
}

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

void Test_Qsort()//快排（递归）
{
	int arr[] = { 5,10,6,1,2,4,3,9 };
	int sz = sizeof(arr) / sizeof(int);
	PrintArr(arr, sz);
	Qsort(arr, 0, sz - 1);
	printf("挖坑法：");
	PrintArr(arr, sz);
}

int main()
{
	Test_Qsort();
	return 0;
}

        运行结果：

        从结果可以看到，不管是挖坑法还是hoare法都可以实现排序，因为他们本身的逻辑是一样的。 

3、双指针法

        顾名思义就是依靠两个类似指针的变量去变量数组并且完成排序，首先定义一个变量prev和一个变量cur，分别在数组的第一个元素位置和第二个元素位置，cur在prev的后边（既cur在第二个元素位置），并且把prev的位置设置成key基准点。当cur遇到比key小的元素则prev往后走一步，然后prev的元素与cur的元素进行交换，交换过后cur继续走。当cur遇到比key大的元素则prev不动，cur继续走。

        最后当cur走到数组外面表示遍历结束，这时候prev所在位置的元素与key元素交换，并且作为新的基准点。

        此时数组也被分成了两个区间，并且左边区间的元素小于key，右边区间的元素大于key。 

        双指针法实现快速排序代码如下：



#include<stdio.h>

void swap(int* p1, int* p2)//交换函数
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
int PatrSort3(int* a, int left, int right)//双指针法
{
	int key = left;//定义基准点
	
	int prev = left;//定义两个变量
	int cur = left + 1;
	while (cur <= right)//当cur还在数组内时
	{
		if (a[cur] <= a[key] && prev != cur)//若cur元素小于keyi元素
		{
			prev++;//prev向后走一步
			swap(&a[cur], &a[prev]);//交换cur和prev位置的元素
		}
		cur++;//cur一直往后走

	}
	swap(&a[prev], &a[key]);//最后交换prev和key的元素
	key = prev;//更新key的位置
	return key;//返回key的下标
}


void Qsort(int* a, int begin, int end)//快速排序（递归法）
{
	if (begin >= end)//
	{
		return;
	}
	int key = PatrSort3(a, begin, end);//每次递归都会找到一个属于该数组的key

	Qsort(a, begin, key - 1);//递归左右区间
	Qsort(a, key + 1, end);
}

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

void Test_Qsort()//快排（递归）
{
	int arr[] = { 5,10,6,1,2,4,3,9 };
	int sz = sizeof(arr) / sizeof(int);
	PrintArr(arr, sz);
	Qsort(arr, 0, sz - 1);
	printf("双指针法：");
	PrintArr(arr, sz);
}

int main()
{
	Test_Qsort();
	return 0;
}

        运行结果：

        从结果来看，三个方法都可以实现快速排序。 三种方法的效率其实也不相上下，但是目前快速排序有一个问题：如果快速排序每次选key时都能选到中位数则快速排序的效率就很好，时间复杂度为：O（N*logN），但是快速排序在面对有序数组的排序下效率会很慢，因为第一位数不是中位数，其时间复杂度为O（N^2）。

4、快速排序的优化

        针对以上的问题，如果每次选key的时候都能选到数组偏中位数的值，那么就解决了该问题，因此当我们有了一个数组的left和right，那么可以假设一个中间值：mid=（left+right）/2，通过对比他们三者之间的关系从而得到三者的中间值。

        三数取中代码如下：

int GetMid(int* a, int left, int right)//针对有序数组排序的三数取中
{
	int mid = (left + right) / 2;//先定义一个mid中间值

	//对比他们三者之间的关系，选出三者之间的中间值
	if (a[left] < a[mid])
	{
		if (a[right] < a[left])
			return left;
		else if (a[mid] > a[right])
			return right;
		else
			return mid;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])
			return left;
		else
			return right;
	}
}

5、测试对比

        通过测试对比优化前的快速排序的效率和优化后快速排序的效率，测试代码如下：



#include<stdio.h>
#include<stdlib.h>
#include<time.h>


int GetMid(int* a, int left, int right)//针对有序数组排序的三数取中
{
	int mid = (left + right) / 2;//先定义一个mid中间值

	//对比他们三者之间的关系，选出三者之间的中间值
	if (a[left] < mid)
	{
		if (a[right] < a[left])
			return left;
		else if (a[mid] > a[right])
			return right;
		else
			return mid;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])
			return left;
		else
			return right;
	}
}

void swap(int* p1, int* p2)//交换函数
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
int PatrSort3(int* a, int left, int right)//双指针法
{
	int key = left;//定义基准点
	int temp = GetMid(a, left, right);
	swap(&a[temp], &a[key]);//使keyi处的元素是三数取中的结果

	int prev = left;//定义两个变量
	int cur = left + 1;
	while (cur <= right)//当cur还在数组内时
	{
		if (a[cur] <= a[key] && prev != cur)//若cur元素小于keyi元素
		{
			prev++;//prev向后走一步
			swap(&a[cur], &a[prev]);//交换cur和prev位置的元素
		}
		cur++;//cur一直往后走

	}
	swap(&a[prev], &a[key]);//最后交换prev和key的元素
	key = prev;//更新key的位置
	return key;//返回key的下标
}


void Qsort(int* a, int begin, int end)//快速排序（递归法）
{
	if (begin >= end)//
	{
		return;
	}
	int key = PatrSort3(a, begin, end);//每次递归都会找到一个属于该数组的key

	Qsort(a, begin, key - 1);//递归左右区间
	Qsort(a, key + 1, end);
}


void Contrast_test()//对比测试
{
	//手动构建数组
	int n = 100000;
	srand(time(0));
	int* n1 = (int*)malloc(sizeof(int) * n);
	int* n2 = (int*)malloc(sizeof(int) * n);
	int* n3 = (int*)malloc(sizeof(int) * n);
	int* n4 = (int*)malloc(sizeof(int) * n);
	int* n5 = (int*)malloc(sizeof(int) * n);
	int* n6 = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
	{
		n1[i] = rand() % 10000;
		n2[i] = n1[i];
		n3[i] = n1[i];
		n4[i] = n1[i];
		n5[i] = n1[i];
		n6[i] = n1[i];
	}
	//先让数组排成有序
    //clock函数返回的是系统启动到调用该函数的时间，单位是毫秒，并存到变量中
	int start1 = clock();
	Qsort(n1, 0, n - 1);
	int end1 = clock();

	//在进行对有序数组的排序
	int start2 = clock();
	Qsort(n1, 0, n - 1);
	int end2 = clock();

	printf("key为中间值，对有序数组的排序:\n");
	printf("Test_PatrSort3:%d\n", end1 - start1);
	printf("Test_PatrSort3:%d\n", end2 - start2);

	free(n1);
	free(n2);
	free(n3);
	free(n4);
	free(n5);
	free(n6);
}

int main()
{
	Contrast_test();
	return 0;
}

         运行结果（优化前）：

         运行结果（优化后）：

        通过结果可以发现，优化之后的快速排序在面对有序的数组效率依然很高。 

结语：

       以上就是关于快速排序的介绍，最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充~！！谢谢大家！！(～￣▽￣)～

 

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

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

相关文章

在re:Invent上IBM宣布与亚马逊云科技携手，Amazon RDS for DB2正式亮相

在re:Invent上IBM宣布与亚马逊云科技携手，Amazon RDS for DB2正式亮相

11月29日&#xff0c;IBM在亚马逊云科技re:Invent 2023上宣布&#xff0c;与亚马逊云科技合作推出Amazon Relational Database Service&#xff08;Amazon RDS&#xff09;for Db2。这项全新的完全托管云服务旨在简化客户在混合云环境中管理人工智能&#xff08;AI&#xff09;…
阅读更多...
element中el-table表头通过header-row-style设置样式

element中el-table表头通过header-row-style设置样式

文章目录 一、知识点二、设置全部表头2.1、方式一2.2、方式二 三、设置某个表头四、最后 一、知识点 有些时候需要给element-ui表头设置不同样式&#xff0c;比如居中、背景色、字体大小等等&#xff0c;这时就可以用到本文要说的属性header-row-style。官网说明如下所示&…
阅读更多...
C++作业4

C++作业4

代码整理&#xff0c; 将学过的三种运算符重载&#xff0c;每个至少实现一个运算符的重载 代码&#xff1a; #include <iostream>using namespace std;class Stu {friend const Stu operator*(const Stu &L,const Stu &R);friend bool operator<(const Stu …
阅读更多...
人机协同

人机协同

人机协同是指人和机器之间进行合作和协同工作的方式&#xff0c;人机协同是人工智能技术发展的一个重要方向&#xff0c;通过人机协同的方式&#xff0c;可以充分利用机器的智能和人的智慧&#xff0c;共同实现更高效、更智能的工作和生活方式。人机协同可以应用于各种领域和场…
阅读更多...
卷积神经网络（VGG-16）猫狗识别

卷积神经网络（VGG-16）猫狗识别

文章目录 一、前言二、前期工作1. 设置GPU&#xff08;如果使用的是CPU可以忽略这步&#xff09;2. 导入数据3. 查看数据 二、数据预处理1. 加载数据2. 再次检查数据3. 配置数据集4. 可视化数据 三、构建VG-16网络四、编译五、训练模型六、模型评估七、保存and加载模型八、预测…
阅读更多...
2023_Spark_实验二十四：SparkStreaming读取Kafka数据源：使用Direct方式

2023_Spark_实验二十四：SparkStreaming读取Kafka数据源：使用Direct方式

SparkStreaming读取Kafka数据源&#xff1a;使用Direct方式 一、前提工作 安装了zookeeper 安装了Kafka 实验环境&#xff1a;kafka zookeeper spark 实验流程 二、实验内容 实验要求&#xff1a;实现的从kafka读取实现wordcount程序 启动zookeeper zk.sh start# zk.sh…
阅读更多...
Linux系统常用指令

Linux系统常用指令

1.使用xshell登录到云服务器的Linux系统&#xff1a; ssh 用户名公网IP&#xff0c;例如&#xff1a; ssh root111.11.111. 2.添加用户 adduser 用户名&#xff0c;例如&#xff1a; adduser user 3.为用户设置密码 passwd 用户名&#xff0c;例如&#xff1a; passwd …
阅读更多...
更改Jupyter Notebook 默认存储路径

更改Jupyter Notebook 默认存储路径

import osprint(os.path.abspath(.)) 然后打开cmd,输入&#xff1a; jupyter notebook --generate-config 按照路径在本地文件夹中找到那个文件。 然后找到"c.NotebookApp.notebook_dir"这条语句&#xff1a;&#xff08;直接通过"crtlf"输入关键字找阿 …
阅读更多...
【BEV感知 LSS方案】Lift-Splat-Shoot（LSS）

【BEV感知 LSS方案】Lift-Splat-Shoot（LSS）

前言 LSS全称是Lift-Splat-Shoot&#xff0c;它先从车辆周围的多个摄像头拍摄到的图像进行特征提取&#xff0c;在特征图中估计出每个点的深度&#xff0c;然后把这些点“提升”到3D空间中。 接着&#xff0c;这些3D信息被放置到一个网格上&#xff0c;最后将这些信息“拍扁”…
阅读更多...
设计模式-结构型模式之桥接设计模式

设计模式-结构型模式之桥接设计模式

文章目录 三、桥接模式 三、桥接模式 桥接模式&#xff08;Bridge&#xff09;是用于把抽象化与实现化解耦&#xff0c;使得二者可以独立变化。它通过提供抽象化和实现化之间的桥接结构&#xff0c;来实现二者的解耦。 这种模式涉及到一个作为桥接的接口&#xff0c;使得实体类…
阅读更多...
element中el-input限制只输入正整数或保留两位小数

element中el-input限制只输入正整数或保留两位小数

文章目录 一、前言二、实现2.1、HTML2.2、只输入正整数2.3、只能输入数字或小数点 三、最后 一、前言 常见的el-input可能会限制用户只能输入正整数或保留两位小数&#xff0c;达到输入金额的需求&#xff0c;点击【跳转】访问el-input的官方文档 element-ui是有el-input-numb…
阅读更多...
新闻网站的技术 SEO：综合指南

新闻网站的技术 SEO：综合指南

要在 Google 上对您的内容进行排名或将目标访问者吸引到您的新闻网站或门户网站&#xff0c;需要的不仅仅是将理想的单词组合串在一起。你应该优化你的内容以获得更高的排名。由于排名高&#xff0c;可见性越高&#xff0c;新闻网站就越高。 持续不断的新内容流和独特的 Googl…
阅读更多...
ES6知识

ES6知识

作用域 局部作用域 局部作用域分为函数作用域和块作用域 函数作用域 在函数内部声明的变量只能在函数内部被访问&#xff0c;外部无法直接访问。函数的参数也是函数内部的局部变量。不同函数内部声明的变量无法互相访问。函数执行完毕后&#xff0c;函数内部的变量实际被清空…
阅读更多...
容器安全是什么

容器安全是什么

容器安全是当前面临的重要挑战之一&#xff0c;但通过采取有效的应对策略&#xff0c;我们可以有效地保护容器的安全。在应对容器安全挑战时&#xff0c;我们需要综合考虑镜像安全、网络安全和数据安全等多个方面&#xff0c;并采取相应的措施来确保容器的安全性。 德迅蜂巢原…
阅读更多...
Ubuntu 2204 安装libimobiledevice

Ubuntu 2204 安装libimobiledevice

libimobiledevice是一个开源的软件&#xff0c;它可以直接使用系统原生协议和IOS设备进行通信&#xff0c;类似iMazing&#xff0c;iTunes&#xff0c;libimobiledevice不依赖IOS的私有库&#xff0c;并且连接IOS设备时用的都是原生协议&#xff0c;IOS无需越狱就能实现设备信息…
阅读更多...
常见基础指令【Linux】

常见基础指令【Linux】

目录 一、Linux基本指令1. ls2. pwd3. cd4. touch5. mkdir6. rm和rmdir7. man8. cp9. mv10. cat11. tac12. more13. less14. head15. tail16. date17. cal18. find19. grep20. zip/unzip21. echo22. wc23. tree24. which25. alias26. whoami27. stat28. tar29. uname30. shutdo…
阅读更多...
SQL-分页查询offset的用法

SQL-分页查询offset的用法

今天在做一道关于查询一张表中第二高工资的问题时发现没有思路&#xff0c;经过一番搜索发现需要用到offset偏移量来解决这个问题。 OFFSET关键字用于指定从结果集的哪一行开始返回数据。通常&#xff0c;它与LIMIT一起使用&#xff0c;以实现分页效果。其语法如下&#xff1a…
阅读更多...
北邮22级信通院数电：Verilog-FPGA（12）第十二周实验（1）设计一个汽车尾灯自动控制系统

北邮22级信通院数电：Verilog-FPGA（12）第十二周实验（1）设计一个汽车尾灯自动控制系统

北邮22信通一枚~ 跟随课程进度更新北邮信通院数字系统设计的笔记、代码和文章 持续关注作者 迎接数电实验学习~ 获取更多文章&#xff0c;请访问专栏&#xff1a; 北邮22级信通院数电实验_青山如墨雨如画的博客-CSDN博客 目录 一.题目要求 二.代码部分 2.1 car_system.…
阅读更多...
【redis】[windows]redis安装以及配置等相关

【redis】[windows]redis安装以及配置等相关

前言&#xff1a;下载安装配置密码、远程访问等等 目录 一、下载 二、配置文件说明 1、bind 1.1 这个参数默认值是127.0.0.1&#xff0c;也就是只允许redis所在机器访问redis。 1.2 如果我们的应用服务和redis服务不在一个机器我们就需要修改这个参数为0.0.0.0&#xff0c…
阅读更多...
使用C语言创建高性能爬虫ip网络

使用C语言创建高性能爬虫ip网络

之前写的python和GO语言的爬虫ip池的文章引起很大反响&#xff0c;这次我将以C语言来创建爬虫IP池&#xff0c;但是因为其复杂性&#xff0c;可能代码并非完美。但是最终也达到的想要的效果。 因为在C语言中创建代理IP池可能会比较复杂&#xff0c;且C语言并没有像Python那样的…
阅读更多...
最新文章

Copyright @ 2022~2023