三路快排改进
来源：3-8 三路快速排序法
Super波神
2019-01-07
老师，三路快排中设置第一个边界lt（我这里是i）为start - 1，这样最后就不用再进行一次赋值操作了，对吧？
void QuickSort3Ways(int arr[], int start, int end){
if (start >= end)
return;
int e = arr[start];
int i = start - 1; // arr[start,...i] < e 初始为空
int j = end + 1; // arr[j,...end] > e 初始为空
int v = start;
while (v < j){
if (arr[v] == e)
v++;
else if (arr[v] < e){
swap(arr[i + 1], arr[v]);
i ++;
}
else{
swap(arr[v], arr[j - 1]);
j --;
}
}
QuickSort3Ways(arr, start, i);
QuickSort3Ways(arr, j, end);
}
写回答
4回答
-
赞！没有问题：）
你真正掌握了写出正确算法的精髓！只要变量的语义明确，维护住变量的语义，就能写出正确的算法：）
继续加油！：）
00 -
qq_漫笔_0
2021-09-16
代码666
00 -
潇潇雨歇兮我材天生
2020-03-28
代码的else if里边遗漏对 v 进行++操作了。可以直接简化索引为 ++i 和 v++。你觉得如何？
012021-09-16 -
小煜_
2019-09-16
老师您好 我想知道上边这个改进是将e放入==v的第一个位置,然后省去v++和交换的时间吗
012019-09-17
相似问题