我认为QuickSort在某些特定情况下可能会导致堆栈溢出异常。
在排序过程中有两种选择主元元素的基本方法 - 主元值可以是排序范围中间的元素,也可以是随机选择的元素(在排序范围内)。第二种方法(随机)是否比第一种方法更不容易发生堆栈溢出?您能给我建议吗?
这是我的快速排序版本(Delphi):
procedure QuickSort(lLowBound, lHighBound: integer; lCompare: TListSortCompare;
lSwap: TListSortSwap);
procedure Sort(lLowIndex, lHighIndex: integer);
var
lLeft: Integer;
lRight: Integer;
lPivot: Integer;
lLeftCompare: Integer;
lRightCompare: Integer;
begin
repeat
lLeft := lLowIndex;
lRight := lHighIndex;
lPivot := (lLowIndex + lHighIndex) div 2; //the pivot as the element in the middle
//lPivot := lLowIndex + Random(lHighIndex - lLowIndex + 1); //the pivot chosen randomly
repeat
lLeftCompare := lCompare(lLeft, lPivot);
while lLeftCompare < 0 do
begin
Inc(lLeft);
lLeftCompare := lCompare(lLeft, lPivot);
end;
lRightCompare := lCompare(lRight, lPivot);
while lRightCompare > 0 do
begin
Dec(lRight);
lRightCompare := lCompare(lRight, lPivot);
end;
if lLeft <= lRight then
begin
if not ((lLeftCompare = 0) and (lRightCompare = 0)) then
begin
lSwap(lRight, lLeft);
if lPivot = lLeft then
lPivot := lRight
else if lPivot = lRight then
lPivot := lLeft;
end;
Inc(lLeft);
Dec(lRight);
end;
until lLeft > lRight;
if (lLowIndex < lRight) then
Sort(lLowIndex, lRight);
lLowIndex := lLeft;
until lLeft >= lHighIndex;
end;
begin
if lHighBound > lLowBound then
Sort(lLowBound, lHighBound);
end;
感谢您提前提出建议!
马吕斯。
最佳答案
使用特定索引(第一个、最后一个或中间)处的任何元素作为主元元素总是会带来特定数据集退化的风险。第一个和最后一个元素特别糟糕,因为它们会随着预排序(或接近预排序)的数据而退化,这很常见。中间元素在实践中问题较少,但仍然容易受到恶意构建的数据集的影响。
使用随机元素意味着退化只能通过纯粹的运气不好而发生(假设 RNG 无法被假设的攻击者预测),所以这是一个很好的策略。显着降低遭遇厄运的可能性的进一步改进是使用 3 个(或 5 个或更多)随机选择元素的中值,但必须根据由此产生的额外复杂性和运行时间进行权衡。
关于delphi - 快速排序和堆栈溢出异常,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/944289/