アルゴリズム学習---高速ソート

クイックソート
初日の挑戦
これからは毎日1つのアルゴリズムに、いくつかのアルゴリズムの問題を加えて向上したいと思っています.今の段階では「ああ!アルゴリズム!」を勉強します.ここは作者に感謝します!こんな面白い本を書こう!
クイックソート!
主な考え方

は配列を取得し、最初のステップは基準値を選択し、一般的に配列の最初の要素を基準値として選択し、基準値に基づいて比較し、第1の部分を右から左に2つに分けて比較し、第2の部分を左から右に比較する.

右から左へ比較すると、基準値より小さい数字(つまり左に置くべき数字)が出てきて、左から右へ比較すると、基準値より大きい数字(つまり数字の右に置くべき)が出てくる

が出てくる.

そして2つの数字を交換

は、2つの位置が出会うまで比較を続け、その内容を基準値と入れ替えて終了する.

その後、配列は2つの部分に分けられ、第1の部分は左であり、第2の部分は右であり、左の右に従って並べ替えられる.

具体的な方法で参考になる資料がたくさんあります!!
主な思考
思考1、どうして右から左へ先に探しますか?
まず左から右に探すのであれば、基準値が1番目で、左から右に探すのであれば、基準値より大きいものを探し、基準値より大きいものが1つしかないと、基準値より大きいところで交差し、この値を基準値と入れ替えて、このような大きな値が1位に走ってしまうので、これで並べ替えを行うと問題が発生します.
思考2,クイックソートの目的は小さいものから大きいものまでソートすることであり,クイックソートを希望する順序でジャンプしたい場合は,大きいものから小さいものまでソートするにはどうすればよいかを考える.逆ソートを参照
逆ソート
くだらないことはあまりコードを言わないでください.

public static void antitoneSort(int[] sortArray,int start,int end){

    if(start > end){
        return;
    }

    int standard = sortArray[start];
    int left = start;
    int right = end;

    while(left != right){

        //      ,                     
        //           ,           
        //           ,           

        while(left < right){
            if(standard < sortArray[right]){
                break;
            }
            right--;
        }

        while (left < right){
            if(standard > sortArray[left]){
                break;
            }
            left++;
        }



        if(left < right){
            int temp = sortArray[right];
            sortArray[right] = sortArray[left];
            sortArray[left] = temp;
        }
        System.out.println(Arrays.toString(sortArray));

    }

    //      
    sortArray[start] = sortArray[left];
    sortArray[left] = standard;

    //       
    antitoneSort(sortArray,start,left -1);
    antitoneSort(sortArray,left+1 , end);
    return;

}

クイックソートの時間的複雑さについて

             ，           。      O(nlogn)

                 ，                      O(n^2)

出会った問題と悟り
正直に言って初めてこれを书いた时、本当に半日本を読んで、数ヶ月前にも勉强したことがありますが、その时は确かに研究していませんでした.本に基づいてコードを写して、それから自分ができるふりをして、最近多くのことで法学の使い方の重要性が分かったので、思い切って本を取って勉强し直しました.怠け者に別れを告げよう.
今回の学習アルゴリズムでは,クイックソートが最初は基準値の選択であることを知らなかったが,最初は任意の配列のデータを基準値と見なすことができると考え,基準値を照会する方法を書いた.それからまたとても楽しくて、结果は発见して、根本的に本の上の実现に従うことができなくて、とても长い时间书いても书いていないで、それからよく本を読んで、第1个が基准値になることを発见します!ここは軽く喷きます!私のおかず鸟!)後に本で理解して書いてみると、自分が独立して完全に書けなかったのは基準値の理解の問題だった.
理解して、また本の上の1つに対して、右から左へ引きつけなければならなくて、私は天秤座で、各种の好奇心、だから研究してどうして右から左へ先に始めます.つまり思考1の内容です.そして何度も間違ったことを試した場合(偶然、自分のデータが大きいものから小さいものまで並んでいることに気づいた)、後で考えて書いてみましたが、クイックソートは大きいものから小さいものまで、やはりいろいろな間違いで、主に右から左へ左へ、大きいものから小さいもの、小さいものから大きいもの、コード注釈を見た人は理解できるはずです.
これはただの始まりです!これからもブログを书いて分かち合うことを望んで、私の成长の过程を记录します!加えて自分に考えを残して!ハハ~初日おめでとう!