java - 无法理解为什么我的排序算法这么慢

Question

所以我正在尝试快速排序，我注意到一些奇怪的事情，每当我对超过 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);

    }
   }
}

Answer 1

我处理算法(特别是递归算法)的方式是遵循以下粗略计划:

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

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

在你的例子中，很少有小问题，但是递归问题中的小问题可能会成倍增加! :-)

首先，尝试上面的方法 - 如果您仍然遇到困难，可以在以下位置找到一个非常好的简单实现:Bob Sedgewicks algorithm site

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