排序算法之快速排序
2021-02-20 21:18
标签：变量 区间 平衡 第一个 for 操作 性能 需要 divide 算法描述： 快速排序也使用分治思想，其过程为： 分解：将原数组划分为两个子数组，但要求左边数组的每个元素都小于右边数组的每个元素。 解决：通过递归调用快速排序，对子数组进行排序。 合并：因为子数组是原址排序，所以不需要合并操作。 快速排序划分数组的方法： 1. 单方向遍历 选择最后一个元素为基准元素。记为x。 定义如下几个计数变量： i：闭区间[0, i]内的元素都≤x j：开区间(i, j)内的元素都>x，j为遍历使用的变量 代码解释：每次发现一个≤x的元素，都会放到第一个区间内，即[0,i]区间内，然后j++。 2. 双向遍历 排序算法实现： 时间复杂度分析： 快速排序的时间复杂度依赖于划分是否平衡，而平衡与否又依赖于用于划分的元素。 如果划分平衡，则其算法性能与归并排序一致，为O(nlgn)。 稳定性分析： 快速排序是不稳定的排序算法 排序算法之快速排序 标签：变量 区间 平衡 第一个 for 操作 性能 需要 divide 原文地址：https://www.cnblogs.com/yanghh/p/12680091.htmlint divide(int low, int high)
{
int x = data[high];
int i = low - 1; // 初时
int divide(int low, int high)
{
int x = data[high];
while(low x的元素
while(low low && data[high] >= x)
{
high--;
}
data[low] = data[high];
}
data[low] = x;
return low;
}
void QuickSort(int low, int high)
{
int mid = divide(low, high);
if(low
上一篇：java的方法