데이터 구조 와 알고리즘 분석의 거품 정렬 알고리즘 과 효율 분석

컴퓨터 과학 에서 정렬 은 영원히 고전적 인 주제 이다.
1. 거품 정렬 이란 무엇 인가
거품 정렬 알고리즘 은 정렬 대기 배열 을 여러 번 옮 겨 다 녀 야 하 며, 매번 옮 겨 다 닐 때마다 인접 한 요 소 를 비교 해 야 합 니 다.만약 한 쌍 의 원소 가 내림차 순 이 라면 서로 그들의 위 치 를 교환한다.그렇지 않 으 면 변 하지 않 는 다.작은 값 이 '기포' 처럼 점점 위로 떠 오 르 고 큰 값 이 바닥 으로 가 라 앉 기 때문에 이런 기술 을 거품 정렬 이나 침하 정렬 이 라 고 부른다.
2. 거품 정렬 알고리즘

for (int i = 1; i < list.length; i++) {
    for (int j = 0; j < list.length-i; j++) {
    if (list[j]>list[j+1]) {
       int temp  = list[j];
       list[j] = list[j+1];
       list[j+1] = temp;
    }
}

3. 거품 정렬 과정 분석
 정렬 전 배열 은 int [] list = {1, 3, 5, 4, 9, 6, 7, 2};
 정렬 과정:

 1     
1  3  5  4  9  6  7  2  
1  3  5  4  9  6  7  2  
1  3  4  5  9  6  7  2  
1  3  4  5  9  6  7  2  
1  3  4  5  6  9  7  2  
1  3  4  5  6  7  9  2  
1  3  4  5  6  7  2  9  
 1     
13456729
 2     
1  3  4  5  6  7  2  9  
1  3  4  5  6  7  2  9  
1  3  4  5  6  7  2  9  
1  3  4  5  6  7  2  9  
1  3  4  5  6  7  2  9  
1  3  4  5  6  2  7  9  
 2     
13456279
 3     
1  3  4  5  6  2  7  9  
1  3  4  5  6  2  7  9  
1  3  4  5  6  2  7  9  
1  3  4  5  6  2  7  9  
1  3  4  5  2  6  7  9  
 3     
13452679
 4     
1  3  4  5  2  6  7  9  
1  3  4  5  2  6  7  9  
1  3  4  5  2  6  7  9  
1  3  4  2  5  6  7  9  
 4     
13425679
 5     
1  3  4  2  5  6  7  9  
1  3  4  2  5  6  7  9  
1  3  2  4  5  6  7  9  
 5     
13245679
 6     
1  3  2  4  5  6  7  9  
1  2  3  4  5  6  7  9  
 6     
12345679
 7     
1  2  3  4  5  6  7  9  
 7     
12345679
    ：
1 2 3 4 5 6 7 9 

4. 정렬 효율 분석
n 개의 요소 가 설치 되 어 있 습 니 다. 첫 번 째 는 n - 1 번 을 비교 해 야 하고 두 번 째 는 n - 2 번 이 필요 합 니 다. 마지막 으로 한 번 만 비교 해 야 합 니 다.그래서 효율 은 (n - 1) + (n - 2)... + 1 = (n - 1) n / 2 = O (n 제곱) 이다.
5. 알고리즘 부족 및 개선
거품 정렬 알고리즘 을 실 현 했 지만 흠 이 있 습 니 다.
예 를 들 어 한 조 의 배열 은 처음에 이미 순 서 를 정 했다.  하나, 둘, 셋, 넷, 다섯.두 번 째 는 옮 겨 다 니 며 끝 날 때 까지 옮 겨 다 닌 다.이렇게 하면 시간 을 낭비 할 것 이다.
이제 최 적 화 된 거품 정렬 알고리즘 을 소개 합 니 다.

   boolean needNextPass = true;//                
      for (int i = 1; i < list.length && needNextPass; i++) {
      needNextPass = false;
      for (int j = 0; j < list.length-i; j++) {
      if (list[j]>list[j+1]) 
        {
         int temp  = list[j];
	 list[j] = list[j+1];
	 list[j+1] = temp;
	 needNextPass = true;
	}
 }

변동 이 그리 크 지 는 않 지만 가뜩 이나 순서 가 정 해 져 있 는 상황 에 부 딪 히 면 옮 겨 다 니 는 횟수 를 줄 여 효율 을 높 인 다.예 를 들 어 {1, 2, 3, 4, 5} 을 정렬 할 때 최 적 화 된 알고리즘 은 한 번 만 옮 겨 다 니 면 된다.