• 【21天学习挑战赛】快速排序



    活动地址:CSDN21天学习挑战赛
    学习的最大理由是想摆脱平庸,早一天就多一份人生的精彩;迟一天就多一天平庸的困扰。

    排序

    基本概念

    评价指标

    1. 稳定性:关键字相同的元素在排序后相对位置不变,但是稳定的算法一定比不稳定的好?不一定,要看实际需求
    2. 复杂度:
      1. 时间复杂度
      2. 空间复杂度

    分类:

    1. 内部排序:关注如何使算法时间空间复杂度更低
    2. 外部排序: 还需要关注如何使读写磁盘次数更少

    内部排序

    1. 插入类排序:
      1. 直接插入排序
      2. 折半插入排序
      3. 希尔排序
    2. 交换排序
      1. 冒泡排序
      2. 快速排序
    3. 选择排序
      1. 简单选择排序
      2. 堆排序
    4. 归并排序
    5. 基数排序

    外部排序

    快速排序

    排序思路过程

    1.一开始第一个元素即默认为基准,但也是low

    2.基准左面的都比基准小,基准右侧都比基准大,因此两侧扫描的时候只有符合条件的才会换过去,相等的就是不动,所以是一个不稳定的算法。

    3.当low>=high就换,而且基准是和low换

    算法图解

    7bc3f43b871cd893122537bed74326a0

    代码实现(C语言)

    #include 
    int Partition(int* arr, int low, int high)
    {
    	//一次划分
    	int tmp = arr[low];//基准
    	while (low < high)
    	{
    		//(1)从后往前找比基准小的数字
    		while (low<high && arr[high]>tmp)
    		{
    			high--;
    		}
    		if (low < high)
    		{
    			arr[low] = arr[high];
    		}
    		//(2)从前往后找比基准大的数字
    		while (low < high && arr[low] <= tmp)
    		{
    			low++;
    		}
    		if (low < high)
    		{
    			arr[high] = arr[low];
    		}
    	}
    	arr[low] = tmp;
    	return low;
    }
    void Quick(int* arr, int low, int high)
    {
    	int par = Partition(arr,low, high);
    	if (low < par - 1)//左边数据超过一个
    	{
    		Quick(arr, low, par - 1);
    	}
    	if (par + 1 < high)//右边数据超过一个
    	{
    		Quick(arr, par + 1, high);
    	}
    }
    void QuickSort(int* arr, int len)
    {
    	Quick(arr, 0, len - 1);//参数一致
    }
    void Show(int* arr, int len)
    {
    	for (int i = 0; i < len; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    }
    
    • 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

    代码思路总结:

    1. 从后往前找比基准小的数据,往前挪

    2. 从前往后找比基准大的数据,往后挪

    3. 重复第一步和第二步。

    快速排序性能

    image-20220820203118701

    快速排序是所有内部排序算法中平均性能最优的排序算法

    关键点

    1. 一趟排序可以确定一个元素的最终位置。
    2. 要求快排的速度快,理想状况就是每次基准都可以把表划分成两个长度相近的子表,此时速度是最快的。当表本身是有序的或者逆序的此时快拍的速度是最慢的。
    3. 快速排序本质上是一种交换排序。
  • 相关阅读:
    【持续更新】整理的Mediapipe学习资料
    Web开发:<p>标签作用
    Applications of Artificial Intelligence and Machine learning in smart cities
    ZCMU--2192: Queue
    java多线程实现同步锁卖票窗口案例
    远程办公中的IT女性:工作量增加3倍,离职率却下降近50%
    【linux kernel】linux的platform设备驱动框架分析
    MYSQL--事务
    计算机系统的层次结构
    layui--table里使用switch
  • 原文地址:https://blog.csdn.net/wxnshuai/article/details/126444986