ホームページ  >  記事  >  Java  >  Javaでクイックソートアルゴリズムを実装するというアイデアは何ですか?

Javaでクイックソートアルゴリズムを実装するというアイデアは何ですか?

王林
王林オリジナル
2020-06-10 10:40:403196ブラウズ

Javaでクイックソートアルゴリズムを実装するというアイデアは何ですか?

1. クイック ソート アルゴリズムとは何ですか?

実際、クイック ソート (クイックソート) はバブル ソートを改良したものです。

2. 高速ソート アルゴリズムの考え方

ソート対象のデータは 1 回のソートによって 2 つの独立した部分に分割され、1 つの部分にあるすべてのデータはすべてのデータよりも上位になります。他の部分のデータは小さい必要があるため、この方法を使用してデータの 2 つの部分をそれぞれすばやく並べ替えます。並べ替えプロセス全体は再帰的に実行できるため、データ全体が順序付けされたシーケンスになります。

(ビデオ チュートリアルの推奨: java ビデオ チュートリアル)

3. 実装のアイデア

(1) 最初のキーワード K 1 をコントロール ワードとして使用します。 [K 1 ,K 2 ,…,K n ] を 2 つのサブ領域に分割し、左側の領域のすべてのキーワードが K 1 以下、右側の領域のすべてのキーワードが K 以上になるようにします。 1 、そして最後に制御ワードは 2 つのサブエリアの中央に配置されます。サブエリア内のデータはまだ順序付けされていない状態です。 ;

(2) 左側の領域を全体として扱い、(1) の手順で処理し、右側の領域も同様に処理します。 (つまり、再帰)

(3) 左側の領域が処理されるまで、手順 (1) と (2) を繰り返します。

4. 実装コード

static void quicksort(int n[], int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp - 1);
            quicksort(n, dp + 1, right);
        }
    }
 
    static int partition(int n[], int left, int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }

推奨チュートリアル: javaエントリープログラム

以上がJavaでクイックソートアルゴリズムを実装するというアイデアは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。