您现在的位置是:首页 > 正文

交换排序算法之快速排序-C语言版(带图详细)

2024-04-01 02:14:53阅读 3

前言

哈喽,大家好,我最近在复习数据结构中的排序算法章节,今天复习到了交换排序算法中的快速排序算法,所以给大家分享一下。

一、什么是快速排序?

快速排序算法是在几种排序算法中效率最高的一个排序算法了,故称为快速排序,它的时间复杂度为:O(nlog2n),相比冒泡排序算法的O(n2)有很大的提升。

二、算法思想

1、选取一个基准元素(一般我们将待排序序列中的第一个元素选取为基准元素)
2、将其他元素与基准元素进行比较,比基准元素大的放到基准元素的右边,比基准元素小的放到基准元素的右边。(以基准元素为中心将元素重新分成两个序列并返回基准元素的下标
3、将新生成的两个序列继续执行1和2两步(此处可以用递归实现)

接下来我们通过一个动图来看一下快速排序算法。
快速排序

三、实例讲解

我们有一个待排序序列是:【 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】
在这里插入图片描述

第一轮排序:

①选取第一个元素44为基准坐标。
在这里插入图片描述

②以44为中心,将序列分为两部分,左边比44小,右边比44大。
在这里插入图片描述
③原来的序列被分成两部分,一部分比44小的是【0,基准坐标-1】,另一部分比44大的是【基准坐标+1,最后】,将这两部分继续执行①和②两步最终即可排序完成。

第一轮排序总结: 算法思想其实不难理解,那么接下来需要解决的问题就是,如何将一个序列以基准坐标分成相对有序的两部分,以及递归出口问题。

四、算法分析

1.时间复杂度

O(nlog2n)

2.空间复杂度

空间复杂度由于需要开辟一个临时空间来存储基准坐标所以是:O(1)

五、代码实现

#include<stdio.h>
void Print(int array[],int len){
	for(int i=0;i<len;i++){
		printf("%d ",array[i]);
	}
	printf("\n");
} 
/*获取基准坐标,并相对有序(左边比基准坐标小,右边比基准坐标大)*/
int getStandard(int array[],int low,int high) {
	int key = array[low];  //临时保存基准元素 
	while(low<high) {  
		//high指针从后向前遍历 , 元素比基准元素大则指针向前移动 则比基准元素小则和基准元素交换 
		while(low<high && array[high]>=key){
			high--;
		}
		if(low<high){
			array[low] = array[high];  //赋值给第一个元素,因为第一个元素作为基准元素已经临时保存了,所可以直接赋值 
		}
		//low指针从前向后遍历 , 元素比基准元素小则指针向后移动 否则比基准元素大则和基准元素交换 
		while(low<high && array[low]<=key){
			low++;
		}
		if(low<high){
			array[high] = array[low];  //复制给high指针所指得位置,因为在11行已经赋值给array[low]了 
		}
	}
	array[low] = key;
	return low; 
}
void QuickSort(int array[],int low,int high){
	if(low<high){  //递归出口 
		int standard = getStandard(array,low,high);
		QuickSort(array,low,standard-1);  //比基准元素小的部分继续调用快速排序 
		QuickSort(array,standard+1,high);   //比基准元素大的部分继续调用快速排序 
	}
}
 int main(){
 	int array[] = {3, 44, 38, 5, 47, 15, 36};
	int size = sizeof(array) / sizeof(int);
	printf("原始序列为:\n");
	Print(array,size); 
	QuickSort(array,0,size-1);
	printf("排序后序列为:\n");
	Print(array,size); 
 } 

六、运行结果

在这里插入图片描述

总结

最后,我们只需要记住快速排序的算法思想(两步)以及如何通过两个指针来实现将待排序序列分成两部分即可。

网站文章

  • cesium入门(一)

    cesium入门(一)ygpGoogle 2020-09-22 19:21:17 697 收藏 4分类专栏: gis 文章标签: nodejs gis版权gis专栏收录该内容2 篇文章0 订阅订阅专栏...

    2024-04-01 02:14:42
  • 想学语言的模块化的同学可进来看看(以51单片机的模块化来讲解)

    想学语言的模块化的同学可进来看看(以51单片机的模块化来讲解)

    因为才刚刚接触程序半年,凭着本人有限的知识,只能从单片机来讲解这个模块化的相关知识. 首先讲讲写这篇博客的初衷,我们第一学期寒假的时候,我们的寒假作业要求就是得用模块化编写,网上看到的一些资料感觉看不懂,找了些大神给我讲解了之后才感觉明白了,自己用的时候还出现了很多的错误.为了让后面的学弟学妹们好好理解模块化写的第一篇博客.分模块的好处首先,这是我在写万年历和温度传感器的时候,显然这是我...

    2024-04-01 02:14:32
  • 第七周学习内容总结——区间dp、dfs

    第七周学习内容总结——区间dp、dfs

    本周学习内容一:本周学习了区间dp,今天又花一下午,终于弄懂这个经典题目(石子归并) 来看我的思考(O ^ ~ ^ O) #include #include #include #include #include #include #include #include using na

    2024-04-01 02:14:24
  • 仅需一个样本即可定制个性化的SAM

    仅需一个样本即可定制个性化的SAM

    仅需一个样本即可定制个性化的SAM

    2024-04-01 02:13:46
  • 最新php中es整合项目(Elasticsearch高级篇整合tp后台)

    最新php中es整合项目(Elasticsearch高级篇整合tp后台)

    以下后台使用thinkphp5.1、Elasticsearch7.14.1、ik分词器集成1索引列表2、添加索引3、设置字段4、添加文档5、修改文档6、查询索引并分页

    2024-04-01 02:13:37
  • 20050912:加把劲了

    向来以做事快著称的我,竟然成了项目里的瓶颈,郁闷~~~今天做了一天才把密码重置做完,然后就是email帐单和用户资料修改了。加油!为了不加班而加班!莫菲斯托,等着我蹂躏你吧(给我来两件绿色我就放了你)~~~~转载于:https://www.cnblogs.com/yidinghe/archive/2005/09/12/235407.html...

    2024-04-01 02:13:31
  • 基于学习的机械臂抓取研究综述

    基于学习的机械臂抓取研究综述

    本文主要总结了2020年的一篇机械臂抓取综述类的论文A Survey on Learning-Based Robotic Grasping,文末有本领域重点的一些论文。

    2024-04-01 02:12:53
  • 450. 删除二叉搜索树中的节点-递归

    450. 删除二叉搜索树中的节点-递归

    一、题目描述给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。一般来说,删除节点...

    2024-04-01 02:12:47
  • 计算机网络总复习

    计算机网络总复习

    计算机网络复习一、计算机网络概述1、计算机网络组成与结构(1)资源子网:(2)通信子网:2、计算机网络的拓扑结构(1)总线型(广播网络)(2)星型(3)树形(分层结构)(4)环形(局域网或城域网常用的...

    2024-04-01 02:12:39
  • 美国服务器查询网站查询网站查询网站查询网站查询,全球DNS节点查询网

    月ъыь0430ю◎⊕㈱全球DNS节点查询网Whats My DNS 网站是一个可以查询世界五大洲各个国家的DNS节点服务器更新记录情况的站点,它的主要功用是从全世界各个国家节点来查询某个域名的DNS...

    2024-04-01 02:11:56