『アルゴリズム』第4版のソート

『アルゴリズム』第4版
一:並べ替えアルゴリズム
並べ替えアルゴリズムは簡単に言えば,時間の複雑さによって2つに分けることができる.時間的複雑さとは、ソートされたデータ規模が指数関数的に増加した場合、ソートアルゴリズムが消費する時間が指数関数的に増加するか、定数的に増加するか、lg的に増加するかを意味します.従って,この2つの時間複雑度はそれぞれO(n平方)とO(nlg(n))の2つである.並べ替えが必要なデータが一定の規模に達すると,この2つの並べ替えアルゴリズムが消費される時間が長くなり,雲泥と判断される.
(一):nの平方レベル
(1)ソートの選択
選択ソートは主に[4,2,7,1,8,9,3]配列の遍歴において[i,n]の最小値を探す.昇順配列を希望する場合.次に最小値をiと交換する.つまり、遍歴のたびに1回だけ交換すればよい.

private void selectSort(int [] arr,int size){
    for(int i=0;iarr[j]){
            //         ，  minIndex。
                minIndex=j;
            }
        }
        //     i      。      。
        swap(arr,i,minIndex);
    }
}

したがって、ソートを選択すると、現在の要素とその後に最小値を選択してソートすることも考えられます.
(2)ソートの交換ソートを挿入する
同じ配列[4,2,7,1,8,9,3]は、昇順配列であれば望ましい.挿入ソートとは、[0,i]でiの適切な位置を探すことです.適切な位置jが見つかった場合、jの位置が0になるまで、iおよびjが交換される.[0,i]は既に秩序化されているため、arr[i]を初めて満たさない場合、ここでは何度も交換する必要があるかもしれない.

private void insertSort(int [] arr,int size){
//   i=1  ，   0                    。
    for(int i=1;i0;j--){
        //            ，       。  (j-1) 0  。    [i,0]           i   。
            if(arr[j]

一般に、2つの要素を1回交換するには3回の操作が必要であり、挿入ソートは内層サイクルを早期に終了することができるが、上記の挿入ソートは複数回の交換を使用する可能性があるため、総時間の消費量において、選択ソートよりも高いことができる.
(2)ソートの付与ソートを挿入する
交換は比較的時間のかかる操作であるため、上記の挿入ソートを最適化するために、値比較を割り当てる方法を採用することができる.[i,0]の配列でiの値を1つの変数に保存し、arr[j-1]と比較し、arr[j-1]より小さい変数であればarr[j]の値をarr[j-1]に割り当て、逆に(j)というインデックスは、所望の位置である.

private void insertSort2(int [] arr,int size){
    //        1    ，    0       。
    for(int i=1;i0;j--){
            if(temp

値を割り当てて比較する挿入ソートでは、要素を交換する必要はありません.ただし、一時変数を格納するために2つの一時的なスペースが追加されます.また、内層サイクルを早期に終了することができる.挿入ソートは,ほぼ整列した配列を配列すると,ほぼO(n)レベルに達する.
(3)ヒルソート.
ヒルソートは、ソートを挿入する延長です.挿入ソートは毎回前の要素と比較され、ヒルソートはまず配列をステップ長で論理的ないくつかの小さな配列に分け、それぞれ挿入ソートを行う.ソート後、ステップ長の値を小さくし続け、再度グループ化し、再度挿入ソートを使用します.最後に、配列全体を1回挿入してソートします.ステップ長シーケンスの選択は,ヒルソートの最悪の状況に直接影響した.例えば[1,2,4,8...]最悪の場合はnの平方です.[1,3,7…((2のn次方)−1)]このようなシーケンスの最悪の場合はnの(1.5次方)である.Sedgewickが提案した[1,5,19,4109...]最悪の場合をn(1.3次方)に低減することができる.

public void shellSort(int [] arr,int size){
    for(int step=size/2;step>0;step/=2){
        for(int i=step;i=0&&arr[j]

(4)集計ソート
集計ソートはO(nlg(n))レベルのアルゴリズムであり,上記のいくつかのソートに対して集計ソートは再帰的に実現される.まず配列を2つに分け、それぞれ1つの要素が残るまで2つに分けます.次に、各小配列を並べ替えます.ソートが完了すると、2つの整列した小さな配列が、1つの整列した大きな配列に結合されます.順番に再帰し、最終的に配列全体のソートを完了します.ソートには、追加の配列のスペースが必要です.

private void merge1(int [] arr,int size){
    merge2(arr,0,size-1);
}

private void merge2(int [] arr,int l,int r){
    if(l>=r){
        return;
    }
    int middle=l/2+r/2;
    merge2(arr,l,middle);
    merge2(arr,middle+1,r);
    merge3(arr,l,middle,r);
}

private void merge3(int [] arr,int l,int m,int r){
    int [] temp = new int[r-l+1];
    for(int i=l;i<=r;i++){
        temp[i-l]=arr[i];
    }
    int i=l;
    int j=m+1;
    for(int k=l;k<=r;k++){
        if(j>r){
            arr[k]=temp[i-l];
            i++;
        }else if(i>m){
            arr[k]=temp[j-l];
            j++;
        }else if(temp[i-l]>temp[j-l]){
            arr[k]=temp[j-l];
            j++;
        }else{
            arr[k]=temp[i-l];
            i++;
        }
    }
}

(5)クイックソート
高速ソートも再帰に基づいて実現されるが,高速ソートと集計の違いは,集計が二分数群のたびに配列をバランスよく二つに分けることができ,配列が最後の層に分かれたときにlg(n)の層数しかないことを保障することである.しかし、選択した要素を中間値としてすばやくソートし、この要素を2分数グループに分け、この要素より大きい値をその値の右に、この要素より小さい値をその要素の左に、秩序配列に遭遇した場合.この二分は配列の階層がnであり,高速並べ替えの時間的複雑さもO(nの二乗)に劣化する.これを避けるには,要素を選択するたびにランダムに選択することで,O(nの二乗)という複雑度が現れる確率をほぼ0に低下させる.しかし,多数の重複要素が現れる配列に遭遇すると,高速ソートをO(nの二乗)に低下させることになるが,この場合,配列が平分化されたときにlg(n)の階層を維持できることを三路高速ソートにより保障する必要がある.

public void quickSort(int [] arr,int size){
    quickSort1(arr,0,size-1);
}

public void quickSort1(int [] arr,int l,int r){
    if(l>=r){
        return;
    }
    int p = partition(arr,l,r);
    quickSort1(arr,l,p-1);
    quickSort1(arr,p+1,r);
}


public int partition(int [] arr,int l,int r){
    //       [l,r]          v  。           ，          n   。
    int v=arr[l];
    int j=l;
    for(int k=l+1;k<=r;k++){
        if(arr[k]

(6)三路快速列

private static void quickThree1(int arr [],int size){
        quickThree2(arr,0,size-1);
    }

    private static void quickThree2(int [] arr,int l,int r){
        if(l>=r){
            return;
        }
        int v=arr[l];
        int lt=l;
        int gt=r+1;
        int i=l+1;
        while (iv){
                swap(arr,i,gt-1);
                gt--;
            }else{
                i++;
            }
        }
        swap(arr,l,lt);
        quickThree2(arr,l,lt-1);
        quickThree2(arr,gt,r);
    }

二:スタック
スタックは優先キューとも呼ばれますが、キューではありません.スタックを実現するには、2つの条件を定義する必要があります.1.任意のノードの優先度は、サブノードの優先度より小さくしてはならない.2、完全な二叉木です.この木にn層がある場合、(n−1)層は満たされなければならず、n層の要素は左から右へ順番に並べられる.スタックの主な操作は、1、新しい要素を挿入し、2、最小要素を削除し、これが最小スタックであれば.新しい要素を挿入する場合、新しいノードはn番目のレイヤにあり、その要素は親要素と比較され、親要素より優先度が高い場合は、両方の位置が交換されます.ルート要素を削除する場合は、n番目のレイヤの最後の要素をルート要素の位置に配置し、ルート要素のサブ要素と比較し、サブノードの要素より大きい場合は、最終的に交換できないまで交換する必要があります.