データ構造とアルゴリズムの並べ替え(まとめ1)

10132 ワード

ソートは、実際に開発された最もよく使用されるいくつかのアルゴリズムの1つであり、ソート中に根拠となる原則に従って内部ソートを分類すると、挿入ソート、交換ソート、選択ソート、集計ソートなどのソート方法に大きく分けることができます.まず、ソートを挿入するアルゴリズムがどのようなものであるか、およびそれらの具体的な実装を見てみましょう.挿入ソートの基本的なソート思想は、各ソート対象要素を1つずつ考察し、各新しい要素を前に並べられたシーケンスの適切な位置に挿入し、新しいシーケンスが依然として秩序化されたシーケンスであるようにすることである.このクラスのソートでは、直接挿入ソート、折半挿入ソート、ヒルソートの3つのソート方法について主に説明します.
 
1.ソートの直接挿入
 
a.アルゴリズムの説明
 
直接挿入ソートは最も簡単な挿入ソート方法であり、その基本思想は:1つの要素のシーケンスだけが常に秩序化されているため、n個の記録されたシーケンスに対して、2番目の要素からn個目の要素まで、1つずつ秩序化シーケンスに挿入操作を実行し、それによってn個の要素がキーワードで秩序化されたシーケンスを得ることができる.一般的に、j−1個の要素を含む秩序あるシーケンスに1個の要素を挿入する方法は、j−1個目の要素から順に挿入すべき位置を前方に検索し、挿入位置を検索しながら要素を後方に移動することで、適切な挿入位置が見つかった場合に直接要素を挿入することができる.キーワードシーケンス{26,53,48,11,13,48,32,15}を例に、ソートを直接挿入する手順を以下に示す.
 
 
 
b:アルゴリズム実装
  

　　

 

public void insertSort(int[] r, int low, int high) {

    for (int i = low + 1; i <= high; i++)

        if (compare(r[i], r[i - 1])) { //    ，  r[i]     

            int temp = r[i];

            r[i] = r[i - 1];

            int j = i - 2;

            for (; j >= low && compare(temp, r[j]); j--)

                r[j + 1] = r[j]; //     

            r[j + 1] = temp; //        

        }

}

　　

　　
 
【効率分析】
スペース効率:1つの補助ユニットのみが使用されます.
時間効率:並べ替えられる要素の個数がnであると仮定すると、順序テーブルにレコードを1つずつ挿入する操作がn−1回行われ、各操作は比較キーと移動レコードに分けられ、比較回数と移動レコードの回数は、並べ替えられるシーケンスのキーコードによる初期列に依存する.直接挿入ソートの時間的複雑度はO(n²)
 
c:実装例
  
　　StraightInsertionSort.java

 

 

package com.test.sort.insertion;

 

public class StraightInsertionSort {

 

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        System.out.println("            》》》》");

        int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };

 

        StraightInsertionSort sort = new StraightInsertionSort();

        System.out.println("      ：");

        sort.printArr(arr);

        sort.insertSort(arr, 0, arr.length - 1);

        System.out.println("      ：");

        sort.printArr(arr);

    }

 

    public void insertSort(int[] r, int low, int high) {

        for (int i = low + 1; i <= high; i++)

            if (compare(r[i], r[i - 1])) { //    ，  r[i]     

                int temp = r[i];

                r[i] = r[i - 1];

                int j = i - 2;

                for (; j >= low && compare(temp, r[j]); j--)

                    r[j + 1] = r[j]; //     

                r[j + 1] = temp; //        

            }

    }

 

    public boolean compare(int paramA, int paramB) {

        if (paramA < paramB) {

            return true;

        } else {

            return false;

        }

    }

 

    /**

     *          

     */

    public void printArr(int[] arr) {

        if (arr != null) {

            for (int temp : arr) {

                System.out.print(temp + "   ");

            }

            System.out.println();

        }

    }

}

d:結果出力
 
　　
 
2.ヒルソート
 
a.アルゴリズムの説明
 
　　
 
ヒルソートは「インクリメンタルソートの縮小」とも呼ばれ、挿入ソートクラスに属するソート方法でもあり、直接挿入ソートに対する改善であるが、時間効率に大きな改善がある.直接挿入ソートの解析から,直接挿入ソートの時間的複雑さはO(n²),しかし、ソートされる要素のシーケンスが秩序化されると、その時間的複雑さはO(n)に向上することができる.これにより、並べ替えられる要素が基本的に秩序化されている場合に、直接並べ替えを挿入する効率が大幅に向上することが分かる.一方,直接挿入ソート法は簡単であるため,n値が小さい方が効率的である.ヒルソートは,この2点から直接挿入ソートを改良したソート方法である.
ヒルソートの基本思想は、まずソートされる要素を複数のサブシーケンスに分け、各サブシーケンスの要素数が相対的に少ないようにし、各サブシーケンスに対してそれぞれ直接挿入ソートを行い、ソートされるシーケンス全体が「基本秩序」になった後、すべての要素に対して直接挿入ソートを行うことである.上記のソート思想に基づいて、ヒルソートのソート過程を示します.
⑴ステップ長シーケンスt 1,t 2,...,tkを選択し、ti>tj(i(2)ステップ長シーケンスの個数kによって、ソート要素シーケンスに対してk回ソートを行う.
(3)各ソートは,対応するステップ長tiに基づいて,並べ替えられるシーケンスをtiサブシーケンスに分割し,各サブシーケンスをそれぞれ直接挿入ソートする.ステップファクタが1の場合、すべての要素は1つのシーケンスとして処理され、その長さはnである.キーワードシーケンス{26,53,67,48,57,13,48,32,60,50}を例に、選択したステップシーケンスが{5,3,1}であると仮定すると、ヒルソートのプロセスは図9−2に示す.ステップ長シーケンス長は3であるため,ソートシーケンスに対して合計3回のソートが必要である.まず、1回目のソートでは、キーワードシーケンスを5つのサブシーケンス{26,13},{53,48},{67,32},{48,60},{57,50}に分けて、それぞれ直接挿入ソートを行い、結果を図に示す.次に,2回目のヒルソートを行い,このステップ長が3の場合,キーワードシーケンスを3つのサブシーケンス{13,48,53,57},{48,50,67},{32,26,60}に分けて直接挿入ソートした結果を図に示す.最後に,シーケンス全体に直接ソートを挿入すると,キーワードが整列したシーケンスが得られ,ヒルソートが終了する.
 
 
 
b.アルゴリズム実現
 
　　　　
 
  

public void shellSort(int[] r, int low, int high, int[] delta) {

        for (int k = 0; k < delta.length; k++)

            shellInsert(r, low, high, delta[k]); //      delta[k]       

    }

 

    private void shellInsert(int[] r, int low, int high, int deltaK) {

        for (int i = low + deltaK; i <= high; i++)

            if (compare(r[i], r[i - deltaK])) { //    ，  r[i]      

                int temp = r[i];

                int j = i - deltaK;

                for (; j >= low && compare(temp, r[j]); j = j - deltaK)

                    r[j + deltaK] = r[j]; //      [j];

                r[j + deltaK] = temp; //        

            }

    }

【効率分析】
スペース効率:1つの補助ユニットのみが使用されます.
時間効率:並べ替えられる要素の個数がnであると仮定すると、順序テーブルにレコードを1つずつ挿入する操作がn−1回行われ、各操作は比較キーと移動レコードに分けられ、比較回数と移動レコードの回数は、並べ替えられるシーケンスのキーコードによる初期列に依存する.直接挿入ソートの時間的複雑度はO(n²)
 
c.使用例
 
　 
　HashInsertSort.java

 

　　

 

package com.test.sort.insertion;

 

public class HashInsertSort {

 

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

 

        System.out.println("        》》》》");

         

        int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };

        int[] delta = {5,3,1};

 

        HashInsertSort sort = new HashInsertSort();

        System.out.println("      ：");

        sort.printArr(arr);

        sort.shellSort(arr, 0, arr.length - 1,delta);

        System.out.println("      ：");

        sort.printArr(arr);

    }

 

    public void shellSort(int[] r, int low, int high, int[] delta) {

        for (int k = 0; k < delta.length; k++)

            shellInsert(r, low, high, delta[k]); //      delta[k]       

    }

 

    private void shellInsert(int[] r, int low, int high, int deltaK) {

        for (int i = low + deltaK; i <= high; i++)

            if (compare(r[i], r[i - deltaK])) { //    ，  r[i]      

                int temp = r[i];

                int j = i - deltaK;

                for (; j >= low && compare(temp, r[j]); j = j - deltaK)

                    r[j + deltaK] = r[j]; //      [j];

                r[j + deltaK] = temp; //        

            }

    }

 

    public boolean compare(int paramA, int paramB) {

        if (paramA < paramB) {

            return true;

        } else {

            return false;

        }

    }

 

    /**

     *          

     */

    public void printArr(int[] arr) {

        if (arr != null) {

            for (int temp : arr) {

                System.out.print(temp + "   ");

            }

            System.out.println();

        }

    }

 

}

　　
 
d.結果出力
 
 
 
3.折り返し挿入ソート
 
a.アルゴリズムの説明
 
　　
 
直接挿入ソートアルゴリズムは簡単で、実現しやすい.並べ替えられる要素の数nが小さい場合、これはより良い並べ替え方法であるが、通常、並べ替えられる要素の数nが大きい場合、直接挿入並べ替え方法を採用するべきではなく、直接挿入並べ替えを改善する必要がある.直接ソートを挿入する基本的な操作は、ソートシーケンスに要素を挿入することであり、挿入位置の決定は、ソートシーケンスの要素をキーワードごとに比較することによって得られる.整列シーケンスで挿入位置を決定する以上、整列シーケンスを絶えず二分して挿入位置を決定することができ、すなわち、挿入位置を検索する方法は、折半検索を用いて実現することができる.
 
b.アルゴリズム実現
 
　　
 
  

    public void binInsertSort(int[] r, int low, int high) {

 

        for (int i = low + 1; i <= high; i++) {

            int temp = r[i]; //        

            int hi = i - 1;

            int lo = low; //       

            while (lo <= hi) { //         

                int mid = (lo + hi) / 2;

                if (compare(temp, r[mid]))

                    hi = mid - 1;

                else

                    lo = mid + 1;

            }

            for (int j = i - 1; j > hi; j--)

                r[j + 1] = r[j]; //     

            r[hi + 1] = temp; //     

        }// for

    }

 
【効率分析】
スペース効率:1つの補助ユニットのみが使用されます.
時間効率:折半挿入ソートは要素の比較回数のみ減少したが、要素の移動回数は減少せず、折半挿入ソートの時間複雑度はO(n²).
 
c.応用例
 
　　 
BinaryInsertSort.java

 

　　

 

 

package com.test.sort.insertion;

 

public class BinaryInsertSort {

 

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        System.out.println("            》》》》");

        int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };

 

        BinaryInsertSort sort = new BinaryInsertSort();

        System.out.println("      ：");

        sort.printArr(arr);

        sort.binInsertSort(arr, 0, arr.length - 1);

        System.out.println("      ：");;

        sort.printArr(arr);

    }

 

    public void binInsertSort(int[] r, int low, int high) {

 

        for (int i = low + 1; i <= high; i++) {

            int temp = r[i]; //        

            int hi = i - 1;

            int lo = low; //       

            while (lo <= hi) { //         

                int mid = (lo + hi) / 2;

                if (compare(temp, r[mid]))

                    hi = mid - 1;

                else

                    lo = mid + 1;

            }

            for (int j = i - 1; j > hi; j--)

                r[j + 1] = r[j]; //     

            r[hi + 1] = temp; //     

        }// for

    }

 

    public boolean compare(int paramA, int paramB) {

        if (paramA < paramB) {

            return true;

        } else {

            return false;

        }

    }

 

    /**

     *          

     */

    public void printArr(int[] arr) {

        if (arr != null) {

            for (int temp : arr) {

                System.out.print(temp + "   ");

            }

            System.out.println();

        }

    }

 

}
JS - Array, For/TIL - 3
JSベース(反応速度試験)