Javaシーケンス分割問題アルゴリズム実装

Javaシーケンス分割問題アルゴリズム実装
問題の説明
入力:シーケンスA[p...r]出力:下付きq(p<=q<=r)と元のシーケンスA[p...r]の再配列新しい配列満足:A[q]=A[r]A[p...q]の各要素がA[q]A[q+1...r]の各要素よりA[q]より大きい
アルゴリズム思想
アルゴリズムはA[r]を利用してシーケンスを2つのセグメントに分ける必要があり、総長は依然としてrであり、左から右にシーケンスをスキャンすることができ、次第にA[r]より大きくない数とA[r]より大きい数を分離することができる.アルゴリズムは、iを現在の分割結果の境界線として使用する2つの下表i=p−1,j=pを維持する.すなわち、iより小さいすべてのスケールがiより大きいシーケンス数はA[r]より大きくなく、jを現在のスキャン位置として使用する.すなわち、iより大きいサイズがjより大きいシーケンス数はA[j]より大きい.i,jを初期化すると,j->rがインクリメントされ,A[j]がA[r]より小さいか否かが判断され,成立するとA[i+1],A[j]が交換される.
ここでは実際にi++を用いてA[r]未満の数を増やし、A[r]より大きい最初の数を最後に移動する.
j=rのとき,最終的な分割シーケンスを得た.
アルゴリズム実装

/**
 * 
 * @author Chuck
 *
 */
public class Partition {
    public static int partition(int [] arr){
        int n = arr.length;
        int i = -1;
        int j = 0;
        int tmp = -1;
        //        
        while(j < n){
            //              ，        arr[n-1]     ， A[i+1]
            if(arr[j] <= arr[n-1]){
                i++;
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
            j++;
        }
        //    
        return i+1;
    }

    public static void main(String [] args){
        int [] arr = {1,3,30,5,6,23,111,232,0,112,10,20};
        int q = Partition.partition(arr);

        System.out.println("q = " + q);
        for(int i=0;i" ");
        }


    }
}

アルゴリズム時間
f(n) = n = O(n)
プレゼンテーションの結果
q = 7 1 3 5 6 0 10 20 232 30 112 23 111