首页 > 其他分享 >指针、快速排序

指针、快速排序

时间:2024-08-10 10:55:21浏览次数:14  
标签:end 指向 int 元素 类型 排序 快速 指针

(一)指针

1.指针变量初始化

(1)如果指针变量没有初始化,此时是随机值。初始化可以让指针变量有明确指向。

eg:①int  a = 10;

          int  *p = &a;

②int  *p = NULL; //0号地址 ---- 空指针

(2)赋值:

方式①:  int  *p;    p=NULL;

方式②:  int a;   int *p;  p = &a;

方式③:int  *p,q;   // p是指针类型 int * ;q是int型

方式④:int  *p,*q;    //此时表示定义了两个int * 类型的变量p , q(同时定义多个指针类型)

注意:定义时候的 * ,修饰变量名的时候 表示定义的是一个指针类型的变量。

要实现被调修改主调

2.指针作为函数参数

(1)形参:指针类型变量,用来接收实参(实参是 要操作的内存空间的地址)

(2)实参:要修改谁,就把谁的地址传过去。(但是要保证空间有效)

注意:被调函数中一定要有 *p 运算(间接访问的操作)

(3)传参方式:①值传递:只是把实参数据赋值给了形参;②地址(指针)传递:传的是地址(可以实现被调修改主调)

(二)指针+一维整型数组

eg:int a[5];   //一维整型数组:

                       //数组名;

                       //类型:数据类型int[5] ;

                       //值:数组首元素地址(常量)

                       //数组名是常量,不能做自增、自减运算

1.定义一个什么类型的指针变量?  int  *p = a;  或  int  *p = &a[0];   (a是数组)

2.谁能代表数组所在空间的首地址? 数组名 -- 数组首元素的地址

eg:   int  *p = a;  //表示 p 指向了数组 a,  此时 *p <=> a[0]

3.指针的其它运算:

(1)p+1:当对指针 p 执行 p + 1 操作时,如果 p 指向的是某个基类型(如整数、字符等)的变量,那么 p + 1 会使指针跳过 sizeof(基类型) 个字节,指向同类型的下一个元素。这是因为指针的运算会根据所指向的数据类型的大小进行相应的偏移。

(2)p-1:与 p + 1 相反,p - 1 会使指针向前移动 sizeof(基类型) 个字节,指向同类型的前一个元素。

(3)p++:指针的后置自增运算。先使用 p 的当前值进行操作,然后将 p 的值增加 sizeof(基类型) 个字节,指向下一个同类型的元素。

(4)p-- :指针的后置自减运算。先使用 p 的当前值进行操作,然后将 p 的值减少 sizeof(基类型) 个字节,指向上一个同类型的元素。

(5)比较:>  <  >=  <=  ==   !=  (比较地址编号)

         当对指针进行比较操作(><>=<===!= )时,实际上是比较它们所指向的内存地址的编号。只有当两个指针指向同一块内存区域(例如,指向同一个数组)时,进行比较才有实际意义。如果两个指针指向不同的内存区域或不同类型的对象,比较的结果是未定义的。

注意:

(1)当 p 是指针类型变量:

①  *&p:&p 表示取指针 p 的地址, *&p 就是对 p 的地址进行解引用,结果仍然是 p 本身。

②  &*p:*p 表示访问指针 p 所指向的内容, &*p 就是取 p 所指向内容的地址。如果 p 指向一个变量 x ,那么 &*p 就等于 &x。

(2)当 p 是指针类型变量,a 是数组时:(<=>  --- 等价)

① *(p+i) <=> a[i] <=> *(a+i)

② a[i]  <=> *(a+i)

③ i[a]  <=> *(i+a)      

(3)若 p 和 q 是指针类型变量:

    在 C 或 C++ 中,对于指针类型的变量 p 和 q ,通常不允许进行 p - qp + qp * q 和

 p / q 这样的运算。指针的主要操作是基于地址的偏移(如 p + n 或 p - n ,其中 n 为整数,表示移动的元素个数)和比较(如 p == q 、 p < q 等),如果对指针进行上述不被允许的数学运算(如 p - qp + qp * q 、p / q),编译器会报错。

4.数组作为函数参数

(1)形参:数组形式(本质上是一个指针类型变量);数组长度

(2)实参:数组名(数组名代表数组首地址); 数组长度

(三)快速排序

思想:分而治之

1.实现思想

选择一个基准元素,通过一趟排序将待排序的序列分割成独立的两部分,其中一部分的所有元素都比基准元素小,另一部分的所有元素都比基准元素大。然后对这两部分分别进行快速排序,从而实现整个序列的有序。

2.实现步骤

(1)选择基准元素:通常从待排序序列中选择第一个元素作为基准值。

(2)分区操作:

从序列的两端开始,设置两个指针 begin 和 end 。                       

指 begin 针从左向右移动,直到找到第一个大于等于基准的元素;end 指针从右向左移动,直到找到第一个小于等于基准的元素。

交换这两个元素的位置。

重复②-③步骤,直到 end 指针与 begin 指针相遇。

最后将基准元素与 end 指针所指向的元素交换位置,此时 end 指针之前的元素都小于等于基准,end 指针之后的元素都大于等于基准,完成分区。

(3)对分区后的两部分分别递归地进行快速排序:对小于基准的子序列和大于基准的子序列分别再次执行上述步骤,直到整个序列有序。

(3)具体代码
void quickSort(int *begin, int *end)
{
	int *p = begin;
	int *q = end;

	int *k = begin;

	if(begin>=end)
	{
		return;
	}

	while(begin<end)
	{
		while(begin<end && *end>=*k)
		{
			--end;
		}
		while(begin<end && *begin<=*k)
		{
			++begin;
		}
		swap(begin,end);
	}
	swap(k,begin);
	quickSort(p,end-1);
	quickSort(begin+1,q);
}

标签:end,指向,int,元素,类型,排序,快速,指针
From: https://blog.csdn.net/weixin_62989562/article/details/140947385

相关文章

  • 指针、字符串函数
    (一)指针操作一维字符型数组const关键字(只读)eg:(1)int *p;  //基类型(目标类型)(2)int a= 10;   ①const int *p=&a;  //const限定是基类型,表示不能通过*p的方式修改基类型的数据   ②int const *p=&a;  //与①等价     ......
  • 如何快速从文本中找到需要的信息,字典和正则灵活运用
    importre#打开文本文件f=open("stock_data.txt",encoding="utf-8")#单独读取第一行数据处理进行分割,末尾换行符去掉headers=f.readline().strip().split(',')print(headers)#定义一个字典,以股标代码做为KEY,每个行做为值stock_list={}forlineinf:line......
  • Docker快速入门指南
    ......
  • 【ACM出版,见刊检索快速稳定】第四届物联网与机器学习国际学术会议(IoTML 2024,8月23-25)
    2024年第四届物联网与机器学习国际学术会议(IoTML2024)将于2024年8月23-25日在中国南昌召开。会议将围绕着物联网和机器学习开展,探讨本领域发展所面临的关键性挑战问题和研究方向,以期推动该领域理论、技术在高校和企业的发展和应用,为专注于该研究领域的创新学者、工程师和......
  • 指针与一维数组
    目录指针:指针变量的初始化:赋值:指针作为函数参数://一维整型数组指针实现一维数组逆序:指针实现选择排序:指针实现冒泡排序:指针实现插入排序:指针实现一维整型数组二分查找(有序数组前提下):指针实现一维数组快速排序:指针:指针变量的初始化:如果指针没有初始化,此时是随机......
  • 指针进阶--指针与一维字符型数组
    目录const关键字:constinta =10;constint*p=&a;(等价于intconst*p=&a)const的应用:一维字符型数组与字符函数指针实现strcpy的功能:指针实现strncpy的功能:指针实现strcat功能:指针实现strncat功能:指针实现strcmp功能:指针实现strncmp功能:void*指针(万能指针):指......
  • 深入了解指针(5)
    1.数组指针变量2.⼆维数组传参的本质3.函数指针变量2.⼆维数组传参的本质3.函数指针变量)1.数组指针变量1.1了解数组指针变量的概念整形指针变量——变量——存放的是整形的地址字符指针变量——变量——存放的是字符的地址数组指针——变量—......
  • 超简单适合练手的双指针题:判断子序列
    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。示例1:输入:s="abc",t="ahbgdc"输出:true示例2:输入:s="axc......
  • LLM大模型的书那么多,如何快速选到适合自己的那一本?
    大模型的书这么多,该怎么选呢?今天就来教大家怎么快速地从众多大模型书中选到你想要的那一本!朋友们如果有需要这些大模型书扫码获取~​大模型基础大模型入门不可错过的一本书,就是这本大模型界的经典畅销书《大规模语言模型》!系统性强,内容适合初学者,如果你想知道如何构......
  • 排序简单篇——冒泡排序、选择排序、插入排序、希尔排序、快速排序全解析【附完整源码
    ......