Javaソートアルゴリズムを素早くマスター - クイックソート（画像とテキスト）

#コンセプト

クイック並べ替えは交換並べ替えです。主な手順は、比較に参照要素を使用することです。基準要素より小さい要素を並べ替えると、ベース要素より大きい要素は一方の側に移動し、ベース要素より大きい要素は反対側に移動します。したがって、配列は 2 つの部分に分割され、次にその 2 つの部分から参照要素が選択され、上記のステップが繰り返されます。プロセスは次のとおりです。

(推奨ビデオ:

java ビデオ チュートリアル )

紫: 基本要素

緑色: 基本要素 ## より大きい# 黄色: ベースライン要素未満

#この考え方は分割統治と呼ばれます。

基本要素

データム要素の選択はランダムに選択できます。次の使用では、最初の要素を基本要素として使用します。

並べ替えプロセス

並べ替えと分割のプロセスは次のとおりです。

紫は基本要素です ( で再選択されています)。各ラウンド)

緑はその他の要素

第一ラウンド

第二ラウンド

第三ラウンド

上図に示すように:

要素数が n の場合、ソート処理はすべての要素を比較する必要があるため、時間計算量は O( n),

平均して、ソート ラウンドには logn ラウンドが必要であるため、クイック ソートの平均時間計算量は O(nlogn) です。

#分別の実施方法

実施方法には両側循環方式と片側循環方式があります

双方向循環方式

最初の選択肢は、ピボット要素 (ピボット) 4 を選択し、次のように配列の左端と右端の要素を指すようにポインターを左右に設定することです。

First このループでは、まず右ポインタ (rightData) が指すデータから開始し、基本要素と比較します。

rightData >= pivot の場合、右ポインタは左に移動します。 . rightData 左ポインタ (leftData) が指すデータが参照要素と比較されます。 leftData pivot の場合、left と right が指す要素が交換されます。

最初のポインタの移動の後、次の構造が得られます。

次に、left と right が指す要素が交換されます。

ループの最初のラウンドが終了し、再び右ポインタに切り替えて、上記の手順を繰り返します。

2 番目のサイクルの後、次の結果が得られます:

3 番目のサイクルの後、次の結果が得られます:

4 サイクル後、次の結果が得られます。

左右のポインタが同じ要素を指していると判断され、ポインタの動きが停止し、ピボットとポインタが移動します。

サイクルの終了を宣言し、Pivo​​t 要素に従って 2 つの部分に分割します。これら 2 つの部分の配列は、次に従って操作されます。上記の手順に進みます。

実装コード

public class DoubleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left = pivot) {
                right--;
            }

            // 控制left指针比较并右移
            while (left <p></p>片ループ方式<p id="实现代码" style="white-space: normal;"><strong></strong>双方向ループ方式は、配列の両側の要素を比較して交換します。片側ループ ルールは配列の片側から走査し、逆方向に比較および交換するため、実装が容易になります。 </p>プロセスは次のとおりです。 <p id="单边循环法" style="white-space: normal;"><strong></strong>最初に、ピボット要素が選択されます (ランダムに選択できます) </p>マーク ポインタを、配列の開始位置を指すように設定します。ベースライン要素よりも小さい領域境界 (理解できません。後で要素を交換するために使用されると理解してください) <p><br></p>元の配列は次のとおりです: <blockquote>
<p><br> </p>
<blockquote><p>从基准元素下一位开始遍历数组<br>如果该元素大于基准元素，继续往下遍历<br>如果该元素小于基准元素，mark指针往右移，因为小于基准元素的区域边界增大了1（即小于基准元素的多了1位），所以mark就 +1，并且该元素和mark指向元素进行交换。</p></blockquote>
<p>遍历到元素3时，因为3 </p>
<p><img src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-12.jpg" alt="Javaソートアルゴリズムを素早くマスター - クイックソート（画像とテキスト）"></p>
<p>然后交换元素</p>
<p><img src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-13.jpg" alt="Javaソートアルゴリズムを素早くマスター - クイックソート（画像とテキスト）"></p>
<p>然后就继续遍历，根据上面的步骤进行判断，后面的过程就不写了。</p>
<p id="实现代码-1" style="white-space: normal;"><strong>实现代码</strong></p>
<pre class="brush:php;toolbar:false">public class SingleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 分治（单边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int mark = startIndex;

        for(int i = startIndex + 1; i<p id="总结" style="white-space: normal;"><strong>总结</strong></p><p>本人也是初次接触算法，慢慢的去理解算法的思路和实现过程后，真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象，若文章有不足之处，恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(･ω･)ﾉ。</p><p>参考资料：《小灰的算法之旅》 第四章。</p><p>本文来自php中文网，<a href="https://www.php.cn/java/base/" target="_blank">java教程</a>栏目，欢迎学习！  </p>

以上がJavaソートアルゴリズムを素早くマスター - クイックソート（画像とテキスト）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。