バブルソートの最適化バージョン、パフォーマンスがほぼ2倍になりました

元のバブルソートは、数ラウンドの交換後に配列が順序付けされた場合でも (たとえば、配列 [2,1,3,4,5,6,7])、最初の 1 ラウンド後には比較的時間がかかります。秩序あるものにはなりましたが、頑固な泡立ちにより栄養のないペアごとの比較を継続する必要があり、時間が犠牲になります。

現在の配列が正しいかどうかを判断するためにフラグを使用する場合、正しい場合はループを終了します。これにより、バブル ソートのパフォーマンスが大幅に向上します~

バブル ソートの時間計算量は O(n* n) そのため、データが増えると速度が遅くなり、大きなデータの並べ替えには非常に不向きになるため、テスト時には長さ 800 のランダム配列も使用しました。

コードは次のとおりです:

package go.derek;
import java.util.*;
public class 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;
}
}
}
}
//バブルソートの改良版
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];
arr[j-1]=tmp;
}
}
}
}
public static void main(String[] 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("バブルソート時間: "+(m-n)+"ms");
long a=System. ();
s.bubbleSort_plus(arr2);
long b=System.currentTimeMillis();
System.out.println("最適化後にかかる時間: "+(b-a)+"ms");
}
}

複数回実行した後、最も明白な結果が見つかりました:

バブルソート時間: 12ミリ秒
最適化後の時間: 4ミリ秒

このフラグの重要性がわかります~

より多くのバブリングソート最適化バージョン、パフォーマンスはほぼ 2 倍になります。関連記事については、PHP 中国語 Web サイトに注目してください。