いくつかの一般的なソートアルゴリズムのjava実装

一、いくつかの一般的なソートアルゴリズムの性能比較
ソートアルゴリズム
さいてきじかん
へいきんじかん
さいあくじかん
セカンダリメモリ
あんていせい
コメント
単純選択ソート
O(n^2)
O(n^2)
O(n^2)
O(1)
ふあんてい
n時間が良い
直接挿入ソート
O(n)
O(n^2)
O(n^2)
O(1)
あんてい
ほとんどの既存の順序がよい
バブルソート
O(n)
O(n^2)
O(n^2)
O(1)
あんてい
n時間が良い
ヒルソート
O(n)
O(nlogn)
O(n^s), s∈(1,2)
O(1)
ふあんてい
sは選択されたグループです
クイックソート
O(nlogn)
O(nlogn)
O(n^2)
O(logn)
ふあんてい
n大きい方が良い
ヒープのソート
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
ふあんてい
n大きい方が良い
集計ソート
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
あんてい
n大きい方が良い
注意:安定しています.すべての等しい数がソートされた後も、ソート前の相対的な位置関係を維持できます.
二、一般的なアルゴリズムの実現(java)
1、選択ソート(Selection Sort)
ソートを選択する基本的な考え方は,ソートされた記録シーケンスに対してn−1パスの処理を行い,iパス目の処理はL[i..n]の最小者をL[i]と位置を交換することである.これにより,iパス処理後,前のi個の記録の位置が正しくなった.

public class selectSort {

    public static void selectSort(int[] a){
        int i,j;
        for (i=0;ifor (j=i+1;jif (a[j]int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
public static void main(String args[]){
int[] a={5,4,9,8,7,6,0,1,3,-5};
selectSort(a);
for(int i=0;iout.print(a[i]+" ");
        }
        System.out.println();
    }
}

2、挿入ソート(Insertion Sort)
挿入ソートの基本思想は,i−1パス処理後,L[1..i−1]が自己配列することである.第iパス処理は、L[1..i-1]がまた順序付けされたシーケンスであるように、L[i]のみをL[1..i-1]の適切な位置に挿入する.この目的を達成するには,順序比較の方法を用いることができる.まずL[i]とL[i-1]を比較し、L[i-1]≦L[i]であれば、L[1..i]が順番に並べられ、iパス目の処理は終了する.そうでなければ、L[i]とL[i-1]の位置を交換し、L[i-1]とL[i-2]を比較し続け、ある位置j(1≦j≦i-1)を見つけて、L[j]≦L[j+1]になるまで比較する.図1は、4つの要素を挿入ソートするプロセスを示し、(a)、(b)、(c)の3回の挿入が必要である.

public class insertSort {

    public static void insertSort(int[] a){
        if (a!=null){
            for (int i=1;iint temp=a[i],j=i;
                if (a[j-1]>temp){
                    while(j>=1&&a[j-1]>temp){
                        a[j]=a[j-1];
                        j--;
                    }
                }
                a[j]=temp;
            }
        }
    }

    public static void main(String args[]){
        int[] a={5,4,9,8,7,6,0,1,3,2};
        insertSort(a);
        for(int i=0;iout.print(a[i]+" ");
        }
        System.out.println();
    }
}

3、バブルソート(Bubble Sort)
泡のソート方法は最も簡単なソート方法です.この方法の基本思想は,並べ替えられる元素を縦に並べた「気泡」と見なし,小さい元素は比較的軽く,それによって浮かび上がることである.バブルソートアルゴリズムでは、この「バブル」シーケンスを何回も処理します.一次処理とは,このシーケンスを底から上へチェックし,隣接する2つの要素の順序が正しいかどうかに常に注意することである.2つの隣接する要素の順序が間違っている場合、すなわち「軽い」要素が下にある場合、それらの位置を交換します.明らかに、一度処理すると、「最も軽い」要素が最高位置に浮かび上がった.2回処理すると、「次軽」の要素が次高位置に浮かび上がります.2パス目の処理では、最も高い位置の要素が「最も軽い」要素であるため、チェックする必要はありません.一般に、iパス目の処理では、i番目の高い位置以上の要素を検査する必要はありません.前のi-1パスの処理を経て、それらは正しく順序付けされているからです.

public class bubbleSort {

    public static void bubbleSort(int[] a){
        for (int i=0;ifor (int j=0;j1;j++){
                if (a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
    }
    public static void main(String args[]) {
        int[] a = {5, 4, 9, 8, 7, 6, 0, 1, 3, 2};
        bubbleSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

4、ヒルソート(Shell Sort)
直接挿入ソートアルゴリズムでは、1つの数を挿入するたびに、シーケンスを1つのノードだけ増加させ、次の数を挿入するのに何の役にも立たない.遠く離れているなら(増分と称する)の数は、得数が移動する際に複数の要素を跨ぐことができるようにすると、一度の比較で複数の要素の交換が解消される可能性がある.D.L.shellは1959年に彼の名前で命名されたソートアルゴリズムで実現した.アルゴリズムはまず、ソートする1組の数をある増量dによっていくつかのグループに分け、各グループに記録された下標の差d.各グループのすべての要素をソートする.その後、小さなインクリメンタルで並べ替え、各グループで並べ替えます.インクリメントが1に減少すると、ソートする数全体がグループに分けられ、ソートが完了します.

public class shellSort {

    public static void shellSort(int[] array){
        int len=array.length;
        for(int h=len/2;h>0;h=h/2){//   h
            for (int i=h;iint temp=array[i];
                int j;
                for (j=i-h;j>=0;j-=h){//  h   ，     ，        
                    if (temp==array[j]){
                        array[j+h]=array[h];
                    }else break;
                }
                array[j+h]=temp;
            }
        }
    }
    public static void main(String args[]){
        int[] a={5,4,9,8,7,6,0,1,3,2};
        shellSort(a);
        for(int i=0;iout.print(a[i]+" ");
        }
        System.out.println();
    }
}

5、クイックソート(Quick Sort)
高速ソートはバブルソートの本質的な改善である.その基本思想は,1回のスキャンにより,ソートシーケンスの長さを大幅に減少させることである.バブルソートでは、1回のスキャンで最大値の数が正しい位置に移動することしか確保できませんが、ソートされるシーケンスの長さは1だけ減少する可能性があります.クイックソートは1回スキャンすることで、ある数(それを基準点としましょう)の左の各数がそれより小さく、右の各数がそれより大きいことを確保します.そして、基準点の左右に1つの要素しかないまで、同じ方法で左右の数を処理します.

public class quickSort {

    public static void quickSort(int[] array,int low,int high) {
        if(low < high){
            int privotLoc = partition(array,  low,  high);  //      
            quickSort(array,low,privotLoc -1);          //          
            quickSort(array,privotLoc + 1,high);        //          
        }
    }

    public static int partition(int a[], int low, int high) {
        int privotKey = a[low];                             //    
        while(low < high){                                   //             
            while(low < high  && a[high] >= privotKey)
                --high;  // high         ，   low+1   。             
            swap(a,low,high);
            while(low < high  && a[low] <= privotKey )
                ++low;
            swap(a,low,high);
        }
        return low;
    }

    public static void swap(int[] a, int i,int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public static void main(String args[]){
        int[] a={5,4,9,8,7,6,0,1,3,2};
        quickSort(a,0,a.length-1);
        for(int i=0;iout.print(a[i]+" ");
        }
        System.out.println();
    }
}

6、ヒープソート(Heap Sort)
スタックソートはツリー選択ソートであり,ソート中にA[n]を完全ツリーの順序格納構造と見なし,完全ツリーにおける親ノードと子ノードの間の内在関係を利用して最小の要素を選択する.

/**
 *    
 *
 *                        ，
 *             （   ）        ，
 *                1 ，              ，
 *                 ，              
 */
public class heapSort {
    private static int heapSize;//    

    private static void maxHeapify( int[] array , int index ){
        int left = 2*index;//   
        int right = 2*index+1;//   
        int largest;
        if( left < heapSize && array[ index ] < array[ left ]){
            largest = left;
        }else{
            largest = index;
        }
        if( right < heapSize && array[ right ] > array[ largest ]){
            largest = right;
        }
        if( largest == index ){
            return ;
        } else {
            int temp = array[ index ];
            array[ index ] = array[ largest ];
            array[ largest ] = temp;
            maxHeapify( array, largest );
        }
    }

    /**
     *      。    ，array.length/2+1              ，
     *            ，        ，    maxHeapify  ，          
     * @param array
     */
    private static void buildMaxHeap(int[] array){
        //       ,     array[0]
        int min = array[0];
        for(int i = 1 ; i < array.length ; i++ ){
            if( min > array[i] ){
                min = array[i];
                array[i] = array[0];
                array[0] = min;
            }
        }
        for( int i = array.length / 2 ; i >= 1; i-- ){
            maxHeapify( array , i );
        }
    }

    /**
     *    :
     */
    public static void heapSort( int[] array ){
        buildMaxHeap( array );
        for(int i = array.length - 1 ; i >= 2 ; i--){
            int temp = array[1];
            array[1] = array[i];
            array[i] = temp;
            heapSize--;
            maxHeapify( array , 1 );
        }
    }

    public static void main(String args[]){
        int[] a={5,4,9,8,7,6,0,1,3,2};
        heapSize = a.length;
        heapSort(a);
        for(int i=0;i" ");
        }
        System.out.println();
    }
}

7.集計ソート(Merge Sort)
2つの順序付け(昇順)シーケンスが同じ配列に隣接する位置に格納されている場合は、A[l..m],A[m+1..h]に設定し、それらを1つの順序付け数列にまとめ、A[l..h]に格納してもよい.

public class mergeSort {

    public static void MergeSort(int[] array,int p,int r){
        if (pint q=(p+r)/2;
            MergeSort(array,p,q);
            MergeSort(array,q+1,r);
            Merge(array,p,q,r);
        }
    }
    public static void Merge(int[] array,int p,int q,int r){
        int n1=q-p+1;
        int n2=r-q;
        int[] L=new int[n1];
        int[] R=new int[n2];
        for (int i=0;ifor (int i=0;i1+i];
        }
        int i,j,k=p;
        for (i=0,j=0;iif (L[i]else{
                array[k]=R[j];
                j++;
            }
        }
        if (ifor (j=i;jif (jfor (i=j;ipublic static void main(String args[]) {
        int[] a = {5, 4, 9, 8, 7, 6, 0, 1, 3, 2};
        MergeSort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}