大体思路是修改Partition方法将原本枢数的调整放到方法结束后去做。
这样因为数组右侧第一个大于当前枢数的位置就应该是未划分的子数组的边界。
然后继续进行Partition调整。
这种写法照比递归的写法多出一个向右寻找边界的过程，该过程的平均时间复杂度为Θ(nlogn)。
这样快速排序的算法平均复杂度乘以了常数项2，而空间复杂度缩小到Ο（1）。
private static void QSort(int[] array)
{
int leftLow, leftHeight, rightLow, rightHeight;
int tempLow, tempHeight, key, temp;
leftLow = 0;
leftHeight = leftLow;
rightLow = array.Length - 1;
rightHeight = array.Length - 1;
tempLow = -1; tempHeight = -1; key = -1;
while (rightHeight > leftLow)
{
while (leftHeight + 1 < rightLow)
{
key = leftHeight;
tempLow = leftHeight + 1;
tempHeight = rightLow;
while (tempLow < tempHeight)
{
while (tempLow < rightHeight && array[tempLow] < array[key])
{
tempLow++;
}
while (leftHeight < tempHeight && array[key] <= array[tempHeight])
{
tempHeight--;
}
if (leftLow < tempHeight && tempLow < rightHeight && tempLow < tempHeight)
{
temp = array[tempLow];
array[tempLow] = array[tempHeight];
array[tempHeight] = temp;
}
}
if (rightHeight == tempHeight && leftHeight ==leftLow )
{
temp = array[rightLow];
array[rightLow] = array[leftHeight];
array[leftHeight] = temp;
rightHeight--;
rightLow--;
continue;
}
rightLow = tempHeight;
if (key == tempHeight)
{
break;
}
else if (key < tempHeight && tempLow > tempHeight)
{
leftHeight++;
}
}
if (leftHeight != leftLow)
{
if (leftHeight < rightLow)
{
if (array[leftHeight] < array[rightLow])
{
temp = leftHeight;
}
else
{
temp = rightLow;
rightLow++;
leftHeight++;
}
}
else
{
temp = rightLow;
rightLow++;
}
key = array[temp];
for (int i = temp; i > leftLow; i--)
{
array[i] = array[i - 1];
}
array[leftLow] = key;
leftLow++;
while (rightLow <= rightHeight && array[rightLow] < array[leftHeight])
{
rightLow++;
}
if (rightLow > rightHeight)
{
rightLow--;
}
}
else
{
rightLow = rightHeight;
leftLow++;
leftHeight++;
}
}
if (array[rightHeight] < array[rightHeight - 1])
{
temp = array[rightHeight];
array[rightHeight] = array[rightHeight - 1];
array[rightHeight - 1] = temp;
}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。