Als ich im Internet surfte, fand ich zufällig die folgende URL Ich wollte Blasensortierung studieren.
URL:http://www.mkyong.com/java/java-bubble-sort-example/
Bubble sort is the simplest sorting algorithm, it compares the first two elements, if the first is greater than the second, swaps them, continues doing (compares and swaps) for the next pair of adjacent elements. It then starts again with the first two elements, compares, swaps until no more swaps are required.
-> Vergleichen Sie die Werte zweier benachbarter Elemente im Array Ausrichtungsalgorithmus, der gemäß den Bedingungen ausgetauscht wird (unabhängig davon, ob der Wert groß oder klein ist)
Zum Beispiel Wenn der Eingang 1597253 ist, Die Ausgabe ist 1235579, abhängig von dem Programm, das die Blasensortierung implementiert.
Ich dachte über den Algorithmus nach, den ich implementieren würde. Zuerst, Vergleichen Sie die Größe der ersten und der zweiten Zahl von links. Wenn die Zahl links groß ist-> Tauschen Sie die Position mit der Zahl rechts aus Wenn die Zahl rechts groß ist-> müssen Sie sie nicht ersetzen
Ebenfalls, Vergleichen Sie die Größe der zweiten und dritten, Entscheiden Sie, ob Sie die Position ersetzen möchten oder nicht. Auf die gleiche Weise 3. VS 4., 4. VS 5 .. .. .. Im Vergleich zur 6. und 7. Größe ist die erste Runde vorbei.
Und Die zweite Runde beginnt. Vergleichen Sie die Größe mit der ersten und zweiten, Vergleichen Sie die Größen der zweiten und dritten. .. .. Vergleichen Sie auf die gleiche Weise die Größe mit der 6. und 7., Die zweite Runde ist vorbei.
Im gleichen Fluss So wie es ist, die dritte und die vierte Runde. .. .. Der letzte ist die sechste Runde
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length; // Länge des Arrays // IF Nummer vor> Nummer nach //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;
//配列の中各数字を比べる必要があり、 // Sie müssen auch jede oben geschriebene Runde ausführen und eine Doppelschleife schreiben for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
// wenn vor> nach der Austauschposition if(input[j]>input[j+1]){
temp = input [j]; // Speichern Sie die vorherige Nummer für eine Weile in Variable input [j] = input [j + 1]; // Verschiebe die letzte Nummer an die Position der vorherigen Nummer input [j + 1] = temp; // Verschiebe die vorherige Nummer (in Variable gespeichert) nach hinten
}
}
}
return input;
}
}
Testergebnisse:
122345, genau
Berechnen Sie die Anzahl der Nummernwechsel wie folgt ・ Berechnen und drucken Sie die Anzahl der Male, um die Position der Zahlen auszutauschen ・ Drucken Sie das Ersatzarray
static int[] sort(int[] input){
int count = 0;
int length = input.length;
int temp;
for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
if(input[j]>input[j+1]){
temp = input[j];
input[j] = input[j+1];
input[j+1] = temp;
count++;
//交換後の配列の元素をプリント System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();
}
}
}
System.out.println(count);
return input;
}
Output：
count:1 123254 count:2 122354 count:3 122345
3 = Anzahl der Börsen:
Im schlimmsten Fall, Die Reihenfolge der Zahlen im Array ist 543221 und wird beim Vergleich der Größe der Zahlen immer ausgetauscht. Da das Array 6 Nummern enthält, beträgt die Anzahl der Austausche Erste Runde: 5 Zweite Runde: 4 Dritte Runde: 3 Vierte Runde: 2 Fünfte Runde: 1 Gesamt: 15
Apropos, In diesem Fall sind die Anzahl der Vergleiche und die Anzahl der Austausche gleich.
Mir ist hier einer aufgefallen, Das Programm, das ich oben geschrieben habe, ist tatsächlich ineffizient.
Die Ursache ist Obwohl die Sequenz bereits in aufsteigender Reihenfolge ist Es besteht weiterhin die Möglichkeit, die Größe der Zahlen zu vergleichen.
Sie können dies herausfinden, indem Sie die Anzahl der Vergleiche berechnen.
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length; // Länge des Arrays // IF Nummer vor> Nummer nach //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;
//比較回数を計算用 int count = 0;
//配列の中各数字を比べる必要があり、 //上記書いた各ラウンドも実行する必要があり二重ループを書く for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
//数字大きさ比較する際、配列の元素をプリント count++; System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();
// wenn vor> nach der Austauschposition if(input[j]>input[j+1]){
temp = input [j]; // Speichern Sie die vorherige Nummer für eine Weile in Variable
}
}
}
return input;
}
}
Output:
count:1 213254 count:2 123254 count:3 123254 count:4 122354 count:5 122354 count:6 122345 count:7 122345 count:8 122345 count:9 122345 count:10 122345 count:11 122345 count:12 122345 count:13 122345 count:14 122345 count:15 122345 count:16 122345 count:17 122345 count:18 122345 count:19 122345 count:20 122345 count:21 122345 count:22 122345 count:23 122345 count:24 122345 count:25 122345 count:26 122345 count:27 122345 count:28 122345 count:29 122345 count:30 122345 122345
input [j + 1] = temp; // Verschiebe die vorherige Nummer (in Variable gespeichert) nach hinten Dreimal ist das Array bereits in aufsteigender Reihenfolge, aber das Programm wird weiterhin fortgesetzt und ist ineffizient. Die Lösung besteht darin, zu überprüfen, ob das Array in aufsteigender Reihenfolge vorliegt. Überprüfen Sie die Methode mit URL, Variable mit booleschem Wert is_sorted; wurde verwendet.
Mit Blick auf die Erklärung, // is sorted? then break it, avoid useless loop. Wenn die Situation sortiert ist, beenden Sie das Programm und Vermeiden Sie unnötige Schleifen.
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length; // Länge des Arrays // IF Nummer vor> Nummer nach //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;
//比較回数を計算用 int count = 0;
Boolean is_sorted;
//配列の中各数字を比べる必要があり、 //上記書いた各ラウンドも実行する必要があり二重ループを書く for(int i=0;i<length;i++){
//ラウンドが始まる前にTrueに設定、もし比較する行為をしない場合ループ終止 is_sorted = true;
for(int j=0;j<length-1;j++){
//数字大きさ比較する際、配列の元素をプリント count++; System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();
// wenn vor> nach der Austauschposition if(input[j]>input[j+1]){
temp = input [j]; // Speichern Sie die vorherige Nummer für eine Weile in Variable input [j] = input [j + 1]; // Verschiebe die letzte Nummer an die Position der vorherigen Nummer input [j + 1] = temp; // Verschiebe die vorherige Nummer (in Variable gespeichert) nach hinten
//交換行為をしたらFalseに変更、 //配列がまだ昇順になってないとのこと is_sorted = false;
}
}
if (is_sorted) break;
}
return input;
}
}
Output： count:1 213254 count:2 123254 count:3 123254 count:4 122354 count:5 122354 count:6 122345 count:7 122345 count:8 122345 count:9 122345 count:10 122345 122345
Wenn es N Nummern gibt Mindestens N Vergleiche in der ersten Runde Die Anzahl der Vergleiche in der zweiten Runde beträgt mindestens N-mal
Schlimmster Fall = O (n²)
Andere: Wenn der japanische Ausdruck seltsam ist, weil ich ein Ausländer bin Ich wäre Ihnen dankbar, wenn Sie es mir sagen könnten.
2019/2/16 Die zeitliche Komplexität und die Anzahl der Vergleiche von Zahlen mit dem Algorithmus, an den ich dachte, wurden korrigiert.
Recommended Posts