快速排序是一种分治算法。它通过一趟排序将数据分割成独立的两部分,然后再分别对这两部分数据进行快速排序。
本文将用3种方法实现：
霍尔法是一种快速排序中常用的单趟排序方法，由霍尔先发现。
它通过选定一个基准数（通常是第一个元素），然后利用双指针和方式进行排序，指针先找比基准值小的数，然后找比基准值大的数，找到后将两个数交换位置，同时实现大数右移和小数左移，当与相遇就排序完成，然后将下标的值与交换，返回基准数的下标，完成了单趟排序。这一过程使得基准数左侧的元素都比基准数小，右侧的元素都比基准数大。
-
同样的步骤，重复上述遍历，直到遍历完数组
- 选择基准值(),将其值保存到另一个变量中作为"坑"
- 从左往右扫描,找到小于基准值的元素,将其值填入"坑"中,然后"坑"向右移动一个位置
- 从右往左扫描,找到大于或等于基准值的元素,将其值填入移动后的"坑"中
- 重复步骤和,直到左右两个指针相遇
- 将基准值填入最后一个"坑"位置
- 对基准值左右两边递归分治，【】 【】重复上述过程,实现递归排序
与双指针法相比,挖坑法在处理基准值时使用了额外的"坑"变量,简化了元素交换的操作,但思想都是利用基准值将数组分割成两部分。
代码如下：
当你讨厌挖左边的坑，可以试试右边的坑😉：
代码如下：
✏️优化快速排序
为什么要使用随机数选取?
避免最坏情况,即每次选择子数组第一个或最后一个元素作为这样会导致时间复杂度退化为。
随机化可以减少排序不均匀数据对算法性能的影响。
相比固定选择第一个或最后一个元素,随机选择key可以在概率上提高算法的平均性能。
这里是优化快速排序使用随机数选取的方法:
- 在划分子数组前,随机生成一个区间中的随机数，
- 将随机处的元素与区间起始元素交换
- 使用这个随机索引取出子数组中的元素作为keyi。
随机选key逻辑代码：
有无序数列数组的首和尾后，我们只需要在首，中，尾这三个数据中，选择一个排在中间的数据作为基准值，进行快速排序，减少极端情况,进一步提高快速排序的平均性能。
代码实现：
取中的返回函数接收：
整体函数实现：
优点在于:对于小区间,插入排序效率高于快速排序的递归开销大部分数组元素位于小区间中，采用插入排序可以省去90%左右的递归调用，但整体数组规模大时,主要工作还是由快速排序完成
与三数取中进行合用
代码实现步骤:
- 初始化一个栈用于保存待排序子数组的起始和结束位置。
- 将整个数组的起始和结束位置压入栈中。
- 循环执行以下步骤，直到栈为空：
出栈，获取当前待排序子数组的起始和结束位置。
进行单趟排序，选取基准数，并将小于基准数的元素移到左边，大于基准数的元素移到右边。
根据基准数的位置，将分区的起始和结束位置入栈。 - 排序结束。
代码实现
以下是栈的实现：
Stack.c
栈的头文件实现：
快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
因此
时间复杂度：
什么情况快排最坏：有序/接近有序 ->
但是如果加上随机选key或者三数取中选key，最坏情况不会出现，所以这里不看最坏