データ構造——配列の並べ替え方法

4938 ワード

データ構造

目次
一、泡の並べ替え
二、並べ替えの選択
三、直接並べ替えを挿入する
四、ヒルの並べ替え
五、快速並べ替え
参照リンク:https://blog.csdn.net/DallinC/article/details/84142209
一、泡の並べ替え
外部ループでは、最初のループはiであり、その後、アール1[i]とアール1[j]の各データを比較し、アール1[j]

        for (int i = 0; i < arr1.length; i++) {

            for (int j = i; j < arr1.length; j++) {
                if (arr1[j] < arr1[i]) {
                    int tempNum = arr1[i];
                    arr1[i] = arr1[j];
                    arr1[j] = tempNum;
                }
            }

        }

二、並べ替えの選択
最小値のインデックスと外層サイクルで比較中のデータ交換位置を選択します.
外循環では、最初の循環はiであり、その後、アール1[i]とアール1[j]の各データを比較し、より小さい値のインデックスをtempに割り当て、同時にアール1[temp]を使用して小さい値を表し、その後継続的に内部サイクルを行い、tempを更新し、アール1[temo]の値が最小となるようにする.
内部循環

は、先にtempでより小さい値のインデックスを表し、

を比較した後、tempを更新します.

その後、tempでより小さい値をインデックスします.

は第2ステップを行い、比較を続けます.

外循環:小さい値のarr 1[temp]とarr 1[i]を担当してデータの交換を実現します.

 for (int i=0;i

三、直接並べ替えを挿入する
最初の席は比較しなくてもいいです.
第二の位置から、最初の位置と比較し、小さい値を第一の位置に置く.
毎回隣り合っている二つの位置の比較です.

第3の位置が第2の位置より小さい場合、交換位置はその後、第1の位置と比較し続けることにより、この3つの数の正しい並べ替え

が実現される.

第三の位置が第二の位置より大きい場合、前の順序が並べられているので、交換は不要です.

は順次行って、(n-1)スキャンを行った後に全体の並べ替えの過程を完成しました.

    public static int [] sort(int[] arr1) {

        for (int i = 0; i < arr1.length; i++) {
            for (int j = i; j > 0 && arr1[j] < arr1[j - 1];) {
                int tempNum = arr1[j];
                arr1[j] = arr1[j - 1];
                arr1[j - 1] = tempNum;
                j--;

            }

        }
        return arr1;
    }

四、ヒルの並べ替え
参照コード:https://blog.csdn.net/qq_2808081/articale/detail/80598960
参考思想:https://blog.csdn.net/zhou_438/articale/detail/83715455
gapグループによると、グループ内で直接挿入順序が実現され、gap==1まで、ループが終了する.

package com.example.priorityqueue;

class Solution {
    public static int[] shellSort(int[] ins) {

        int n = ins.length;
        int gap = n / 2;
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
//                               
                for (int j = i; j >= gap && ins[j] < ins[j - gap]; ) {
                    int temp = ins[j - gap] + ins[j];
                    ins[j - gap] = temp - ins[j - gap];
                    ins[j] = temp - ins[j - gap];
                    j -= gap;
                }
            }
            gap = gap / 2;
        }
        return ins;
    }


    public static void main(String args[]) {
        Solution solution = new Solution();
        int[] arr = new int[]{9, 71, 37, 56, 88, 96, 21, 5, 48, 43};
        shellSort(arr);
        for (int x = 0; x < arr.length; x++) {
            System.out.print(arr[x] + ",");
        }
    }
}

五、快速並べ替え
参照コード:https://blog.csdn.net/WZL995/article/details/88365958
参考思想:https://www.cnblogs.com/dev1ce/p/10618478.html
高速並べ替えのアルゴリズム思想:
9、71、37、56、88、96、21、58、48、43 配列要素
0、1、 2、 3、 4、 5、 6、 7、 8、9 配列下付き
配列の中のある要素を選択します.要素の左側の配列要素はこの要素に等しくないようにします.配列の右側の要素はこの要素より大きいです.
例えば、要素58を選択して、配列を上記規則に従って第1ラウンドの順序付けを行う.
9、37、56、21、48、43、58、88、96.
第1ラウンドの並べ替えで上記の規則を満たします.
第二ラウンドは58の両側の配列を再度上記の規則に従って並べ替えます.(配列が不可分になるまで再帰的な思想を採用する)
があります
以上の考えから、ある元素をどのように計算するかが非常に重要です.実際にこの元素の位置を計算するのが本質です.これも高速ソートの中心です.
迅速な並べ替えの実現には「元の場所の並べ替え」が採用されている.つまり元の配列で並べ替えられ、正規化と並べ替えには追加の空間が必要です.
実現の考え方は、元の配列を3つの部分に分け、以下はある要素に等しく、ある要素より大きい.

package com.example.priorityqueue;

class Solution {
    public static int getMiddle(int[] arr, int low,int high)
    {
        int temp = arr[low]; //               
        while(low < high)
        {
            while(low < high && arr[high] > temp)
            {
                high--;
            }
            arr[low] = arr[high];//           
            while(low < high && arr[low] < temp)
            {
                low++;
            }
            arr[high] = arr[low] ; //           
        }
        arr[low] = temp ; //         
        return low ; //              
    }
    public static void QuickSort(int [] arr,int low,int high) {
        if(low < high)
        {
            int middle = getMiddle(arr,low,high); // arr        
            QuickSort(arr, low, middle-1);   //           
            QuickSort(arr, middle+1, high); //           
        }
    }



    public static void main(String args[]) {
        Solution solution = new Solution();
        int[] arr = new int[]{9, 71, 37, 56, 88, 96, 21, 5,48, 43};
        QuickSort(arr,0,arr.length-1);
        for(int x = 0;x < arr.length;x++){
            System.out.print(arr[x]+",");
        }


    }
}