원칙 : 인접한 두 가지 요소와 교환 요소를 큰 값으로 오른쪽 끝과 비교하십시오.
아이디어 : 인접한 두 개의 숫자를 순서대로 비교하고, 소수점을 앞쪽에 놓고 많은 숫자를 뒷면에 놓습니다. 즉, 첫 번째 여행에서 : 먼저 첫 번째와 두 번째 숫자를 비교하고, 소수점을 이전과 그 이후에 넣습니다. 그런 다음 두 번째 숫자와 세 번째 숫자를 비교하고 큰 숫자 전후 소수점을 넣고 마지막 두 숫자를 비교할 때까지 이렇게 계속하십시오. 모든 정렬이 완료 될 때까지 첫 번째 단계를 반복하십시오.
예를 들어 : 배열을 정렬하려면 : int [] arr = {6,3,8,2,9,1};
첫 번째 순서 :
첫 번째 정렬 : 6 및 3 비교, 6은 3보다 크고 스왑 위치 : 368291
두 번째 정렬 : 6 및 8 비교, 6은 8 미만, 교환 위치 없음 : 368291
세 번째 순서 : 8 및 2 비교, 8은 2보다 크고 스왑 위치 : 362891
네 번째 순서 : 8 및 9 비교, 8은 9 미만, 교환 위치 없음 : 362891
다섯 번째 순서 : 9 및 1 비교 : 9는 1, 스왑 위치 : 362819입니다.
첫 번째 여행은 총 5 회 비교되었으며 결과를 정렬했습니다. 362819
-----------------------------------------------------------------------------------------
두 번째 순서 :
첫 번째 정렬 : 3 및 6 비교, 3은 6 미만, 교환 위치 없음 : 362819
두 번째 정렬 : 6 및 2 비교, 6은 2보다 크고 스왑 위치 : 326819
세 번째 순서 : 6 및 8 비교, 6은 8보다 크며 교환 위치 없음 : 326819
네 번째 순서 : 8 및 1 비교, 8은 1보다 크며 스왑 위치 : 326189
두 번째 여행은 총 비교되었고 분류 결과는 다음과 같습니다. 326189
-----------------------------------------------------------------------------------------
세 번째 순서 :
첫 번째 정렬 : 3 및 2 비교, 3은 2보다 크고 스왑 위치 : 236189
두 번째 정렬 : 3 및 6 비교, 3은 6 미만, 교환 위치 없음 : 236189
세 번째 순서 : 6 및 1 비교, 6은 1보다 크며 스왑 위치 : 231689
두 번째 여행은 총 비교되었고 분류 결과는 다음과 같습니다. 231689
-----------------------------------------------------------------------------------------
네 번째 순서 :
첫 번째 정렬 : 2 및 3 비교, 2는 3 미만, 교환 위치 없음 : 231689
두 번째 정렬 : 3 및 1 비교, 3은 1보다 크고 스왑 위치 : 213689
두 번째 여행은 총 비교되었고 분류 결과는 다음과 같습니다. 213689
-----------------------------------------------------------------------------------------
다섯 번째 주문 :
첫 번째 정렬 : 2 및 1 비교, 2는 1보다 크며 스왑 위치 : 123689
두 번째 여행은 총 비교되었고 분류 결과는 다음과 같습니다. 123689
-----------------------------------------------------------------------------------------
최종 결과 : 123689
-----------------------------------------------------------------------------------------
이것으로부터 우리는 n 숫자를 정렬해야하고 N-1 번은 총 정렬된다는 것을 알 수 있습니다. 각 I-Pass의 분류 시간 수는 (NI)이므로 이중 루프 명령문을 사용하여 외부 레이어가 각 트립의 시간 수를 몇 배 제어 할 수 있는지 제어 할 수 있습니다.
for (int i = 1; i <arr.length-1; i ++) {for (int j = 1;버블 분류의 장점 : 정렬 할 때마다 정렬 할 때마다 더 큰 값을 찾을 수 있기 때문에 비교할 수 있습니다. 위에서 언급했듯이 : 첫 번째 비교 후 마지막 숫자는 가장 큰 숫자 여야합니다. 두 번째로 정렬 할 때 마지막 숫자 이외의 다른 숫자 만 비교하면 두 번째 비교에 참여한 숫자 후에 가장 큰 숫자가 순위가 매겨 질 수도 있습니다. 세 번째 시간을 비교할 때, 마지막 두 숫자 이외의 다른 숫자 만 비교하면됩니다. 즉, 비교를 수행하지 않으면 한 번 비교할 때마다 알고리즘의 양이 어느 정도 줄어 듭니다.
시간 복잡성 측면에서 :
1. 데이터가 순서대로 진행되면 정렬을 완료하기 위해 여행 만하면됩니다. 필요한 비교 및 레코드 운동의 수는 모두 최소값, 즉 CMIN = N-1; MMIN = 0; 따라서 기포 분류에 가장 적합한 시간 복잡성은 O (n)입니다.
2. 불행히도 우리의 데이터가 반대 순서라면 N-1 순서가 필요합니다. 각 순서는 비교해야하며 (1≤i≤n-1), 교환 기록 위치에 도달하려면 각 비교가 레코드로 3 번 이동해야합니다. 이 경우 비교 및 움직임 시간은 모두 최대 값에 도달합니다. 기포 정렬의 최악의 시간 복잡성은 다음과 같습니다. O (N2).
요약하면 : 거품 정렬의 총 평균 시간 복잡성은 다음과 같습니다. O (n2).
코드 구현 :
/ * * 버블 정렬 */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 = 1; i <arr.length; i ++) {// 외부 루프는 (int j = 1; j <arr.length-i; j ++)의 정렬 시간을 제어합니다 (// 내부 루프는 (arr [j-1]> arr [j])에 정렬 될 때마다 몇 번 컨트롤됩니다. [int temp = j]; ARR [J] = ARR [J-1]; ARR [J-1] = 온도; }}} system.out.println (); System.out.println ( "정렬 된 배열은 :"); for (int num : arr) {system.out.print (num+""); }}}