クイックソートが遅いのはなぜですか？

Question

私はいくつかのインタビューの準備の一環としてソートアルゴリズムを書くことを練習しています。なぜこのクイックソートがなぜ非常に速くないのか誰かが私を助けることができるのでしょうか？それは正しいランタイムの複雑さがあるように見えますが、私のマージソートより約2の定数で遅いです。私のコードを改善し、質問に必ずしも答えないコメントもありがとうと思います。

ありがとうございました！エチケットミスをしてしまったら、どうか私に知らせてください。これが私の最初の質問です。

private class QuickSort implements Sort { 

     @Override 
     public int[] sortItems(int[] ts) { 
      List<Integer> toSort = new ArrayList<Integer>(); 
      for (int i : ts) { 
       toSort.add(i); 
      } 
      toSort = partition(toSort); 
      int[] ret = new int[ts.length]; 
      for (int i = 0; i < toSort.size(); i++) { 
       ret[i] = toSort.get(i); 
      } 
      return ret; 
     } 

     private List<Integer> partition(List<Integer> toSort) { 
      if (toSort.size() <= 1) 
       return toSort; 
      int pivotIndex = myRandom.nextInt(toSort.size()); 
      Integer pivot = toSort.get(pivotIndex); 
      toSort.remove(pivotIndex); 
      List<Integer> left = new ArrayList<Integer>(); 
      List<Integer> right = new ArrayList<Integer>(); 
      for (int i : toSort) { 
       if (i > pivot) 
        right.add(i); 
       else 
        left.add(i); 
      } 
      left = partition(left); 
      right = partition(right); 
      left.add(pivot); 
      left.addAll(right); 
      return left; 
     } 

} 

お世話になりました皆さん、ありがとうございました！

これは後世のための私の非常に改善されたクラスである：クイックソートの最大の利点の

private class QuickSort implements Sort { 

     @Override 
     public int[] sortItems(int[] ts) { 
      int[] ret = ts.clone(); 
      partition(ret,0,ret.length); 
      return ret; 
     } 

     private void partition(int[] toSort,int start,int end) { 
      if(end-start<1) return; 
      int pivotIndex = start+myRandom.nextInt(end-start); 
      int pivot = toSort[pivotIndex]; 
      int curSorted = start; 
      swap(toSort,pivotIndex,start); 
      for(int j = start+1; j < end; j++) { 
       if(toSort[j]<pivot) { 
        if(j!=curSorted+1) 
         swap(toSort,curSorted,curSorted+1); 
        swap(toSort,j,curSorted++); 
       } 
      } 
      // Now pivot is at curSorted 
      partition(toSort,start,curSorted); 
      partition(toSort,curSorted+1,end); 
     } 
    } 

Answer 1

一つは、それがin-placeアルゴリズムとして実装することができるということです。新しいリストを作成せず、その代わりに要素をソートしないでください。

Answer 2

リストを再利用しないことに加えて、あなたは整数間の変換や、各ステップでint型：

 for (int i : toSort) { // converts from Integer to int 
      if (i > pivot) 
       right.add(i); // converts from int to Integer 
      else 
       left.add(i); // converts from int to Integer 
     } 

注一般的にint型から整数への変換は、作成する新しいオブジェクトが必要であること。

最後に、random.nextInt（）は単純な操作ではありません。おそらく、toSortが特定のサイズを超えている場合はランダムピボットを選択し、そうでない場合は単純なピボット選択戦略を使用する方が良いでしょう（Measure it！）。