Java 클래식 알고리즘 버블 정렬 코드 공유

원제: Java의 클래식 알고리즘: Bubble Sort(Bubble Sort)

버블 정렬이란?

버블 정렬은 순서에 따라 요소를 서로 쌍으로 비교하는 간단한 정렬 알고리즘입니다. 순서가 큰 것에서 작은 것 순이면 두 요소를 서로 비교할 때 더 큰 요소가 먼저 순위가 지정되고, 그렇지 않으면 더 큰 요소가 나중에 순위가 지정됩니다. 버블 정렬은 큰 것부터 작은 것까지의 정렬과 작은 것부터 큰 것의 정렬로 나누어진다.

원리: 인접한 두 요소를 비교하고 값이 더 큰 요소를 오른쪽 끝으로 바꿉니다.

아이디어: 인접한 두 숫자를 차례로 비교하여 앞에 소수점을 넣고 뒤에 큰 숫자를 넣습니다. 즉, 첫 번째 단계에서는 먼저 첫 번째 숫자와 두 번째 숫자를 비교하고 소수를 먼저 배치하고 큰 숫자를 마지막에 배치합니다. 그런 다음 두 번째 숫자와 세 번째 숫자를 비교하고 소수를 앞에 놓고 큰 숫자를 뒤에 놓고 마지막 두 숫자를 비교할 때까지 이렇게 계속하여 소수를 앞에 놓고 큰 숫자를 뒤에 넣습니다. 모든 정렬이 완료될 때까지 첫 번째 단계를 반복합니다.

예: 배열을 정렬하려면: int[] arr={6,3,8,2,9,1};

1차 정렬:

1차 정렬: 6 및 3 비교, 6가 3보다 큼, 위치 바꾸기: 3 6 8 2 9 1

두 번째 정렬 : 6과 8을 비교하면 6이 보다 작습니다. 8, 위치 교환 없음: 3 6 8 2 9 1

세 번째 정렬: 8과 2을 비교하면 8이 2보다 큽니다. , 교환 위치: 3 6 2 8 9 1

네 번째 순서: 8 및 9 비교, 8이 9보다 작음, 위치 교환 없음: 3 6 2 8 9 1

다섯 번째 정렬: 9 및 1 비교: 9가 1보다 큼, 위치 바꾸기: 3 6 2 8 1 9

첫 번째 여행에서 총 5 비교를 했고, 정렬 결과는 3 6 2 8 이었습니다. 1 9

---------------------------------- --- ----------

2차 정렬:

첫 번째 정렬: 3 및 6을 비교하면 3이 6 , 위치 교환하지 않음: 3 6 2 8 1 9

두 번째 정렬: 6 및 2 비교, 6이 2보다 큼, 위치 바꾸기: 3 2 6 8 1 9

3위: 6 및 8 비교, 6이 8보다 큼, 위치 교환 없음: 3 2 6 8 1 9

네 번째 정렬: 8 및 1 비교, 8은 1보다 큽니다. 위치 바꾸기: 3 2 6 1 8 9

두 번째 패스에서 총 4개의 비교가 이루어졌으며 정렬 결과는 다음과 같습니다. 3 2 6 1 8 9

---- -------------------------- ----------- ---------------

세 번째 정렬:

첫 번째 정렬: 3 2과 비교하면 3이 2, 위치 교환: 2 3 6 1 8 9

두 번째 정렬:

3 및 6 비교, 3이 6보다 작습니다. 위치를 교환하지 마세요. 2 3 6 1 8 9

세 번째 정렬: 6 및 1 비교, 6 더 큼 1보다 위치 교환: 2 3 1 6 8 9

두 번째 여행이 진행됩니다. 총 3 비교, 정렬 결과: 2 3 1 6 8 9

------------ - ------------------------------------------------- - -------

네 번째 정렬:

첫 번째 정렬: 2 및 3 비교, 2이 3보다 작음, 위치 교환 없음: 2 3 1 6 8 9

두 번째 정렬: 3 및 1 비교 , 3이 1보다 큽니다. 위치 바꾸기: 2 1 3 6 8 9

두 번째 여행은 총 2 비교를 진행했고, 정렬 결과: 2 1 3 6 8 9

----------------------------------------------- --- --------

다섯 번째 정렬:

첫 번째 정렬: 2과 1을 비교하면 2이 1, 포지션 교환: 1 2 3 6 8 9

두 번째 여행은 총 1회 비교, 정렬 결과: 1 2 3 6 8 9

------------------- ---------- -------------- -----

최종 결과:

1 2 3 6 8 9--------- -------- ---------------- --------

N개 숫자를 정렬해야 하며 총 N개임을 알 수 있습니다. -1 정렬이 수행될 때마다 i에 대한 정렬 횟수는 (N-i)회입니다. , 즉 이중 루프 문을 사용할 수 있습니다. 외부 레이어는 루프의 횟수를 제어하고, 내부 레이어는 루프의 횟수를 제어합니다. 레이어는 각 패스의 사이클 수, 즉

for(int i=1;i<arr.length;i++){

    for(int j=1;j<arr.length-i;j++){

    //交换位置

}

버블 정렬의 장점: 정렬이 수행될 때마다 비교 횟수가 한 번 줄어듭니다. 수행하면 더 큰 값을 찾습니다. 위의 예와 같이 첫 번째 비교 후에는 마지막 숫자가 가장 큰 숫자여야 합니다. 두 번째 정렬에서는 마지막 숫자를 제외한 다른 숫자만 비교하면 되며 가장 큰 숫자도 찾을 수 있습니다. 두 번째 비교에 참여한 숫자 뒤에는 세 번째 비교에서는 마지막 두 숫자를 제외한 나머지 숫자만 비교하면 되는 식이다... 즉, 비교를 하지 않을 때마다 여행 당 한 번의 비교가 줄어든다. 어느 정도 알고리즘의 양.

시간 복잡도 측면에서:

　1. 데이터가 올바른 경우 정렬을 완료하는 데 한 번의 이동만 필요합니다. 필요한 비교 횟수와 레코드 이동 횟수가 모두 최소값에 도달합니다. 즉, C_min=n-1; M_min=0; 따라서 버블링 정렬의 가장 좋은 시간 복잡도는 O_{(n)입니다.}

2. 아쉽게도 데이터가 역순인 경우 n-1 패스가 필요합니다. 각 정렬 작업에는 n-i 비교(1≤i≤n-1)가 필요하며, 각 비교에서는 교환 레코드 위치에 도달하기 위해 레코드를 3번 이동해야 합니다. 이 경우 비교 및 ​​이동 횟수가 최대에 도달합니다. 버블 정렬의 최악의 시간 복잡도는 O_(n²)입니다.

요약하면 버블 정렬의 전체 평균 시간 복잡도는 O_{(n² )}.

Java 클래식 알고리즘 버블 정렬 코드:

/*
 * 冒泡排序 */public class BubbleSort {
　　public static void main(String[] args) {
　　　　int[] arr={6,3,8,2,9,1};
　　　　System.out.println("排序前数组为：");
　　　　for(int num:arr){
　　　　　　System.out.print(num+" ");
　　　　}
　　　　for(int i=0;i<arr.length-1;i++){//外层循环控制排序趟数　　　　　　for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟排序多少次　　　　　　　　if(arr[j]>arr[j+1]){
　　　　　　　　　　int temp=arr[j];
　　　　　　　　　　arr[j]=arr[j+1];
　　　　　　　　　　arr[j+1]=temp;
　　　　　　　　}
　　　　　　}
　　　　} 
　　　　System.out.println();
　　　　System.out.println("排序后的数组为：");
 　　　　for(int num:arr){
 　　　　　　System.out.print(num+" ");
 　　　　} 
　　}
 }

자세히 알아보기 고전적인 Java 알고리즘 버블 정렬에 대해 공유합니다. PHP 중국어 웹사이트에 주목하세요!