アルゴリズム--ソートアルゴリズムの紹介とまとめ(一)

1、ソートアルゴリズムの種類紹介
ソートアルゴリズムを学習する前に、ソートアルゴリズムの分類を簡単に理解する必要があります.バブルソートアルゴリズムと高速ソートアルゴリズムの基本操作は、両方の要素を交換する値であるため、交換ソートアルゴリズムに属します.ソートとスタックソートアルゴリズムの選択の基本的な操作は、すべての要素から最大です.(または最小)値なので、選択ソートアルゴリズムに属します.挿入ソートとshellソートアルゴリズムの基本操作は、1つの要素を適切な位置に挿入するため、挿入ソートに属します.上記のいくつかの基本ソートアルゴリズムは、コンピュータのメモリを直接ソートします.一部の大きなファイルでは、コンピュータのメモリが限られているため、直接ソートすることはできません.読み込みメモリをソートします.この場合,多重集計ソートアルゴリズムを用いて,ファイルをメモリを読み込むことができるいくつかの小さな部分に分割し,それぞれソートし,複数回の処理を経て大きなファイルのソートを完了することができる.各ソートアルゴリズムにはそれぞれの特徴があり、特定の場合に良好な実行効率を有することが多いため、実際の問題の必要に応じてソートアルゴリズムを合理的に選択する必要がある.
2、アルゴリズム実装経典例(java実装)
2.1、泡立ちソートアルゴリズム
バブルソートアルゴリズムは、すべてのソートアルゴリズムの中で最も簡単で、最も基本的なものです.バブルソートアルゴリズムの構想は交換ソートであり,隣接データの交換によってソートの目的を達成する.
実現構想:バブルソートアルゴリズムは複数回の比較と交換によってソートを実現し、そのソートフローは以下の1、配列中の各データに対して、隣接する2つの要素の大きさを順次比較する.2、前のデータが後のデータより大きい場合は、この2つのデータを交換する(ここではバブルソートが交換ソートに属することを説明している).1ラウンド目の複数回の比較を経て、最大のデータを並べ替えることができる.3、残りのデータを同じ方法で1つずつ比較し、最後に配列中のデータを小さい順に並べ替えることができる.
具体的なコードは以下の通りです.

/** * @author lqf * describe:       * * 2015-4-2 */
public class P4_1_Exchange_BubbleSort {
    static final int SIZE =10;

    /** * @return */
    static int geneNum(){
        int tempNum =(int)(Math.random()*100.0);
        return tempNum;
    }

    /** * @param a */
    static void bubbleSort(int[] a){
        for(int i=1;i<a.length;i++){
            for(int j=0;j<a.length-i;j++){
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j]=a[j+1];
                    a[j+1] = temp;
                }
            }
            System.out.print(" "+i+"      ：");
            for(int k=0;k<a.length;k++){
                System.out.print(a[k]+" ");
            }
            System.out.print("
");
        }
    }
    public static void main(String[] args){
        int[] array = new int[SIZE];

        for(int i=0;i<10;i++){
            array[i]= P4_1_Exchange_BubbleSort.geneNum();
        }

        System.out.print("       ：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.print("
");
        P4_1_Exchange_BubbleSort.bubbleSort(array);

        System.out.print("       ：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }

    }
}

2.2、ソートアルゴリズムの選択
ソートアルゴリズムの選択も比較的簡単なソートアルゴリズムであり,その構想は比較的直観的である.ソートアルゴリズムを選択し、各ステップで最小値を選択して並べ替え、ソートの目的を達成します.
実装構想:選択ソートアルゴリズムは選択と交換によってソートを実現し、そのソートプロセスは以下の通りである:1、まず元の配列から最小の1つのデータを選択し、それを最初の位置にあるデータと交換する.2.次に、残りのn−1(第1の位置に配置された最小のデータを除く)個のデータの中から最小の1個のデータを選択し、第2の位置とのデータ交換を行う.
具体的なコードは以下の通りです.

/** * @author Mr0 * describe:      ，          ，     n-1      。 *              ，            。 * */
public class P4_2_Select_SelectSort {
static final int SIZE =10;

    /** * @return */
    static int geneNum(){
        int tempNum =(int)(Math.random()*100.0);
        return tempNum;
    }

    /** * @param a */
    static void selectSort(int[] a){
        for(int i=1;i<=a.length;i++){
            int index = i-1;
            for(int j=i-1;j<a.length;j++){      //               index，           index    
                if(a[j]<a[index]){
                    index = j;
                }
            }
            int temp=a[i-1];
            a[i-1]=a[index];
            a[index] = temp;

            System.out.print(" "+i+"      ：");
            for(int k=0;k<a.length;k++){
                System.out.print(a[k]+" ");
            }
            System.out.print("
");
        }
    }
    public static void main(String[] args){
        int[] array = new int[SIZE];

        for(int i=0;i<10;i++){
            array[i]= P4_2_Select_SelectSort.geneNum();
        }

        System.out.print("       ：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.print("
");
        P4_2_Select_SelectSort.selectSort(array);

        System.out.print("       ：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }

    }
}

2.3、並べ替えアルゴリズムの挿入
挿入ソートアルゴリズムは、ソートされていないデータを適切な位置に1つずつ挿入することによってソート作業を完了する.ソートアルゴリズムを挿入する構想は比較的簡単で、応用は比較的多い.
実現構想:1、まず配列の前の2つのデータを小さいから大きいまで並べ替える.2.次に、3番目のデータを並べた2つのデータと比較し、3番目のデータを適切な位置に挿入する.3.次に、4番目のデータを、順序付けされた最初の3つのデータのうち4に挿入し、最後のデータを適切な位置に挿入するまで、上記の手順を繰り返します.最後に,元の配列の小さいものから大きいものへのソートが完了した.
具体的なコードは以下の通りです.

/** * @author Mr0 * describe:      ，                ，      。         ， *           ，        。 * */
public class P4_3_Insert_InsertSort {
static final int SIZE =10;

    /** * @return */
    static int geneNum(){
        int tempNum =(int)(Math.random()*100.0);
        return tempNum;
    }

    /** * @param a */
    static void insertSort(int[] a){

        for(int i=1;i<a.length;i++){
            int j=i-1;
            int t=a[i];
            while(j>=0 &&t<a[j] ){
                a[j+1]=a[j];
                j--;
            }
            a[j+1] = t;


            System.out.print(" "+i+"      ：");
            for(int k=0;k<a.length;k++){
                System.out.print(a[k]+" ");
            }
            System.out.print("
");
        }
    }
    public static void main(String[] args){
        int[] array = new int[SIZE];

        for(int i=0;i<10;i++){
            array[i]= P4_3_Insert_InsertSort.geneNum();
        }

        System.out.print("       ：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.print("
");
        P4_3_Insert_InsertSort.insertSort(array);

        System.out.print("       ：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }

    }
}

上で紹介したバブルソートアルゴリズム,選択ソートアルゴリズム,挿入ソートアルゴリズムは,比較的直感的な考え方であるが,ソートの効率は比較的低い.以下では、前の3つのアルゴリズムの改善から得られた、より効率的なソートアルゴリズムをいくつか紹介します.前の3つのアルゴリズムを理解することは、以下に紹介するアルゴリズムを理解するのに役立ちます.