• 快速排序的实现!递归实现!!超详细!!!


    快速排序

    快速排序的介绍

    快速排序之所以快,是相对于冒泡排序,不再是只有相邻的数之间交换,它是可以跳跃式的交换,交换的距离会变得大的多,所以速度就提高了。
    当然也会存在最坏的结果,仍然是跟冒泡一样是相邻的两数之间进行了交换,所以它最差的时间复杂度和冒泡排序是一样的,都是O(N²),它的平均复杂度是O(NlogN)

    图文结合介绍逻辑思路

    1.给数组放置10个数字,然后设定基准值为第一个元素的值,也就是5.然后设定两个变量i,j用于分别从左和右遍历数组。i在最左边,j在最右边。
    在这里插入图片描述
    2.j向左动找到比基准值5小的数,i向右动找到比基准值5大的数。然后将i,j所指向的值交换
    注意:这里是j先动,当j找到比基准值小的数之后,i再动。原因稍后解释
    在这里插入图片描述
    3.第2步,ij交换后二者继续走,分别找到4,9之后再交换
    在这里插入图片描述
    4.第三部之后ij继续走直至i和j走到同一个位置停下,此时将这个位置的值和基准值5交换位置,即 将1和5交换。
    在这里插入图片描述
    5.交换后我们可以看到,5(基准值)左边的数都是小于5的,右边的数都是大于5的!
    这里可以解释一个很重要的问题的了,为什么是j先动,直到j找到一个比基准值小的数之后i再动。
    原因:j寻找的是比基准值小的数,i寻找的是比基准值大的数,对吧。然后当ij碰面,大概率(有个特殊情况下面步骤会提到)情况下,碰面的位置是在数组中间的某个位置,我们需要的结果是变换后基准值左边都小于基准值,基准值右边都大于基准值。而最开始,基准值在最左边,所以为了满足交换后最左边的最也是小于基准值的,我们就需要碰面的位置的值是小于基准值的,故需要j先动找到这个值。
    换个说法:为什么每次都需要j先移动,因为当最后i和j相碰时,此时所指向的是j寻找到比基准值小的数字,然后和基准值交换能确保基准值左边的都是小于基准值的数字,但是如果i先右边移动的话,最后i和j相碰时,i和j所指向的是i寻找得比基准值大的数,此时和基准值相交换,基准值左边是有一个比基准值大的数,没有达到我们需要的排序效果。

    在这里插入图片描述
    6.利用递归,分别将基准值左右两部分再传去函数排序,这里我们拿左边来举例。
    此时基准值是1
    在这里插入图片描述
    7.j先走,寻找比基准小的值,一直走到ij相等的位置停下来,i,j,基准都在同一个位置,交换后不变。

    在这里插入图片描述
    8.接着将基准值1右边的递归进行排序即可
    在这里插入图片描述

    关键点

    1.选取基准点
    2.永远是j先向左移动直到i,j相等或者j找到比基准值小的数之后,i再向右移动
    3.当i,j碰面时候,将i和j所指向的数和基准值交换
    4.然后处理左半边和右半边(递归)
    5.c语言自带快排的函数,叫qsort,可以直接使用,我们这里是实现这个函数的功能

    代码

    #define _CRT_SECURE_NO_WARNINGS 1
    
    #include
    
    int arr[100] = { 0 };
    //定义全局数组的好处:
    //如果定义的是在mian里的数组的话,在my_qsort函数传参的时候需要把数组传进去
    //更麻烦的是,在递归的时候,需要将变换后的基准点位置左右两侧分别传给两个数组再进行传参,这是及其麻烦且不便的
    //但是利用全局数组的话,只需要和第一次使用my_qsort一样传入起始与结尾的下标即可
    
    void my_qsort(int left, int right)
    {
    	int sta = arr[left];//定义基准变量。基准的单词是standard,取首字母方便理解!
    	int tmp = 0;//临时变量,用于后面对两个数组元素的位置交换
    	int i = left;
    	int j = right;
    	//定义i,j分别存储left和right是为了在后面的程序中不改变left和right,为什么不能改变呢,看函数最后几行的递归处,还需要将现在的left和right传到递归函数中。
    
    	if (i > j)//逻辑实现的第一个判断,如果传进来的right比left还行,那肯定就是传参出现了问题。
    	{
    		return;
    	}
    
    	while (i != j)//当ij没走到一块时
    	{
    		//只能先判断arr[j],原因的话在我讲解流程的图的时候已经解释了
    		while (i < j && arr[j] >= sta)//j一步步左移,直到找到比基准小的数
    		{
    			j--;
    		}
    		while (i < j && arr[i] <= sta)//i一步步左移,直到找到比基准大的数
    		{
    			i++;
    		}
    		if (i < j)
    		{
    			//将j找到的比基准小的数和i找到的比基准大的数交换位置
    			tmp = arr[i];
    			arr[i] = arr[j];
    			arr[j] = tmp;
    		}
    	}
    	//将基准归为(这一步过后,基准已经是排好序的了)
    	arr[left] = arr[i];//当循环结束,此时i = j,将这个位置的数和基准交换
    	arr[i] = sta;
    
    	//递归实现
    	my_qsort(left, i - 1);//处理此时基准左边部分的数
    	my_qsort(i + 1, right);//处理基准右边部分的数
    }
    
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);//给定输入的个数
    
    	for (int i = 0; i < n; i++)//循环给数组赋值
    	{
    		scanf("%d", &arr[i]);
    	}
    
    	my_qsort(0 , n - 1);//由于数组元素对应到下标需要减1,我们这里直接减1再传进去就更方便编写程序者思考和使用
    	//y_qsort(1, n);    //不过如果在实际应用中,只能这样传,然后函数实现的时候再减1,因为一般用户是不知道数组的这个特点的,只能让其按常识进行传参
    
    	for (int i = 0; i < n; i++)//循环打印数组
    	{
    		printf("%d ", arr[i]);
    	}
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70

    参考文章

    https://blog.csdn.net/Czc1357618897/article/details/121600596

  • 相关阅读:
    it监控系统可以电脑吗?有什么效果
    2022_08_06__106期__二叉树
    含叠氮的代谢糖蛋白标记试剂361154-30-5,N -叠氮乙酰基甘露糖胺-四酰基化
    兆骑科创创新创业服务平台——创新创业的联通之桥
    FlowJo 10.4.0(流式细胞分析器工具)
    Linux终将取代Unix?富士通确认Unix系统和大型机的结束时间
    【系统架构】-什么是MDA架构、ADL、DSSA
    【毕业设计】 NodeMCU使用mpu6050惯性传感器 - 单片机 物联网嵌入式
    js数组按照id删除
    “蔚来杯“2022牛客暑期多校训练营10 F.Shannon Switching Game?
  • 原文地址:https://blog.csdn.net/qq_67838572/article/details/127710883