0

このアプリのピボットとして中央値を選択しようとしていますが、何か間違ったことをしているようです。どんな助けでも大歓迎です。

最初のいくつかの番号を順番に取得し、最後に向かって取得します。

    public class QuickSort {

    public static void main(String[] args) {
    int [] list = {1,3,2,4,6,5,8,7,9,0};
    quickSort (list);

    for (int i=0; i < list.length; i++)
        System.out.print(list[i] + " ");
}
public static void quickSort(int [] list)
{
    quickSort(list, 0, list.length - 1);
}

public static void quickSort (int[] list, int first, int last)
{
    int size = last - first + 1;
    if (size > 3){
        int median1 = median(list, first, last);
        int partition1 = partition(list, first, last, median1);
        quickSort(list, first, partition1 - 1);
        quickSort(list, partition1 + 1, last);
    }
}
    public static int median(int [] list, int first1, int last1){
        int middle = (first1 + last1)/2;
        if (list[first1] > list[middle])
            swap(list, first1, middle);
        if (list[first1] > list[last1])
            swap(list, first1, last1);
        if (list[middle] > list[last1])
            swap(list, middle, last1);
        swap(list, middle, last1 - 1);
        return list[last1 - 1 ];
    }
    public static int partition(int [] list, int left, int right, long pivot) {
        int leftPtr = left;
        int rightPtr = right - 1; 

        while (true) {
          while (list[++leftPtr] < pivot);

          while (list[--rightPtr] > pivot);
          if (leftPtr >= rightPtr) 
            break;
          else
            swap(list, leftPtr, rightPtr); 
        }
        swap(list, leftPtr, right - 1);
        return leftPtr; 
    }
       public static void swap(int []list, int dex1, int dex2) {
         int temp = list[dex1];
         list[dex1] = list[dex2];
          list[dex2] = temp;
            }

いくつかの番号を順番に取得しますが、すべてではありません。

4

1 に答える 1

1

通常、コンピュータプログラミングに使用できるアプローチは2つあります。次のいずれかを行うことができます。a）うまくいくものを取り、好きなものが得られるまで、ものの削除/変更を開始します。またはb）可能な限り最小のケースを取り、それを機能させてから、さらに複雑さを追加し続けます。この場合、私はb）（FYI b）が通常最良のアプローチであることを提案します）

int [] list = {3、1、}で開始すると、リストが正しくソートされていないことがわかります。これは、quickSort関数が3より大きいサイズのリストのみをソートしているためです。この場合、この条件はおそらく「サイズ> 1」であるはずですが、動作させるにはさらにいくつかの作業が必要になる場合があります。

ウィキペディアにはQuickSortに関する多くの情報があります：http： //en.wikipedia.org/wiki/Quicksort

于 2013-03-22T04:11:04.130 に答える