【C语言】快速排序（经典算法，建议收藏！！！）

目录

• • 1、原理
  • 2、代码展示
  • 4、适用场景
  • 4、评价

    1、原理

    快速排序（Quick Sort）是一种常用且高效的排序算法，其基本原理如下：

    
    （图片来源网络，侵删）

    1.选取基准值（Pivot）: 从数组中选择一个基准值，通常是数组中的第一个元素、最后一个元素或者中间元素。

    2.分割数组: 将数组中小于基准值的元素移到基准值的左侧，大于基准值的元素移到基准值的右侧。这一步骤通常被称为“分区”（Partitioning）。

    3.递归排序子数组: 递归地对基准值左侧和右侧的子数组进行排序。即对左侧子数组和右侧子数组分别重复步骤1和步骤2，直到每个子数组的大小为1或0（已经有序）。

    4.合并排序结果: 不需要合并步骤，因为在分区的过程中，已经将元素移动到了正确的位置。

    2、代码展示

    要求对一个数组完成升序排序

    #include 
    void quick_sort(int arr[], int start, int end)
    {
    	//判断是否需要排序
    	if (start >= end)
    	{
    		return;
    	}
    	int left = start;
    	int right = end;
    	int pivot = arr[left];	//基准值
    	while (left  pivot) && (left  
    4、适用场景
     
    快速排序适用于以下场景：
     
    1.大型数据集: 快速排序在处理大型数据集时表现优异，其平均时间复杂度为O(n log n)，在实践中通常比其他O(n log n)复杂度的排序算法执行得更快，尤其是对于中等规模至大规模的数据集。
     
    2.需要原地排序的情况: 快速排序是一种原地排序算法，只需要常数级别的额外空间，因此适用于对内存消耗有限的场景，尤其是在处理大型数据集时，节省了额外的内存开销。
     
    3.平均情况下的高性能要求: 在平均情况下，快速排序的性能非常出色，其时间复杂度为O(n log n)，因此适用于对排序性能要求较高的场景。
     
    4.数据分布较为均匀: 当待排序的数据分布较为均匀时，快速排序的性能较好。因为快速排序的性能高度依赖于选择的基准值，当数据分布不均匀时可能会导致快速排序性能下降，甚至退化为O(n^2)的时间复杂度。
     
    5.适度重复的数据集: 对于包含适度重复元素的数据集，快速排序通常表现良好。适度重复的数据集会使得分区过程中的子数组大小更加均衡，从而提高排序的效率。
     
    总的来说，快速排序适用于处理大型数据集、需要原地排序、对排序性能要求高、数据分布较为均匀以及包含适度重复元素的情况。然而，在处理极端情况下的数据集时，如完全有序或者完全逆序的数据，快速排序的性能可能会退化为O(n^2)，此时可能需要考虑其他排序算法。
     
    4、评价
     
    快速排序的优势在于其平均情况下的时间复杂度为O(n log n)，并且具有较好的空间复杂度。然而，快速排序的性能高度依赖于选择的基准值，不同的基准值选择策略可能会影响排序算法的效率。通常情况下，基准值的选择可以采用随机选择或者三数取中等策略，以尽量避免最坏情况的发生。快速排序是一种原地排序算法，只需要常数级别的额外空间，因此在排序大型数据集时，快速排序通常是首选的排序算法之一。
     
    总结：
    整个排序过程可以概括为“分而治之”的思想，通过不断地将数组分割成更小的子数组，并对子数组进行排序，最终实现整个数组的有序。
     
    那么写到这里，本节内容就结束了，这篇博客花费了很长时间，但写完有满满的成就感，希望能帮助到大家，如果文章有不足的地方，欢迎在评论区留言指正，我们一起学习交流！
    希望能得到大家的关注、点赞、评论、收藏！ 你的支持是我最大的动力！！