버블 정렬의 최적화된 버전, 성능이 거의 두 배 향상됨

원래 버블 정렬은 배열 [2,1,3,4,5,6,7]과 같이 여러 라운드의 교환 후에 배열이 주문되었더라도 상대적으로 시간이 많이 걸립니다. , 질서정연해졌지만 완고한 버블링은 여전히 ​​영양가 없는 ​​쌍 비교를 계속해야 하므로 시간을 희생합니다.

현재 배열이 순서대로 되어 있는지 확인하기 위해 플래그를 사용한다면, 순서대로 되어 있으면 루프를 종료하면 버블 정렬의 성능이 크게 향상될 수 있습니다~

버블 때문에 sort 시간 복잡도가 O(n*n)이므로 데이터가 많을수록 속도가 느려지는데, 이는 빅데이터 정렬에 매우 부적합하므로 테스트 시 길이 800의 랜덤 배열도 사용했습니다.

코드는 다음과 같습니다.

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;
}
}
}
}
//버블 정렬의 개선된 버전
public void bubbleSort_plus(int[] arr){
부울 플래그=true;
for(int i=0;i 플래그=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 ){
정렬 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.currentTimeMillis()
s.bubbleSort_plus(arr2);
long b=System.currentTimeMillis();
System.out.println("최적화 후 시간 소모: "+(ba)+"ms");
}
}

여러 번 실행한 후 가장 확실한 결과를 찾았습니다.

버블 정렬에 12ms가 걸렸습니다.
최적화 후 4ms가 걸렸습니다

예 , 이 플래그의 중요성~

버블소트를 더욱 최적화한 버전으로 성능이 2배 가까이 향상되니 관련 글은 PHP 중국어 홈페이지를 주목해주세요!