0

Javaでクイックソートを実装しようとしていますが、疑問が1つあります。だからここに私のクイックソートコードがあります：

package com.sorting;

public class QuickSort implements Sort {

@Override
public int [] sort(int[] arr) {
    return quickSort(arr, 0, arr.length - 1);
}

private int [] quickSort(int[] numbers, int low, int high) {

    if (low < high) {
        int q = partitionTheArrayAroundPivot(numbers, low, high);

        if (low < q)
            quickSort(numbers, low, q);

        if ((q+1) < high)
            quickSort(numbers, q + 1, high);
    }

    return numbers;
}

private int partitionTheArrayAroundPivot(int[] numbers, int low, int high) {

    int pivot = selectPivot(numbers, low, high);
    int i = low;
    int j = high;

    while (true) {

            while (numbers[i] < pivot) {
            i++;
        }

            while (numbers[j] > pivot) {
            j--;
        }

        if ( i <= j) {
            swap(numbers, i, j);
            i++;
            j--;
        } else {
            return j;
        }

    }

}

private int selectPivot(int[] numbers, int low, int high) {
    return numbers[high];
}

private void swap(int[] numbers, int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

}

疑問 1: >= ピボットの数値に到達するまで、インデックス i を増やし続けます。

while (numbers[i] < pivot)
    i++;

j同様に、<= ピボットの数値に達するまでインデックスを減らし続けます

while (numbers[j] > pivot)
    j--;

したがって、これは、両方のヒットが 2 つの異なる場所でピボットする場合、両方のインデックスもループから抜け出すことを意味します。たとえば、ピボットが 1 の場合、ここでは 1,0,1 であり、i は 0 になり、j は 2 になります。以下の条件は次のようになります。 if (i <= j) { .... } を満たす必要がありますが、その場合、上記の配列 (1,0,1) を並べ替えることができません。 i = j = 1 になります。その後、i は 3 番目の要素、つまり 1 にヒットし、再び値 i = 2 でループから抜け出し、同様に j = 0 となり、配列をソートできなくなります。

では、どこに問題があるのでしょうか。何か不足していますか？

4

2 に答える 2

0


while (numbers[i] <= pivot)and を使用するとwhile (numbers[j] >= pivot)、コードが機能します

于 2015-05-23T03:55:56.153 に答える
0

selectPivot が代わりにインデックスを返すように、コードを少し書き直します。

private int selectPivotIndex(int[] numbers, int low, int high) {
    return high;
}

次に、パーティショニング関数はピボットを脇に移動し、残りのアイテムをピボット値に従って並べ替えることができます。単一のループで実行できます。この実装では、ピボットの複製が右側に配置されます。

private int partitionTheArrayAroundPivot(int[] numbers, int low, int high) {

    int pivotIndex = selectPivotIndex(numbers, low, high);

    swap(numbers, pivotIndex, high); // Not needed if selectPivotIndex always returns high
    int newPivotIndex = low;
    for(int i = low; i < high; i++)
    {
        if(numbers[i] < numbers[pivotIndex])
        {
            swap(numbers, i, newPivotIndex);
            newPivotIndex++;
        }
    }
    swap(numbers, newPivotIndex, pivotIndex);

    return newPivotIndex;
}

quickSort最後に、永久ループに陥らないように、メソッドを少し調整する必要があります。

if (low < q)
      quickSort(numbers, low, q - 1);

このアプローチは、理解とデバッグが簡単です。うまくいくことを願っています。

于 2012-06-23T15:52:34.987 に答える