거품 정렬 (1)

거품 정렬
거품 정렬 (Bubble Sort) 은 컴퓨터 과학 분야 의 비교적 간단 한 정렬 알고리즘 이다.이 는 정렬 할 요소 열 을 반복 적 으로 방문 하여 서로 인접 한 두 요 소 를 순서대로 비교 한 적 이 있다. 만약 그들의 순서 (예 를 들 어 크 고 작은 것, 이니셜 이 A 에서 Z 까지) 가 잘못 되면 그들 을 교환 할 것 이다.방문 요 소 는 인접 요소 가 교환 되 지 않 을 때 까지 반복 적 으로 진행 되 는 것 이다. 즉, 이 요 소 는 정렬 이 완료 되 었 다 는 것 이다.이 알고리즘 의 이름 유래 는 큰 원소 가 교환 을 통 해 서서히 수열 의 꼭대기 (오름차 순 또는 내림차 순 배열) 로 떠 오 르 기 때문이다. 탄산 음료 에서 이산화탄소 의 기포 가 결국 꼭대기 까지 떠 오 르 는 것 처럼 '거품 서열' 이 라 고 불 린 다.
알고리즘 원리
거품 정렬 알고리즘 의 원 리 는 다음 과 같다. 비교적 인접 한 원소 이다.첫 번 째 가 두 번 째 보다 크 면 두 사람 을 교환 하 세 요.모든 인접 요소 에 대해 똑 같은 일 을 하고 첫 번 째 쌍 부터 마지막 쌍 까지 한다.이 점 에서 마지막 요 소 는 가장 큰 숫자 일 것 이다.모든 요소 에 대해 마지막 을 제외 하고 이상 의 절 차 를 반복 합 니 다.한 쌍 의 숫자 도 비교 할 필요 가 없 을 때 까지 점점 적어 지 는 요소 에 대해 위의 절 차 를 반복 합 니 다.
알고리즘 분석
시간 복잡 도
파일 의 초기 상태 가 정상 이면 한 번 스 캔 하면 정렬 이 완 료 됩 니 다.필요 한 키워드 비교 횟수 와 기록 이동 횟수 모두 최소 치:...따라서 거품 정렬 의 가장 좋 은 시간 복잡 도 는?초기 파일 이 역순 이 라면 정렬 을 해 야 합 니 다.매번 정렬 은 차 키워드 의 비교 (1 ≤ i ≤ n - 1) 를 진행 하고 매번 비교 할 때마다 기록 을 세 번 이동 하여 교환 기록 위치 에 도달 해 야 합 니 다.이러한 상황 에서 비교 와 이동 횟수 가 모두 최대 치 에 달 합 니 다.
거품 정렬 의 최 악의 시간 복잡 도 는?종합 적 으로 거품 서열 의 평균 시간 복잡 도 는?
알고리즘 안정성
거품 정렬 은 작은 원 소 를 앞으로 조절 하거나 큰 원 소 를 뒤로 조절 하 는 것 이다.비 교 는 인접 한 두 원소 의 비교 이 고 교환 도 이 두 원소 사이 에서 발생 한다.따라서 두 원소 가 같다 면 다시 교환 하지 않 을 것 이다.만약 에 두 개의 똑 같은 요소 가 서로 인접 하지 않 으 면 앞의 두 개의 교환 을 통 해 두 개 를 인접 하 더 라 도 이때 교환 하지 않 기 때문에 같은 요소 의 앞 뒤 순 서 는 변 하지 않 았 기 때문에 거품 정렬 은 안정 적 인 정렬 알고리즘 이다.
알고리즘 설명

public class P4_1 {
	static final int SIZE = 10;
	/**
	 *            
	 * @param a
	 */
    public static void bubbleSort(int[] a){
    	int temp;
    	for(int i=1;ia[j+1]){
    				//       
    				temp=a[j];
    				a[j]=a[j+1];
    				a[j+1]=temp;
    			}
    		}
    		 System.out.print(" "+i+"     :");			//         
       	  for(int k=0;k