並べ替え-交換並べ替え[1-バブル並べ替え]+簡単な選択並べ替え.
4495 ワード
私は特に「バカ」な文章が好きです.
これは2つのアルゴリズム,泡立ち,簡単な選択並べ替えを含むため,少し長い.別々に見てもいいです.それぞれ20分で十分です.足りないなら私を探してください.
この泡のソートについては、これは古典的なアルゴリズムで、もしあなたが聞いたことがなければ、あなたが極品プログラマーだと信じています.
アルゴリズムの原理を知っているかもしれませんが、彼をよく説明することができますか?やってみましょう.
バブルアルゴリズム、例えば:
ソートするデータは{6,3,7,9,2}です.
バブルソートは簡単に言えば、最大の値を徐々に選択し、最後ろに置いて、最初からsize-1の要素の中で最大を見つけて、最後から2番目に置いて、このようにします.
バブルソートは数回に分けて行われますが、まず1回目からどのような動作をするかを見てみましょう.
最初はこうします.
{6,3,7,9,2},6と3を比較し,6>3が成立すると交換する.
{3,6,7,9,2},6と7を比較し,6>7が成立しなければ交換しない.
{3,6,7,9,2},7と9を比較し,7>9が成立しなければ交換しない.
{3,6,7,9,2},9と2を比較し,9>2が成立すると交換する.
{3, 6, 7, 2, 9}. 5つの元素の配列について,4回の比較を行った後,1回の泡立ちが完了した.
次に2回目はどうしますか?9は1回目の中で一番大きく選ばれたので、もう最後まで置いておきました.
では、2回目は実は9を比較する必要はありません.2回目の関心の要素は{3,6,7,2}です.
2回目はこうします
{3,6,7,2},3と6を比較し,3>6が成立しなければ交換しない.
{3,6,7,2},6と7を比較し,6>7が成立しなければ交換しない.
{3,6,7,2},7と2を比較し,7>2が成立すると交換する.
{3, 6, 2, 7}. 4つの元素の配列について,3回の比較を行った後,2回目の泡立ちが完了し,この結果は{3,6,2,7,9}であった.
3回目に関心を持つデータは{3,6,2}であり、具体的な過程は詳しくは言わないが、3回目のソートの結果は{3,2,6}である.合計結果:{3,2,6,7,9}
4回目に関心を持つデータは{3,2}であり,4回目のソートの結果は{2,3}であった.
5回目に気になるデータは{2}ですが、あれ?1つの要素だけがどのようにソートされますか?はい、最初のセクションでソートを直接挿入したときに言いました.
1つの要素のシーケンスだけが秩序化されているので、5回目は無視できます.
5つの要素の配列について,並べ替えに4回,普及後,n個の要素の配列について,並べ替えにn−1回が必要であるという結論も得られた.
複雑度:
時間複雑度:O(n^2)
---------------------
簡単な選択のソートもここに書きたいです.私はよくこの2つのアルゴリズムを混同しているので、ここに書いたほうがいいです.
単純選択ソート:
バブルソートでは、各要素が隣接する要素と比較され、次の要素が現在より大きい場合は交換され、1回の完了後、最大の数字を最後に置くことができます.
単純にソートを選択するのは、無秩序配列の中で最大の要素を最初に見つけて、無秩序配列の最後の要素と交換することです.ここで明らかな違いは次のとおりです.
単純選択ソートでは、1回あたり最大1回の交換が行われます.
たとえば、ソートするデータは{6,3,7,9,2}です.
最初にこうしました
このデータの中で最大の要素を見つけて、私たちは彼が9であることを発見して、それでは彼は最後の要素(以下4と表記して、数値は2)と交換して、交換した後に得ます:{6,3,7,2,9}
2回目:最大の9が末尾に置かれているため,無秩序な配列は{6,3,7,2}である.
このデータの中で最大の要素を見つけて、私たちは彼が7であることを発見して、それでは彼は最後の要素(以下3と表記して、数値は2)と交換して、交換した後に得ます:{6,3,2,7}
3回目:無秩序配列が{6,3,2},最大要素が6であると,最後の要素(以下2,数値2)と交換し,{2,3,6}を得る.
4番目:無秩序配列は{2,3}ですね.これはもう秩序があるのに,どうしてまだ並べ替えているのか.はい、これは特殊な状況です.もし私たちが最初の配列が{6,2,7,9,3}であれば、このステップに進んだとき、無秩序な配列は{3,2}なので、このステップは必要ですが、このステップの最大の要素は3で、最後の要素も彼自身なので、交換する必要はありません.
5回目は、1つの要素しかありません.ソートする必要はありません.
泡神に似ているのではないでしょうか.あなたはnoと言うかもしれませんが、うん、どうせ私は間違っています.
実はもう一つ、バブルソートの重点は最大値の下付きスケールを見つけることです.私たちが最終的に交換するときは、最大値の下付きスケールが指す数値と最後の要素の数値を交換するからです.
では、最大値の下付き文字をどうやって探しますか?
考え方はこうです.
最大値の下付き記号を見つけるために比較する必要があります.
このサイクルでは、比較します.
最初の要素とすべての要素の値は、
他の要素がこの要素より大きい場合は、下にマークします.
さらにこの大きな要素を持って残りのものと比べて、一周したら最大のものを見つけました.
やはり例がはっきりしています.
{6,3,7,9,2}については,まず最大値の下付きを0と仮定した(これは明らかに誤りであるが,これは我々の始まりである).
この比較は1から始まります.
下付き0の値は6、下付き1の値は3.6<3ですか.いいえ、次の要素を比較します.
下の2の値は7、6<7ですか?はい、7の下にマークをつけます:2;次は7で残りと比較します.
下の3の値は9、7<9ですか?はい、9の下に3とマークします.次は9で残りと比較します.
下の4の値は2、9<2ですか?いいえ.比較完了.
最後に記した下書きは3.すなわち、この配列における最大値の下付きは3である.
Javaアルゴリズムは次のとおりです.
単純選択ソートの時間的複雑さ:O(n^2)
次の論文では,バブルソートの改良アルゴリズムについて論じる:高速ソート
これは2つのアルゴリズム,泡立ち,簡単な選択並べ替えを含むため,少し長い.別々に見てもいいです.それぞれ20分で十分です.足りないなら私を探してください.
この泡のソートについては、これは古典的なアルゴリズムで、もしあなたが聞いたことがなければ、あなたが極品プログラマーだと信じています.
アルゴリズムの原理を知っているかもしれませんが、彼をよく説明することができますか?やってみましょう.
バブルアルゴリズム、例えば:
ソートするデータは{6,3,7,9,2}です.
バブルソートは簡単に言えば、最大の値を徐々に選択し、最後ろに置いて、最初からsize-1の要素の中で最大を見つけて、最後から2番目に置いて、このようにします.
バブルソートは数回に分けて行われますが、まず1回目からどのような動作をするかを見てみましょう.
最初はこうします.
{6,3,7,9,2},6と3を比較し,6>3が成立すると交換する.
{3,6,7,9,2},6と7を比較し,6>7が成立しなければ交換しない.
{3,6,7,9,2},7と9を比較し,7>9が成立しなければ交換しない.
{3,6,7,9,2},9と2を比較し,9>2が成立すると交換する.
{3, 6, 7, 2, 9}. 5つの元素の配列について,4回の比較を行った後,1回の泡立ちが完了した.
次に2回目はどうしますか?9は1回目の中で一番大きく選ばれたので、もう最後まで置いておきました.
では、2回目は実は9を比較する必要はありません.2回目の関心の要素は{3,6,7,2}です.
2回目はこうします
{3,6,7,2},3と6を比較し,3>6が成立しなければ交換しない.
{3,6,7,2},6と7を比較し,6>7が成立しなければ交換しない.
{3,6,7,2},7と2を比較し,7>2が成立すると交換する.
{3, 6, 2, 7}. 4つの元素の配列について,3回の比較を行った後,2回目の泡立ちが完了し,この結果は{3,6,2,7,9}であった.
3回目に関心を持つデータは{3,6,2}であり、具体的な過程は詳しくは言わないが、3回目のソートの結果は{3,2,6}である.合計結果:{3,2,6,7,9}
4回目に関心を持つデータは{3,2}であり,4回目のソートの結果は{2,3}であった.
5回目に気になるデータは{2}ですが、あれ?1つの要素だけがどのようにソートされますか?はい、最初のセクションでソートを直接挿入したときに言いました.
1つの要素のシーケンスだけが秩序化されているので、5回目は無視できます.
5つの要素の配列について,並べ替えに4回,普及後,n個の要素の配列について,並べ替えにn−1回が必要であるという結論も得られた.
public static void bubbleSort(int[] toSort) {
int size = toSort.length;
// ，
// size ， size - 1
for (int i = 0; i < size - 1; i++) {
//
//
// ， ：（ - 1）
//
// size - i,
// size - i - 1
for (int j = 0; j < size - i - 1; j++) {
// ， ，
if (toSort[j] > toSort[j + 1]) {
int tmp = toSort[j];
toSort[j] = toSort[j + 1];
toSort[j + 1] = tmp;
}
}
}
} 複雑度:
時間複雑度:O(n^2)
---------------------
簡単な選択のソートもここに書きたいです.私はよくこの2つのアルゴリズムを混同しているので、ここに書いたほうがいいです.
単純選択ソート:
バブルソートでは、各要素が隣接する要素と比較され、次の要素が現在より大きい場合は交換され、1回の完了後、最大の数字を最後に置くことができます.
単純にソートを選択するのは、無秩序配列の中で最大の要素を最初に見つけて、無秩序配列の最後の要素と交換することです.ここで明らかな違いは次のとおりです.
単純選択ソートでは、1回あたり最大1回の交換が行われます.
たとえば、ソートするデータは{6,3,7,9,2}です.
最初にこうしました
このデータの中で最大の要素を見つけて、私たちは彼が9であることを発見して、それでは彼は最後の要素(以下4と表記して、数値は2)と交換して、交換した後に得ます:{6,3,7,2,9}
2回目:最大の9が末尾に置かれているため,無秩序な配列は{6,3,7,2}である.
このデータの中で最大の要素を見つけて、私たちは彼が7であることを発見して、それでは彼は最後の要素(以下3と表記して、数値は2)と交換して、交換した後に得ます:{6,3,2,7}
3回目:無秩序配列が{6,3,2},最大要素が6であると,最後の要素(以下2,数値2)と交換し,{2,3,6}を得る.
4番目:無秩序配列は{2,3}ですね.これはもう秩序があるのに,どうしてまだ並べ替えているのか.はい、これは特殊な状況です.もし私たちが最初の配列が{6,2,7,9,3}であれば、このステップに進んだとき、無秩序な配列は{3,2}なので、このステップは必要ですが、このステップの最大の要素は3で、最後の要素も彼自身なので、交換する必要はありません.
5回目は、1つの要素しかありません.ソートする必要はありません.
泡神に似ているのではないでしょうか.あなたはnoと言うかもしれませんが、うん、どうせ私は間違っています.
実はもう一つ、バブルソートの重点は最大値の下付きスケールを見つけることです.私たちが最終的に交換するときは、最大値の下付きスケールが指す数値と最後の要素の数値を交換するからです.
では、最大値の下付き文字をどうやって探しますか?
考え方はこうです.
最大値の下付き記号を見つけるために比較する必要があります.
このサイクルでは、比較します.
最初の要素とすべての要素の値は、
他の要素がこの要素より大きい場合は、下にマークします.
さらにこの大きな要素を持って残りのものと比べて、一周したら最大のものを見つけました.
やはり例がはっきりしています.
{6,3,7,9,2}については,まず最大値の下付きを0と仮定した(これは明らかに誤りであるが,これは我々の始まりである).
この比較は1から始まります.
下付き0の値は6、下付き1の値は3.6<3ですか.いいえ、次の要素を比較します.
下の2の値は7、6<7ですか?はい、7の下にマークをつけます:2;次は7で残りと比較します.
下の3の値は9、7<9ですか?はい、9の下に3とマークします.次は9で残りと比較します.
下の4の値は2、9<2ですか?いいえ.比較完了.
最後に記した下書きは3.すなわち、この配列における最大値の下付きは3である.
Javaアルゴリズムは次のとおりです.
public static void selectionSort(int[] toSort) {
int size = toSort.length;
for (int i = 0; i < size - 1; i++) {
int maxIndex = getMaxIndex(toSort, size - i);
// size - i - 1
// ， 。
if (size - i - 1 == maxIndex) {
continue;
}
int tmp = toSort[size - i - 1]; // last unsorted element
toSort[size - i - 1] = toSort[maxIndex];
toSort[maxIndex] = tmp;
}
}
private static int getMaxIndex(int[] toSort, int len) {
// 0
int maxIndex = 0;
for (int i = 1; i < len; i++) {
// tmp
int tmp = toSort[maxIndex];
if (tmp < toSort[i]) {
// ： ， maxIndex！
// ，maxIndex
maxIndex = i;
}
}
return maxIndex;
}単純選択ソートの時間的複雑さ:O(n^2)
次の論文では,バブルソートの改良アルゴリズムについて論じる:高速ソート