원칙
버블 분류는 아마도 모든 프로그래머가 사용할 수있는 알고리즘이며 가장 친숙한 알고리즘 중 하나 일 것입니다.
그 아이디어는 복잡하지 않습니다.
배열 ARR []가 정렬되었고 N 요소가 있다고 가정합니다.
1. n = 1이라면 : 분명히, 대기열이 필요하지 않습니다. (사실,이 토론은 불필요한 것 같습니다)
2. n> 1 인 경우 :
(1) 우리는 첫 번째 요소부터 시작하여 인접한 두 가지 요소를 모두 비교합니다. 이전 요소가 다음 요소보다 크면 전자는 최종 결과에서 확실히 순위가 매겨 질 것입니다. 그래서 우리는이 두 요소를 교환합니다. 그런 다음 다음 두 인접한 요소를 비교하십시오. 이런 식으로, 마지막 요소 쌍이 비교 될 때까지 첫 번째 라운드 라운드가 완료됩니다. 마지막 요소는 배열에서 가장 큰 요소 여야합니다 (비교적 큰 요소는 매번 뒷면에 배치되기 때문에).
(2) 위의 과정을 반복하십시오. 이번에는 마지막 과정이 이미 배열되어 있기 때문에 마지막 과정을 고려할 필요가 없습니다.
(3) 요소가 하나만 남을 때까지 요소가 가장 작아야하며 정렬이 끝날 수 있습니다. 분명히, N-1 분류가 수행되었다.
위의 프로세스에서 매번 (또는 "휠"이 정렬되면, 숫자는 특정 위치에서 최종 위치로 천천히 "float"됩니다 (기포처럼 회로도를 그리며 배열을 수직으로 그립니다).
코드 구현 :
Public Class Bubblesort {public static void main (String [] args) {int score [] = {67, 69, 75, 87, 89, 90, 99, 100}; for (int i = 0; i <sc 이후의 int temp = score [j]; 스코어 [J] = 점수 [j + 1]; 스코어 [j + 1] = 온도; }} system.out.print ( "th" + (i + 1) + "시퀀스 분류 결과 :"); for (int a = 0; a <sc } system.out.println ( ""); } system.out.print ( "최종 정렬 결과 :"); for (int a = 0; a <sc }}}
알고리즘 성능/복잡성
루프 변수가 자동으로 증가하고 초기화되는 시간을 무시합니다. 먼저 알고리즘의 비교 수를 분석하십시오. 입력 데이터에 관계없이 위의 기포 분류가 N-1 라운드에서 수행 될 것이며, 각 분류 라운드의 횟수는 N-1에서 0에서 0에서 비교해야한다는 것을 쉽게 알 수 있습니다. 그러면 총 비교 수는 (n-1)+...+2+1 = (n-1) N/2 (n^2)/2입니다. (여기서 사각형을 만드는 방법을 모르기 때문에 여기에서 n^2를 사용하여 제곱을 나타냅니다.
과제 수를 살펴 보겠습니다. 여기에서 과제는 교환 작업을 나타냅니다. 위의 코드의 경우 1 개의 교환은 3 개의 할당과 같습니다. 교환이 필요할 때마다 할당 작업 수는 입력 데이터와 관련이 있습니다. 최선의 경우, 즉, 주문이 처음에있을 때 과제 수는 0입니다. 최악의 경우 과제 수는 (n-1) n/2입니다. 입력 데이터가 평균 (또는 "완전히 무작위") 분포라고 가정하면 교환 수의 약 절반이됩니다. 위의 결과로부터, 우리는 평균 사례를 얻을 수 있으며, 할당 수는 3/2 * (n^2)/2 = 3/4 * (n^2)입니다.
요약하면, 어쨌든, 기포 분류 공간 복잡성 (여분의 공간)은 항상 O (1)입니다.
개선하다
데이터가 완전히 주문 될 때 최적의 시간 복잡성이 표시됩니다. 다른 경우에는 거의 항상 O (n^2)입니다. 따라서 데이터가 기본적으로 주문 될 때 알고리즘이 가장 잘 수행됩니다.
그러나 위의 코드는 어떻게 O (n) 복잡성을 가질 수 있습니까? 실제로 위의 것은 기본 아이디어에 중점을두기 때문에 가장 간단한 경우 일뿐입니다. 알고리즘에 최선의 경우 O (n) 복잡성을 갖기 위해서는 일부 개선이 필요합니다. 개선 된 코드는 다음과 같습니다.
public static void bubblesort (int [] arr) {int temp = 0; 부울 스왑; for (int i = arr.length -1; i> 0; --i) {// 각 종류의 길이는 swap = false; for (int j = 0; ARR [J] = ARR [J + 1]; ARR [J + 1] = 온도; SWAP = true; }} // loop j if (swap == false) {break; }} // loop i} // 메소드 Bubblesort실제로, 많은 양의 데이터의 경우 버블 분류가 거의 사용되지 않기 때문에 작은 데이터를 사용할 때 추가 된 부울 변수는 실제로 추가 오버 헤드를 유발합니다. 그래서 나는 개인적으로 위의 개선 된 알고리즘이 순전히 이론적이라고 생각합니다. 일반적으로 버블 링 분류로 이전을 작성하십시오.
알고리즘 안정성
인접 요소가 동일 할 때 우리는 그들의 위치를 교환 할 필요가 없으므로 거품 정렬은 안정적인 종류입니다.
알고리즘 적용 가능한 시나리오
버블 분류에 대한 아이디어는 간단하고 코드는 간단하여 작은 데이터를 정렬하는 데 특히 적합합니다. 그러나 알고리즘의 복잡성이 높기 때문에 데이터 볼륨이 클 때 사용하기에 적합하지 않습니다. 더 많은 데이터가있을 때 사용해야하는 경우 정렬 방법 선택과 같은 알고리즘을 개선하는 것이 가장 좋습니다.