Java의 버블 정렬에 대한 간단한 예제 분석

이 글에서는 주로 Java의 간단한 버블 정렬 예제를 소개하며, 관심 있는 친구들은 참고할 수 있습니다.

1. 알고리즘 원리

인접 요소 비교. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.

첫 번째 쌍부터 시작하여 마지막 쌍으로 끝나는 각 인접 요소 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.

마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.

비교할 숫자 쌍이 더 이상 없을 때까지 매번 요소 수를 줄여 위 단계를 계속 반복하세요.

2. 구현 아이디어

외부 루프 변수를 i로 설정하고 내부 루프 변수를 j로 설정하여 이중 루프를 사용하여 구현합니다. 정렬해야 할 n개의 숫자가 있는 경우 외부 루프는 n-1번 반복되고, 내부 루프는 n-1, n-2,...,1번 반복됩니다. 매번 비교되는 두 요소는 내부 루프 j와 관련이 있으며 각각 a[j]와 a[j+1]로 식별할 수 있습니다. i의 값은 1, 2,..., n-1입니다. . 각 i에 대해 j의 값은 0,1,2,...n-i입니다.

배열 길이가 N:

1이라고 가정합니다. 인접한 두 데이터를 비교하여 전자의 데이터가 후자의 데이터보다 크면 두 데이터를 교환합니다.
2． 이러한 방식으로 0번째 데이터를 배열의 N-1번째 데이터로 이동한 후 가장 큰 데이터가 배열의 N-1번째 위치로 "싱크"됩니다.
3． N=N-1, N이 0이 아니면 이전 두 단계를 반복하고, 그렇지 않으면 정렬이 완료됩니다.

3. 코드 구현

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      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]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

4. 성능 분석

레코드 순서의 초기 상태가 "양수"인 경우 버블 정렬 프로세스는 정렬 중에 한 번만 정렬하면 됩니다. process 레코드 이동 없이 n-1 비교만 필요합니다. 반대로 레코드 순서의 초기 상태가 "역순"인 경우 n(n-1)/2 비교 및 ​​레코드 이동이 필요합니다. 따라서 버블 정렬의 전체 시간 복잡도는 O(n*n)입니다.

5. 알고리즘 최적화

버블 정렬 방법의 단점 및 개선 방법:

먼저 정렬 과정에서 최종 정렬을 수행한 후 데이터가 완전히 정렬되었음에도 불구하고 프로그램이 완료 여부를 판단할 수 없습니다. 이 문제를 해결하기 위해 플래그 플래그를 설정하고 해당 초기 값을 true로 설정하여 정렬된 테이블이 정렬되지 않은 테이블임을 나타냅니다. 각 정렬이 시작되기 전에 플래그 값을 true로 설정하고 데이터 처리를 수행합니다. 교환하면 플래그를 false로 변경합니다. 새로운 정렬 시작 시 이 플래그를 확인하세요. 이 플래그가 거짓이면 지난번에 데이터가 교환되지 않았음을 의미하며, 그렇지 않으면 정렬이 수행됩니다. 정렬, 한 번의 스캔에는 데이터 교환이 없을 수도 있고, 하나 이상의 데이터 교환이 있을 수도 있습니다. 기존의 버블 정렬 알고리즘과 최근 몇 년 동안 개선된 일부 알고리즘에서는 한 번의 스캔에서 데이터 교환이 있는지 여부에 대한 정보만 기록됩니다. , 데이터 교환이 발생한 위치는 기록되지 않습니다. 이 정보를 최대한 활용하기 위해 전역 스캔의 각 역순 데이터 쌍에 대해 로컬 버블 정렬을 수행할 수 있으며 이를 로컬 버블 정렬이라고 합니다. 로컬 버블 정렬은 버블 정렬 알고리즘과 동일한 시간 복잡도를 가지며, 필수 키워드의 비교 횟수와 이동 횟수는 정방향 및 역순 모두 정확히 동일합니다. 로컬 버블 정렬과 버블 정렬 사이의 데이터 이동 횟수는 항상 동일하고 로컬 버블 정렬에 필요한 키 비교 횟수는 버블 정렬보다 적은 경우가 많기 때문에 이는 로컬 버블 정렬이 더 낮을 가능성이 있음을 의미합니다. 비교 횟수가 적다는 장점이 프로그램 복잡도에 따른 추가 오버헤드를 상쇄하기 어려울 때, 데이터 양이 많을 때 로컬 버블 정렬의 시간 성능이 향상되었습니다. 버블정렬보다 훨씬 나은 정렬이다. N개의 정렬되지 않은 데이터에 대해 버블 정렬을 수행할 때 k번째 데이터와 k+1번째 데이터가 역순이면 k+1번째 데이터에 대해 순방향 버블 정렬이 수행되므로 이동 즉, 이전 k+1 데이터를 양의 순서로 조정합니다. 이 버블링 방법은 첫 번째 k+1 데이터만 버블링하기 때문에 우리는 이를 로컬 버블링이라고 부릅니다.

package sort;

import java.util.Arrays;

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      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]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

위 내용은 Java의 버블 정렬에 대한 간단한 예제 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!