与快速排序算法混淆C#
问题描述:
我一直在研究如何在C#中为大学做快速排序。我几乎可以工作。只有几个数字没有按正确的顺序出现。 array:1,5,8,6,7,3,2,4,9 “sorted”into:1,5,4,6,2,3,7,8,9 instead of 1,2, 3,4,5,6,7,8,9。 不知道在哪里,我在我的代码会错:与快速排序算法混淆C#
int[] array4 = { 1, 5, 8, 6, 7, 3, 2, 4, 9};
QuickSort quick = new QuickSort();
quick.Quicksort(array4, 0, array4.Length - 1);
public void Quicksort(int[] array, int left, int right)
{
int pivot, temp;
pivot = array[(left + right/2)];
do
{
while ((array[left] < pivot) && (left < right))
left++;
while ((pivot < array[right]) && (right > left))
right--;
if (left <= right)
{
temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
while (left <= right);
if (left < right) Quicksort(array, left, right);
}
}
感谢
答
在你快速排序的方法,因为李的评论所指出的,你是不是调用带有的左侧和右侧部分的快速排序法分区/枢轴。
首先我相信你是不是在该行得到适当的支点:
pivot = array[(left + right/2)];
以上,师会先发生,所以它会分“右”两个再加入到“左”。这会给你一个错误的关键。它应该是:
pivot = array[(left + right)/2];
其次,当你进入快速排序的方法,你给出的起始索引值(左/右),并且使用这些变量来获得下一个支点。当你改变它们时,这将抛弃“左”和“右”STARTING索引。因此,您需要复制这些STARTING值并使用复制的值创建下一个分区/数据透视表。
以下是我对您的代码所做的更改,它似乎正常工作。
public static void Quicksort(int[] array, int left, int right)
{
int pivot, temp;
pivot = array[(left + right)/2];
int originalLeft = left;
int originalRight = right;
do
{
while (array[left] < pivot)
left++;
while (pivot < array[right])
right--;
if (left <= right)
{
temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
while (left <= right);
// note that the original left and right values are needed here
if (originalLeft < right)
Quicksort(array, originalLeft, right);
if (left < originalRight)
Quicksort(array, left, originalRight);
}
希望这会有所帮助。
+0
你的建议已修复它。我看到我要去哪里错了。 干杯! –
通常,当发生这种情况时,您不会在数组中的所有值中逗留。尝试更改输入数据并将'1'移动到列表的末尾。 – jdweng
您需要进行两个递归调用,一个用于左侧分区,另一个用于右侧。 – Lee