Java 정렬 알고리즘 요약 거품 정렬

2322 단어 Java거품 정렬
본고는 자바 정렬 알고리즘의 총괄적인 거품 정렬을 실례로 다루고 있다.여러분에게 참고할 수 있도록 나누어 드리겠습니다.구체적인 분석은 다음과 같다.
선언: 거품 정렬(Bubble Sort)은 서로 인접한 두 개의 수를 순서대로 앞에 놓고 큰 수를 뒤에 놓는다.
다음은 거품이 자바에 정렬된 알고리즘의 실현을 살펴본다.
거품 정렬은 컴퓨터의 일종의 정렬 방법으로 시간 복잡도는 O(n^2)이다. 비록 무더기 정렬, 빠른 정렬의 O(nlogn, 밑수 2)에는 미치지 못하지만 두 가지 장점이 있다.
1.'프로그래밍 복잡도'가 낮아 코드를 쓰기 쉽다.
2. 안정성을 가진다. 이곳의 안정성은 원래 서열에서 같은 원소의 상대적인 순서가 정렬 후의 서열로 유지되고 무더기 정렬, 빠른 정렬은 모두 안정성을 가지지 않는다는 것을 말한다.
그러나 1차원, 2차원 병합 정렬, 불균형 2차원 트리 정렬의 속도는 거품 정렬보다 빠르고 안정성을 가지지만 속도가 무더기 정렬에 미치지 못한다.
빠른 정렬.거품 정렬은 n-1번 서브 정렬을 거쳐 완성된 것으로 i번 서브 정렬은 첫 번째 수에서 n-i 개 수로, 만약에 i번 서브 정렬이 다음 수보다 크면
(오름차순, 작은 내림차순) 은 두 수를 교환한다.
거품 정렬 알고리즘이 안정적이고 O(1)의 추가 공간, 비교와 교환의 시간 복잡도는 모두 O(n^2)이다. 스스로 적응하고 이미 기본 정렬된 알고리즘에 대해 시간 복잡도는 O(n)이다.거품 알고리즘의 많은 성질은 삽입 알고리즘과 비슷하지만 시스템에 대한 비용은 조금 높다.
정렬 프로세스
정렬된 그룹 R을 상상합니다 [1...N]수직으로 세워 각 데이터 요소를 무게가 있는 기포로 간주하고 가벼운 기포가 중기포 아래에 있을 수 없다는 원칙에 따라 아래에서 위로 수조 R를 스캐닝한다. 본 원칙에 위반되는 경기포를 스캐닝하면 위로'떠다니게 한다. 이렇게 반복적으로 진행한다. 마지막에 어떤 두 기포가 모두 가벼운 사람이 위에 있고 무거운 사람이 아래에 있을 때까지.
코드 구현:

//     
public class BubbleSort{
  public static void sort(Comparable[] data){
    //   
    int len = data.length; 
    for (int i = 0; i < len - 1; i++){
      //   
      Comparable temp = null; 
      //  ,false  
      boolean isExchanged = false; 
      for (int j = len - 1; j > i; j--){
        //  data[j] data[j - 1],  
        if (data[j].compareTo(data[j - 1]) < 0){
          temp = data[j]; 
          data[j] = data[j - 1]; 
          data[j - 1] = temp; 
          //  ,  
          isExchanged = true; 
        }// end if 
      }// end for 
      //  , ,  
      if (!isExchanged){
        return; 
      }// end if 
    }// end for 
  }// end sort 
  public static void main(String[] args){
    //  JDK1.5 , 
    // int,double Comparable 
    Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
    sort(c);
    for (Comparable data : c){
      System.out.println(data);
    }
  }
}

거품 정렬법으로 n개의 데이터를 정렬하려면 모두 n-1번의 비교가 필요하다.원래 순서가 있는 데이터라면 n-1회 비교도 필요하다.거품 정렬법의 알고리즘은 매우 간단하고 효율도 비교적 떨어진다.
본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다.

좋은 웹페이지 즐겨찾기