一般的なソートアルゴリズムの概要

概要

コンピュータサイエンスと数学において、ソートアルゴリズムとは、一連のデータを特定の順序で並べるアルゴリズムです。この記事では、バブル ソート、選択ソート、挿入ソート、クイック ソート、マージ ソートなど、よく使用されるソート アルゴリズムをいくつかまとめ、それぞれ Java コードを使用して実装し、図を使用して実装の原理を簡単に紹介します。

アルゴリズムの原理と実装

1. バブルソート

• 概略図

• 理解する

これは、ソートするリストを繰り返し反復処理し、隣接する項目の各ペアを比較して、順序が間違っている場合はそれらを交換することによって機能します。

• Javaコード

パブリッククラスBubbleSort { 
 
    //要素をソートするロジック
公共 静的void bubble_srt( int配列[]) {
 int n = 配列の長さ;
整数k;
 ( int m = n; m >= 0; m --) {  
 ( int i = 0; i < n - 1; i++) {
                k = i + 1;
                配列[i] > 配列[k]の場合{
                    swapNumbers(i, k, 配列);
                }
            }
            printNumbers(配列);
        }
    } 
 
    プライベート静的void swapNumbers( int i, int j, int [] 配列) { 
 
整数 温度;
 temp = 配列[i];
        配列[i] = 配列[j];
        配列[j] = temp ;
    } 
 
    プライベート静的void printNumbers( int [] input) { 
 
 ( int i = 0; i < input.length; i++) {
            システム.out.print (input[i] + ", " );
        }
        System.out.println ( "\n" ) ;
    } 
 
公共 静的void main(String[] args) {
 int [] 入力 = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
        bubble_srt(入力);
    }
 }

2. 選択ソート

• 概略図

• 理解する

内側のループは次に小さい (または大きい) 値を見つけ、外側のループはその値を適切な場所に配置します。

• Javaコード

パブリッククラスSelectionSort { 
 
公共 静的  int [] doSelectionSort( int [] arr){ 
 
 ( int i = 0; i < arr.length - 1; i++)の場合
        {
整数 インデックス= i;
 ( int j = i + 1; j < arr.length; j++)の場合
                (arr[j] < arr[インデックス])の場合
インデックス= j; 
 
 int小さい数値 = arr[インデックス];
            arr[インデックス] = arr[i];
            arr[i] = 小さい数値;
        }
 arrを返します。
    } 
 
公共 静的void main(文字列a[]){ 
 
 int [] arr1 = {10,34,2,56,7,67,88,42};
 int [] arr2 = doSelectionSort(arr1);
 ( int i : arr2){
            システム出力プリント(i )
            System.out.print ( ", " ) ;
        }
    }
 }

バブルソートと選択ソートの違い

1. バブルソートは隣接する位置にある 2 つの数値を比較しますが、選択ソートは最大値または最小値を見つけるために数値を比較します。

2. バブルソートでは比較の各ラウンドの後に位置が間違っている場合は位置を変更する必要がありますが、選択ソートでは比較の各ラウンドで位置を 1 回だけ変更する必要があります。

3. バブルソートは数字で位置を見つけるソートで、選択ソートは指定された位置の数字を見つけるソートです。

3. 挿入ソート

• 概略図

• 理解する

各ステップでは、すべての要素が挿入されるまで、ソートするレコードが以前にソートされた順序付きシーケンスに挿入されます。

• Javaコード

パブリッククラス挿入ソート{ 
 
公共 静的void main(文字列a[]){ 
 
整数[] arr1 = {10,34,2,56,7,67,88,42}; 
 
 int [] arr2 = doInsertionSort(arr1); 
 
 ( int i : arr2){ 
 
システム出力プリント(i ) 
 
 System.out.print ( ", " ) ; 
 
 } 
 
 } 
 
公共 静的  int [] doInsertionSort( int [] 入力){ 
 
整数 温度; 
 
 ( int i = 1; i < input.length; i++) { 
 
 ( int j = i ; j > 0 ; j --) {   
 
入力[j] < 入力[j-1])の場合{ 
 
 temp = 入力[j]; 
 
入力[j] = 入力[j-1]; 
 
入力[j-1] = temp ; 
 
 } 
 
 } 
 
 } 
 
入力を返します。 
 
 } 
 
 }

4. クイックソート

• 概略図

• 理解する

元の問題を、規模は小さいが構造は元の問題に似ているいくつかのサブ問題に分解し、これらのサブ問題を再帰的に解決してから、これらのサブ問題の解決策を元の問題の解決策に組み合わせます。

パブリッククラスQuickSort { 
 
    プライベートint配列[];
    プライベートint長さ; 
 
パブリックvoidソート( int []inputArr){ 
 
        （inputArr == null || inputArr.length == 0）の場合{
戻る;
        }
        this.array = 入力Arr;
        長さ = inputArr.length;
        クイックソート(0, 長さ - 1);
    } 
 
    プライベート void クイックソート( int下位インデックス、 int上位インデックス) { 
 
 int i = 下位インデックス;
 j = 上位インデックス;
        // ピボット番号を計算します。ピボットを中間のインデックス番号として取得します。
 intピボット = 配列[lowerIndex+(higherIndex-lowerIndex)/2];
        // 2つの配列に分割する
        i <= j の場合
            /**
             *各反復で、  左側は
             *はピボット値よりも大きく、また、数値を特定します
             *から ピボット値より小さい右側。検索が終了すると
             *が完了したら、両方の数値を交換します。
             */
            配列[i] < ピボット) {
                私は++;
            }
            while (配列[j] > ピボット) {
                j --;  
            }
            もし (i <= j) {
                交換番号(i, j);
                //動く 索引 に 両側の次の位置
                私は++;
                j --;  
            }
        }
        // quickSort() メソッドを再帰的に呼び出す
        （下限インデックス < j）の場合
            クイックソート(下位インデックス、j);
        (i < より高いインデックス)
            クイックソート(i, 上位インデックス);
    } 
 
    プライベートvoid exchangeNumbers( int i, int j) {
整数  temp = 配列[i];
        配列[i] = 配列[j];
        配列[j] = temp ;
    } 
 
公共 静的void main(文字列a[]){ 
 
        MyQuickSort ソーター = 新しい MyQuickSort();
 int [] 入力 = {24,2,45,20,56,75,2,56,99,53,12};
        ソート器.sort(入力);
 ( int i:入力) {
            システム出力プリント(i )
            システム出力を印刷します( " " ) ;
        }
    }
 }

5. マージソート

• 概略図

• 理解する

ソートするシーケンスを長さ 1 の複数のサブシーケンスに分割し、これらのシーケンスを 2 つずつ結合します。長さ 2 の順序付けられたシーケンスをいくつか取得し、これらのシーケンスを 2 つずつ結合します。長さ 4 の順序付けられたシーケンスをいくつか取得し、これらのシーケンスを 2 つずつ結合します。これらが 1 つのシーケンスに直接結合されるまで、これを繰り返します。

• Javaコード

パブリッククラス MergeSort { 
 
    プライベートint []配列;
    プライベートint [] tempMergArr;
    プライベートint長さ; 
 
公共 静的void main(文字列a[]){ 
 
 int [] 入力引数 = {45,23,11,89,77,98,4,28,65,43};
        MyMergeSort mms = 新しい MyMergeSort();
        mms.sort(入力配列);
 ( int i:inputArr )の場合{
            システム出力プリント(i )
            システム出力を印刷します( " " ) ;
        }
    } 
 
パブリックvoidソート( int inputArr[]) {
        this.array = 入力Arr;
        入力Arrの長さは、次の式で計算されます。
        this.tempMergArr = 新しいint [長さ];
        マージソートを実行します(0, 長さ - 1);
    } 
 
    プライベートvoid doMergeSort( int下位インデックス、 int上位インデックス) { 
 
        （下限インデックス < 上限インデックス）の場合 {
 int中間 = 下位インデックス + (上位インデックス - 下位インデックス) / 2;
            // 以下の手順では配列の左側をソートします
            マージソートを実行します(下位インデックス、中間);
            // 以下の手順では配列の右側をソートします
            doMergeSort(中間 + 1、上位インデックス);
            // 両側をマージします
            mergeParts(下位インデックス、中間インデックス、上位インデックス);
        }
    } 
 
    プライベート void mergeParts( int下位インデックス、 int中間、 int上位インデックス) { 
 
 ( int i = 下位インデックス; i <= 上位インデックス; i++) {
            tempMergArr[i] = 配列[i];
        }
 int i = 下位インデックス;
 int j = 中央 + 1;
 int k = 下位インデックス;
        (i <= 中間 && j <= 上位インデックス) {
            tempMergArr[i] <= tempMergArr[j] の場合 {
                配列[k] = tempMergArr[i];
                私は++;
            }それ以外{
                配列[k] = tempMergArr[j];
                j++;
            }
            関数
        }
        (i <= 中間) {
            配列[k] = tempMergArr[i];
            関数
            私は++;
        }
    }
 }

一般的なソートアルゴリズムの複雑さ