Javaを使用してソートアルゴリズムを実装する方法

不安定なソート

選択ソート:
1回目の比較で得られた最小のレコードを最初のレコードの位置と交換し、1回目のレコードを除いたレコードに対して2回目の比較を行い、その結果最小のレコードが 2 番目のレコードと交換されます
時間計算量: O(n^2)
空間計算量: O(1)

    public static void selectSort(int[] arr){        
    if (arr == null || arr.length == 0)            
    return;        
    int len = arr.length;        
    for (int i = 0; i < len; i++) {            
        int min = arr[i];            
        int index = i;            
        for (int j = i+1; j < len; j++) {                
        if (arr[j] < min) {                    
            min = arr[j];
          index = j;
          }
       }
       arr[index] = arr[i];
       arr[i] = min;
     }
    }

クイック ソート:
指定されたレコードのセットについて、各ソートの後、次のことがわかりますシーケンスは 2 つの部分に分割され、前半部分のすべてのレコードが後半部分のすべてのレコードよりも小さくなり、前後の 2 つの部分のレコードが迅速にソートされます
時間計算量: O(nlogn) 最悪ケース: O(n^2 )
空間複雑度: O(nlogn)

    public int Partition(int[] a,int start,int end){        int std = a[start];
        while (start < end){
             while(start < end && a[end] >= std)                 
             end--;
             a[start] = a[end];
             while(start < end && a[start] <= std)                 
             start++;
             a[end] = a[start];
        }
        a[start] = std;
        return start;
    }
    public void quickSort(int[] a,int start,int end){        
            if(start >= end){
            return;
        }
        int index = Partition(a,start,end);
        quickSort(a,start,index-1);
        quickSort(a,index+1,end);
    }

ヒープソート: 完全なバイナリツリー
バイナリツリーを大きなトップヒープに調整し、ヒープの最後の要素をヒープのトップ要素と交換しますヒープ (つまり、バイナリ ツリーのルート ノード)、ヒープの最後の要素が最大のレコードとなり、最初の n-1 個の要素が最大の最上位ヒープに合わせて調整され、次にヒープの最上位要素が次のようになります。現在のヒープの最後の要素と交換して 2 番目に大きいレコードを取得します。調整された要素が 1 つだけになるまで処理を繰り返します。この時点で、その要素が最小のレコードになります。
時間計算量: O(nlogn)
空間計算量: O(1)

   public void HeapSort(int[] a){        
            for (int i = a.length/2 - 1; i >= 0 ; i--) {
            HeapAdjust(a,i,a.length-1);
        }        
        for (int i = a.length - 1; i >= 0; i--) {
            swap(a,0,i);
            HeapAdjust(a,0,i-1);
        }
    }    
    private void swap(int[] a, int i, int j) {        
            int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }    
    public void HeapAdjust(int[] arr,int s,int len){        
            int tmp = arr[s];        
            for (int i = s * 2 + 1; i < len ; i = i * 2 + 1) {            
                    if (i < len && arr[i] < arr[i+1]){
                i++;
            }            
            if (tmp > arr[i])                
            break;
            arr[s] = arr[i];
            s = i; //s记录被替换的子结点的索引
        }
        arr[s] = tmp;
    }

安定したソート

直接挿入ソート:
最初のレコードはそれ自身の順序付けされたシーケンスとみなすことができ、残りのレコードは順序付けされていないシーケンスと呼ばれます。 次に、2 番目のレコードから開始して、最後のレコードが順序付けされたシーケンスに挿入されるまで、レコードのサイズに応じた順序で、現在処理されているレコードを前の順序付けされたシーケンスに挿入します
時間計算量: O(n^2)
空間計算量: O(1)

    public static void insertSort(int[] arr){        
            if (arr == null || arr.length == 0)            
            return;        
            int len = arr.length;        
            for (int i = 1; i < len; i++) {            
            int curr = arr[i];            
            int j = i;            
            if (arr[j-1] > curr){                
                while (j > 0 && arr[j-1]> curr){
                arr[j] = arr[j-1];
                j--;
                }
            }
          arr[j] = curr;
        }
    }

バブルソート:
最初のレコードから開始して、2 つの隣接するレコードが順番に比較され、前のレコードが次のレコードよりも大きい場合、位置が入れ替わり、n 個のレコードのうち最大のレコードが配置されます。 n 番目のレコードのビットを抽出し、前の n-1 レコードに対して 2 回目の比較を実行し、比較するレコードが 1 つだけ残るまでこのプロセスを繰り返します
時間計算量: O(n^2)
空間複雑度: O(1)

    public void bubbleSort(int[] arr){        
            boolean flag = true;        
            for (int i = 0; i < arr.length && flag; i++) {
            flag = false;            
            for (int j = 0; j < arr.length - i - 1; j++) {                
                    if (arr[j] > arr[j+1]){
                flag = true;
                swap(arr,j,j+1);
                }
            }
        }
    }    
    private void swap(int[] arr, int j, int i) {        
            int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

マージソート: 再帰: 再帰、ユニオン: 別々のデータを秩序正しくマージします
長さ 1 の 2 つの隣接するサブシーケンスをすべてマージして、長さ 2 または 1 の n/2 個の順序付きサブシーケンスを取得し、次に 2 つをマージし、順序付きシーケンスが得られるまでこのプロセスを繰り返します
時間計算量: O(nlogn)
空間の複雑さ: O(n)

   public static void mergeSort(int[] arr,int begin,int end){        
              int mid = (begin+end)/2;        
              if (begin < end){
            mergeSort(arr,begin,mid);
            mergeSort(arr,mid+1,end);
            Merge(arr,begin,end,mid);
        }
    }    
    public static void Merge(int[] arr,int begin,int end,int mid){        
            int[] temp = new int[end-begin+1];        
            int i = begin;        
            int j = mid+1;        
            int k=0;        
            while (i <= mid && j <= end){            
            if (arr[i] < arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }        
        while (i <= mid){
            temp[k++] = arr[i++];
        }        
        while (j <= end){
            temp[k++] = arr[j++];
        }        
        for (int m = 0;m < temp.length;m++){
            arr[m+begin] = temp[m];
        }
    }

以上がJavaを使用してソートアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。