Optimierte Version der Blasensortierung, Leistung nahezu verdoppelt

Die ursprüngliche Blasensortierung ist relativ zeitaufwändig, selbst wenn ein Array nach mehreren Austauschrunden geordnet wurde, wie zum Beispiel das Array [2,1,3,4,5,6,7], Nach der ersten Runde , es ist geordnet geworden, aber das hartnäckige Sprudeln muss den unnährstoffreichen paarweisen Vergleich noch fortsetzen und opfert so Zeit.

Wenn Sie ein Flag verwenden, um festzustellen, ob das aktuelle Array in Ordnung ist, verlassen Sie die Schleife, wenn es in Ordnung ist, was die Leistung der Blasensortierung erheblich verbessern kann~

Aufgrund der Blase Sortieren Die zeitliche Komplexität beträgt O (n * n). Wenn also mehr Daten vorhanden sind, wird sie langsamer, was für die Sortierung großer Datenmengen sehr ungeeignet ist. Daher haben wir beim Testen auch ein Zufallsarray mit einer Länge von 800 verwendet.

Der Code lautet wie folgt:

package go.derek;
import java.util.*;
public class Sort {
//Bubble sort
public void bubbleSort(int[] arr){
for(int i=0;i for(int j=arr.length-1;j>i;j -- ){
if(arr[j] int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
🎜> 🎜> 🎜> 🎜> //Verbesserte Version der Blasensortierung
public void bubbleSort_plus(int[] arr){
boolean flag=true;
for(int i=0;i flag=false;
for(int j=arr.length-1; j> ;i;j--){
if(arr[j] flag=true;
int tmp=arr[j];
arr [ j] = arr [j-1]; args ){
Sort s=new Sort();
int[] arr1=new int[800];
for(int i=0;i arr1 [i]=new Random().nextInt(800)+1;
}
int[] arr2=new int[800];
for(int i=0;i arr2[i]=new Random().nextInt(800)+1;
}
long n=System.currentTimeMillis();
s.bubbleSort_plus(arr1);
long m=System.currentTimeMillis();
System.out.println("Blasensortierzeit: "+(m-n)+"ms");
long a=System.currentTimeMillis(); 🎜> s.bubbleSort_plus(arr2);
long b=System.currentTimeMillis();
System.out.println("Zeitaufwändig nach der Optimierung: "+(b-a)+"ms");
}
}

Nachdem wir es mehrmals ausgeführt hatten, fanden wir das offensichtlichste Ergebnis:

Die Blasensortierung dauerte 12 ms.
Nach der Optimierung dauerte sie 4 ms.

Ja , die Bedeutung dieser Flagge~

Für optimierte Versionen der Blasensortierung wird die Leistung nahezu verdoppelt. Für verwandte Artikel beachten Sie bitte die chinesische PHP-Website!