十大ソートアルゴリズムjava

9577 ワード

javaデータ構造とアルゴリズムソートアルゴリズムデータ構造 java アルゴリズムクイックソート

1.バブルソート(BubbleSort)
バブルソートアルゴリズムの原理は次のとおりです.

隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.

は、各ペアの隣接要素について、最初のペアから最後のペアまで同じ作業を行う.この点では、最後の要素が最大の数になるはずです.

は、最後のステップを除いて、すべての要素について以上のステップを繰り返す.

は、

を比較する必要がないまで、より少ない要素に対して上記のステップを繰り返し続ける.

package sortArithmetic;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args){
        int[] arr=new int[15];
        for(int i=0;iarr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }
}

2.ソートの選択(SelectionsSort)
選択ソート(Selection sort)は、単純で直感的なソートアルゴリズムです.ソート対象のデータ要素から最小(または最大)の要素を最初に選択し、シーケンスの開始位置に格納し、残りの未ソート要素から最小(または最大)の要素を見つけます.(大)要素を並べ替えたシーケンスの最後に配置します.これを使用して、並べ替え対象のすべてのデータ要素の個数がゼロになるまで並べ替えます.並べ替えを選択するのは不安定な並べ替え方法です.

package sortArithmetic;

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args){
        int[] arr=new int[15];
        for(int i=0;iarr[j]){
                    min=arr[j];
                    index=j;
                }
            }
            if(index!=i){
                int temp=arr[index];
                arr[index]=arr[i];
                arr[i]=temp;
            }
        }
    }
}

3.ソートの挿入(InsertSort)
挿入ソートは、一般に直接挿入ソートとも呼ばれます.少量の要素のソートでは、有効なアルゴリズムです.ソートを挿入することは最も簡単なソート方法であり、その基本思想は、ソートされたソートテーブルにレコードを挿入し、新しいレコード数が1増加したソートテーブルを挿入することである.その実装プロセスでは、2層ループが使用され、外側ループは最初の要素を除くすべての要素に対して、内側ループは現在の要素の前の整列テーブルに対して挿入される位置を検索し、移動します.

package sortArithmetic;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args){
        int[] arr=new int[15];
        for(int i=0;iarr[i]){
                int insertVal=arr[i];
                int insertIndex=i-1;
                while(insertIndex>=0&&insertVal

4.ヒルソート(ShellSort)
ヒルソート(Shell's Sort)は、挿入ソートの一種であり、「縮小増分ソート」(Diminishing Increment Sort)とも呼ばれ、直接挿入ソートアルゴリズムのより効率的な改良バージョンである.ヒルソートは非安定ソートアルゴリズムである.この方法はD.L.Shellが1959年に提案したことから名付けられた.
ヒルソートは、レコードを下付きの一定の増分でグループ化し、各グループに対して直接挿入ソートアルゴリズムを使用してソートする.増分が減少するにつれて、各グループに含まれるキーワードはますます多くなり、増分が1に減少すると、ファイル全体がグループに分けられ、アルゴリズムは終了する.

package sortAlgorithm;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args){
        int[] arr=new int[20];
        for(int i=0;i0;gap/=2){
            for(int i=gap;iarr[i]){
                    int insertVal=arr[i];
                    int insertIndex=i-gap;
                    while(insertIndex>=0&&arr[insertIndex]>insertVal){
                        arr[i]=arr[i-gap];
                        insertIndex-=gap;
                    }
                    arr[insertIndex+gap]=insertVal;
                }
            }
        }
    }
}

5.クイックソート(QuickSort)
基本的な考え方は、ソートするデータを1回のソートで独立した2つの部分に分割し、その一部のすべてのデータが他の部分のすべてのデータよりも小さくなった後、この方法で2つの部分のデータをそれぞれ迅速にソートし、ソートプロセス全体を再帰的に行うことで、データ全体が秩序化されたシーケンスになることです.

package sortAlgorithm;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args){
        int[] arr={10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left>=right)return;
        int i=left;
        int j=right;
        int base=arr[i];
        while(i=base)j--;
            while(i=j)break;
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
        arr[left]=arr[i];
        arr[i]=base;
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}

6.ヒープソート(HeapSort)
スタックソートの基本的な考え方は、ソートされるシーケンスを大きなスタックに構築することです.この場合、シーケンス全体の最大値は、スタックのルートノードです.末尾要素と交換し、末尾が最大値になります.次に、残りのn−1要素をスタックに再構築し、n要素の二次小値を得る.このように繰り返し実行すると、秩序あるシーケンスが得られます.

package sortAlgorithm;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {
    public static void main(String[] args){
        Random random=new Random();
        int[] arr=new int[20];
        for(int i=0;i=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        for(int i=arr.length-1;i>0;i--){
            int temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,i);
        }
    }
    private static void adjustHeap(int[] arr, int parent, int length) {
        int temp = arr[parent];
        int lChild = 2*parent+1;
        while(lChildarr[lChild]) lChild++;
            if(temp>=arr[lChild]) break;
            arr[parent]=arr[lChild];
            parent=lChild;
            lChild=2*parent+1;
        }
        arr[parent]=temp;
    }
}

7.バケツソート(BucketSort)
バケツソート(Bucket sort)やいわゆる箱ソートは、配列を限られた数のバケツに分けるソートアルゴリズムです.バケツごとに個別にソートします.(別のソートアルゴリズムを使用するか、再帰的にバケツソートを使用してソートを継続する可能性がある)、最後に各バケツの記録列を順番に並べ替えてソートシーケンスを記憶する.バケツソートはハトの巣ソートの帰納結果である.ソートする配列内の数値が均一に割り当てられている場合、バケツソートは線形時間(O(n))を使用する.しかし,バケツソートは比較ソートではなく,O(n log n)下限の影響を受けなかった.

package sortAlgorithm;

import java.util.*;

public class BucketSort {
    public static void main(String[] args){
        Random random=new Random();
        int[] arr=new int[20];
        for(int i=0;i> bucketArr=new ArrayList<>();
        for(int i=0;i());
        }
        for(int i=0;i

8.集計ソート(MergeSort)
集計ソート(Merge Sort)は、集計操作において確立された有効で安定したソートアルゴリズムであり、このアルゴリズムは分治法を採用している.(Divide and Conquer)の非常に典型的な応用.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの秩序化テーブルを1つの秩序化テーブルに結合すると、2パス集計と呼ばれる.

package sortAlgorithm;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {
    public static void main(String[] args){
        Random random=new Random();
        int[] arr=new int[10];
        for(int i=0;i

9.カウントソート(CountingSort)
カウントソートの基本思想は、与えられた入力シーケンスの各要素xに対して、シーケンスの値がxより小さい要素の個数を決定します(ここでは、各要素の大きさを比較するのではなく、要素値のカウントとカウント値の加算によって決定される).この情報があれば、xを最終的な出力シーケンスの正しい位置に直接格納することができる.例えば、入力シーケンスの中で17要素の値がxの値より小さい場合、xは出力シーケンスの18番目の位置に直接格納することができる.もちろん、例えば、複数の要素が同じ値を有する場合、出力シーケンスの同じ位置にこれらの要素を置くことはできません.したがって、上記のスキームは適切に変更されます.

package sortAlgorithm;

import java.util.Arrays;
import java.util.Random;

public class CountingSort {
    public static void main(String[] args){
        Random random=new Random();
        int[] arr=new int[10];
        for(int i=0;i

10.基数ソート(RadixSort)
これは、比較対象のすべての値(正の整数)を同じ数桁の長さに統一し、数桁の短い数の前にゼロを補います.その後、最下位から順に並べ替えを行います.これにより、最下位から最上位まで並べ替えが完了すると、数列が秩序あるシーケンスになります.

package sortAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class RadixSort {
    public static void main(String[] args){
        Random random=new Random();
        int[] arr=new int[10];
        for(int i=0;i> temp=new ArrayList<>();
        int max=Integer.MIN_VALUE;
        for(int i=0;i());
        }
        for(int exp=1;exp<=radix;exp++){

            //  
            for(int i=0;i

Djangoのmodelsセクション

Python+Flask+Docker使ってブラウザでサイト見れるようにする