1

所以我正在玩快速排序，我注意到一些奇怪的事情，每当我对超过 10 个值进行排序时，与插入排序相比，排序需要很长时间。任何时候我要求它对超过 10 个值进行排序，有人可以解释为什么它这么慢吗？也许这与代码有关。

编辑。我做了一些更改，现在我遇到了堆栈溢出错误，太好了。

       public class quicksorttest{
   public static void main(String args[]){
      int array[] = new int[100];
      for(int a =0; a<array.length;a++){
         array[a] = (int)(Math.random()*100);
      }

      quickSort(array,0,array.length);
   }

   public static void quickSort(int array[],int p, int q){
    if(q-p <=1);//skip

    else{
        int x; int i,j,k;
        //let x = middle element in f[p..q-1]. 

        x= array[(p+q/2)];
        i=p;j=p;k=q;
        while(j!=k){
            if(array[j]==x)
                j=j+1;
            else if(array[j]<x){    //swap array[j] with array[i]
                int temp =array[j];
                array[j] = array[i]; array[i]=temp;
                j=j+1;i=i+1;

            }
            else{//array[j]>x
                //swap array[j[ with array[k-1]
                int temp = array[j]; 
                array[j] = array[k-1]; array[k-1]=temp;
                k=k-1;
            }
        }

        quickSort(array,p,i);
        quickSort(array,j,q);

    }
   }
}
4

1 回答 1

0

我处理算法，特别是递归算法的方法是遵循以下粗略计划：

  • 从一个空数组开始
  • 尝试一个包含 1 个元素的数组
  • 尝试一个包含 2 个元素的数组（前三个元素很重要，因为它们通常是递归方法的最终状态/）
  • 尝试具有 3 或 4 个元素的数组，但尝试相同的集合一段时间，以便您可以重现结果。如果您使用随机集失败，但它在下一次运行时有效，您可能不知道您是否已解决问题或者您正在尝试的数据

只有当你重复上述工作后，你才应该尝试更大的数据集，然后最后尝试随机数据。

在您的情况下，几乎没有小问题，但是递归问题中的小问题可以成倍增加！:-)

首先，尝试上面的方法——如果你仍然卡住，可以在以下位置找到一个非常好的简单实现：Bob Sedgewicks algorithm site

值得添加 System.out.println 语句（对于小型数据集 - 对于大型数据集，这不太有用），或者更好的是使用调试器（IntelliJ、Eclipse、Netbeans 等）单步执行

于 2013-02-23T19:51:52.163 回答