递归实现快速排序的超长计算时间

问题描述 投票:0回答:1

我试图实现一个快速排序算法,但它似乎有一些不好的行为。它确实对一组元素进行了排序,但它花费了太多时间,确切地说,它花费了大约 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;
                 }
            }
       }          
 }
c# recursion quicksort
1个回答
1
投票

请看下面一行

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
本身发生变化,我们将丢失这些信息。

© www.soinside.com 2019 - 2024. All rights reserved.