0

私が持っている資料によると、Javaでクイックソートを学んでいます。最良のケースはピボットが中央値であり、最悪のケースはピボットの片側が常に空である場合です。

次のコードでは、「indexPartition」がピボットですか? 最悪の状況で実行されるように、次の関数にどのようなパラメーターを入れますか?

    private void quickSortSegment(E[] list, int start, int end)
{
  if (end-start>1) 
  { 
     int indexPartition = partition(list, start, end);
     quickSortSegment(list, start, indexPartition);
     quickSortSegment(list, indexPartition+1, end);
  }
}

private int partition(E[] list, int start, int end)
{
  E temp; 
  E partitionElement = list[start];
  int leftIndex = start; 
  int rightIndex = end-1;
  while (leftIndex<rightIndex)
  {  
    while (list[leftIndex].compareTo(partitionElement) <= 0 && leftIndex<rightIndex)
    {
        leftIndex++; 
    }
    while (list[rightIndex].compareTo(partitionElement) > 0)
    {
        rightIndex--; 
    }
     if (leftIndex<rightIndex)
     {  
        temp = list[leftIndex];
        list[leftIndex] = list[rightIndex];
        list[rightIndex] = temp;
     }
  }
  list[start] = list[rightIndex];
  list[rightIndex] = partitionElement;
  return rightIndex;
}
4

3 に答える 3

1

動画のクイック並べ替え

ウィキペディアの記事と一緒にこのビデオは、物事をクリアする必要があります. ウィキペディアは、並べ替えアルゴリズムを説明するのに非常に優れています。あなたの質問に関してindexPartitionは、ピボットrightIndexのインデックスであるです。partitionElement

于 2013-06-20T09:08:42.060 に答える
1

このメソッド partition() に問題があります。たとえば、{3,1,2} の場合、{1,3,2} が返されます。

public class CompareApp {
public static void main(String... args) {
    Integer[] arr = {3, 1, 2};
    quickSortSegment(arr, 0, 2);
    for (Integer i : arr) System.out.println(i);
}

private static <E extends Comparable> void quickSortSegment(E[] list, int start, int end) {
    if (end - start > 1) {
        int indexPartition = partition(list, start, end);
        quickSortSegment(list, start, indexPartition);
        quickSortSegment(list, indexPartition + 1, end);
    }
}


private static <E extends Comparable> int partition(E[] list, int start, int end) {
    E temp;
    E partitionElement = list[start];
    int leftIndex = start;
    int rightIndex = end - 1;
    while (leftIndex < rightIndex) {
        while (list[leftIndex].compareTo(partitionElement) <= 0 && leftIndex < rightIndex) {
            leftIndex++;
        }
        while (list[rightIndex].compareTo(partitionElement) > 0) {
            rightIndex--;
        }
        if (leftIndex < rightIndex) {
            temp = list[leftIndex];
            list[leftIndex] = list[rightIndex];
            list[rightIndex] = temp;
        }
    }
    list[start] = list[rightIndex];
    list[rightIndex] = partitionElement;
    return rightIndex;
}}

java system.compare.CompareApp

1 3 2

于 2013-06-20T10:07:10.623 に答える