快速排序：10分钟掌握高效算法精髓

hello！大家好我会尽量每天跟大家持续更新，忙的时候可能会断更一天，非常感谢大家的点赞关注和支持！！！（这个基础算法会每天分享一个简单又详细）

基础算法（快速，归并）

快速排序的定义：

快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）的思想。它的核心是通过选择一个基准元素（pivot），将列表分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为 O(n log n)，在实际应用中性能优异。

解释：

比如一个班级里面有10位同学，现在老师要按照高低进行排队（左低右边高），在10个里面随便挑一个为基准，然后在从基准左右边，开始一个一个的对比老师挑选的孩子基准（就比如调的最中间的）右边要查找低于基准，左边就查找高于基准（如果低于就放到基准左边）（高于就放到基准右边），这样全部查找完第一遍就会左边全部小于或者等于基准右边呢相反，无论排序第一遍（是否已经成功）（就是从低到高排列完基本上第一遍是不会的）这个基准最终位置就能定下来，因为左边都是低于他的右边都是高于他的，

接下来只需要，1.左边部分为一个整体，循环这个排序，2.右边部分也分为一个整体，循环这个排序最终就能完成。

步骤：

1.选择基准元素：

从列表中选择一个元素作为基准（pivot）。选择方式可以是第一个元素、最后一个元素、中间元素或随机元素。

2.分区：

将列表重新排列，使得所有小于基准元素的元素都在基准的左侧，所有大于基准元素的元素都在基准的右侧。基准元素的位置在分区完成后确定。

3.数组模拟栈来替代递归调用：

对基准元素左侧和右侧的子列表分别递归地进行快速排序。就是可以用不是递归循环，就怕最坏的结果，就是刚好他们相等或者说是选的第一个是最大的右边都是最小的，这样递归深度太大容易导致栈溢出.

​​​​​​​4.合并：

由于分区操作是原地进行的，递归结束后整个列表已经有序。

首先呢，我们定义一个结构体Range，还有一个结构体函数new_Range(这个结构体函数可不是多余，我们如果说手动赋值容易出错，并且又可能产生冗余代码。)

/* 定义表示区间的结构体，包含起始和结束位置 */ typedef struct _Range { int start, end; } Range; /* 创建并返回一个新的Range结构体实例 */ Range new_Range(int s, int e) { Range r; r.start = s; r.end = e; return r; }

接下来就是核心代码：（默认从小到大排序）

void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }//这个是交换代码嘛，t就相当于空瓶子将两个值互换后函数结束t的生命周期也结束了.但*x，*y是接收我们指向的数组元素要用到指针

核心函数快速排序

第一步

创建函数加上参数（第一个数组，第二个是我们数组的长度为固定值），加上我们用动态内存来控制区间的分配，当然这个用数组也可以，但是visual studio 2022不兼容这个数组我放到下面重点讲数组（概念）虽然动态更好，我们只要了解这个算法就可以

数组就是：

Range r[len];就行用栈来控制，但是一般就是比较小大的话动态是最好，它的作用就是来存储我们要排序的子序列的下标.比如r[0]就是（strat，end），后面会用这个求出mid的值中间数区分左边区域和右边区域

不好意思这个里面也比较详细，可能手机看的话比较小一点，点开放大看好些

核心

1.进行我们的初始化我们创建的存储待排序子序列栈.

2.开始判断要排序的数组是否是超过0个是否符合逻辑，你们可以自己理解

3.求出我们的中间调出的值mid来平分，左右两边.

4.进入算法反向思维，左边大于中间值，也就是中间值小于左边的值，这样条件不成立就会找到需要交换位置的值，然后跳到下一个找右边的，反之亦然。

5.开始利用函数交换出来之后，就要进行下一步处理，判断我们左右2个子区域还有没有要进入待排序的，然后将我们的栈加一，到最面r[--p],就是将我们以及排序的子序列栈排出去.

打印函数：

这个输出函数用于检测，不多讲解了.

主函数：

这个就是初始化，调用.你也可以用开辟的空间来存储，你直接输入的，然后排序.这个你们可以私下里面尝试这做一下.

希望我们也可以相互学习，我就是一个小白，不过可以帮助大学里面学习的基础c语言免费回答感谢感谢！！！QQ群号：238038904(c语言和嵌入式学习讨论群)