버블 정렬 알고리즘의 Java 구현 및 간단한 최적화 예

원리

버블 정렬은 아마도 모든 프로그래머가 사용하는 알고리즘이면서 가장 친숙한 알고리즘 중 하나일 것입니다.
아이디어는 복잡하지 않습니다.
이제 n개의 요소가 있는 arr[] 배열을 정렬한다고 가정해 보겠습니다.
1. n=1인 경우: 당연히 정리할 필요가 없습니다. (사실 이 논의는 불필요한 것 같습니다.)
2. n>1인 경우:
(1) 첫 번째 요소부터 시작하여 인접한 두 요소를 모두 비교하면 다음 요소 Big보다 좋습니다. 전자는 최종 결과에서 확실히 뒤쳐질 것입니다. 그래서 우리는 이 두 요소를 교환합니다. 그런 다음 인접한 두 요소를 비교합니다. 이는 마지막 요소 쌍이 비교되고 첫 번째 정렬 라운드가 완료될 때까지 계속됩니다. 마지막 요소가 배열에서 가장 커야 한다는 것을 확신할 수 있습니다(비교적 큰 요소가 매번 뒤쪽에 배치되기 때문입니다).
(2) 위의 과정을 반복합니다. 이번에는 마지막 항목이 이미 정렬되어 있으므로 고려할 필요가 없습니다.
(3) 이 작업은 요소가 하나만 남을 때까지 수행됩니다. 이 요소가 가장 작아야 정렬이 완료됩니다. 분명히 n-1 정렬이 발생합니다.
위 프로세스에서 정렬할 때마다(또는 "라운드"라고 함) 숫자가 특정 위치에서 최종 위치까지 천천히 "부유"합니다(개략도를 그리고 수직으로 배열을 그려서 확인합니다). 버블 정렬과 비슷하므로 "버블 정렬"이라고 합니다.

코드 구현:

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  //最多做n-1趟排序
       for(int j = 0 ;j < score.length - i - 1; j++){  //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围实在逐步缩小的)
         if(score[j] < score[j + 1]){  //把小的值交换到后面
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print("第" + (i + 1) + "次排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print("最终排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

알고리즘 성능/복잡성
루프 변수 증가 및 초기화 시간을 무시합니다. 먼저 알고리즘의 비교 횟수를 분석합니다. 위의 버블 정렬은 아무런 개선 없이도 입력 데이터에 상관없이 n-1번의 정렬을 수행하게 되며, 각 정렬에 필요한 비교 횟수가 n-1에서 0으로 감소한다는 것을 쉽게 알 수 있습니다. 그러면 총 비교 횟수는 (n-1)+(n-2)+...+2+1 = (n-1)n/2≒(n^2)/2입니다. (여기서는 제곱을 계산하는 방법을 모르기 때문에 여기서는 n^2를 사용하여 제곱을 표현합니다. 아래도 마찬가지입니다.)
과제 개수를 살펴보겠습니다. 여기서 할당은 교환 작업을 의미합니다. 위 코드의 경우 한 번의 교환은 세 개의 할당과 같습니다. 매번 교체가 필요하지 않기 때문에 할당 작업 횟수는 입력 데이터와 관련됩니다. 가장 좋은 경우, 즉 처음부터 순서대로 하면 할당 개수는 0개이다. 최악의 경우 할당 개수는 (n-1)n/2입니다. 입력 데이터가 균등하게(또는 "완전히 무작위") 분포되어 있다고 가정하면 비교 시 교환 횟수가 대략 절반 정도 됩니다. 위 결과를 통해 평균적인 경우 과제 개수는 3/2 * (n^2)/2 = 3/4*(n^2)라는 것을 알 수 있습니다.
결론적으로 말하자면, 이 경우 버블 정렬의 공간 복잡도(추가 공간)는 항상 O(1)입니다.

Improvement
는 최적의 시간 복잡도를 보여주며, 데이터가 완전히 정렬되었을 때 O(n)입니다. 그렇지 않으면 거의 항상 O(n^2)입니다. 따라서 알고리즘은 데이터가 기본적으로 정렬되어 있을 때 가장 잘 수행됩니다.
그런데 위 코드는 어떻게 O(n) 복잡도를 가질 수 있을까요? 실제로 위의 내용은 가장 간단한 경우에 불과하므로 최선의 경우 알고리즘이 O(n) 복잡도를 갖도록 하려면 몇 가지 개선이 필요한 코드는 다음과 같습니다.

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
    swap=false;
    for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort

사실 대용량 데이터를 사용할 때는 버블 정렬을 거의 사용하지 않기 때문에, 작은 데이터를 사용할 때는 추가된 부울 변수로 인해 추가적인 오버헤드가 발생하게 됩니다. 따라서 개인적으로 위의 개선된 알고리즘은 순전히 이론적인 것이라고 생각합니다. 일반적으로 버블 정렬의 경우 전자를 작성하면 됩니다.

알고리즘 안정성
인접한 요소가 동일할 때 위치를 바꿀 필요가 없으므로 버블 정렬이 안정적인 정렬임을 쉽게 알 수 있습니다.

알고리즘의 적용 시나리오
버블 정렬은 간단한 아이디어와 간단한 코드를 가지고 있어 특히 작은 데이터를 정렬하는 데 적합합니다. 하지만 알고리즘의 복잡도가 높아 데이터 양이 많을 때 사용하기에는 적합하지 않습니다. 데이터가 많을 때 사용해야 한다면 선택 정렬 등 알고리즘을 개선하는 것이 가장 좋습니다.

버블 정렬 알고리즘의 Java 구현과 간단한 최적화 예제를 보려면 PHP 중국어 웹사이트에 주목하세요!