我试图实现一个快速排序算法,但它似乎有一些不好的行为。它确实对一组元素进行了排序,但它花费了太多时间,确切地说,它花费了大约 165 个元素的这么多时间,它还没有完成一次(运行了几分钟)。我尝试调试并意识到可能需要多次迭代才能完成,但仍会产生正确的输出。代码是在继承 List 的类中编写的,应该递归编程。我做错了吗?我觉得这个过程需要太多的迭代。我的意思是,它是调用 QUICKsort.
这是代码:
using System;
using System.Collection.Generic;
public class PersonList : List<Person>{
public void quickSort(int start, int end){
if(start < end){
int pivot = partition(start, end);
if(pivot > 1){
quickSort(start, end -1);
}
if(pivot + 1 < end){
quickSort(pivot + 1, end);
}
}
}
public int partition(int start, int end){
Person per = new Person();
int tmp = this[start].ID;
while(true){
while(this[start].ID < tmp){
start++;
}
while(this[end].ID > tmp){
end--;
}
if(start < end){
if(this[start].ID == this[end].ID){
return end;
} else{
per = this[start];
this[start] = this[end];
this[end] = per;
}
} else{
return end;
}
}
}
}
请看下面一行
quickSort(start, end -1);
QuickSort 是一种分而治之的算法,它将其操作的数据集划分为更小的块,并递归地对更小的块进行操作(然后将它们分开)。您在这里所做的是,您不是在数据集的下“一半”(它应该如何工作)上调用 QuickSort,而是在被最顶层项目减少的数据集上调用。由于这条线,递归在比预期更大的数据集上运行,因此需要更长的时间。
对缩减数据集进行操作的正确行是
quickSort(start, pivot)
由于数据点是相对于枢轴元素进行预排序的,因此您可以将数据集划分为低于和高于枢轴元素的块。因此我什至相信
quickSort(start, pivot - 1)
就足够了。
编辑
根据德语维基百科(伪代码应该是可读的,虽然它是德语)代码应该看起来更像
private int Partition(int start, int end)
{
var pivot = end;
var i = start;
var j = end - 1;
int tmp = this[pivot].ID;
do
{
while (this[i].ID < tmp && i < end)
{
i++;
}
while (this[j].ID > tmp && j > start)
{
j--;
}
if (i < j)
{
Swap(i, j);
}
}
while (i < j);
if (this[i].ID > tmp)
{
Swap(i, pivot);
}
return i;
}
我们必须使用单独的循环变量,因为它们是根据
start
和 end
检查的,如果 start
和 end
本身发生变化,我们将丢失这些信息。