Java를 사용하여 버블 정렬 알고리즘 구현

버블 정렬의 알고리즘 분석 및 개선

교환 정렬의 기본 아이디어는 정렬할 레코드의 키워드를 쌍으로 비교하여 두 레코드의 순서가 일치함을 알면 반대로, 레코드에 역순이 없을 때까지 교환이 수행됩니다.
교환 정렬의 기본 개념을 적용한 주요 정렬 방법으로는 버블 정렬과 퀵 정렬이 있습니다.

public class BubbleSort implements SortUtil.Sort{ 
public void sort(int[] data) { 
int temp; 
for(int i=0;i<data.length;i++){ 
for(int j=data.length-1;j>i;j--){ 
if(data[j]<data[j-1]){ 
SortUtil.swap(data,j,j-1); 
} 
} 
} 
}

버블 정렬

1. 정렬 방법

정렬된 레코드 배열 R[1..n]을 세로로 배열하고, 각 레코드 R을 보면 가중치가 R.key인 버블입니다. 가벼운 기포는 무거운 기포 아래에 있을 수 없다는 원리에 따라 배열 R은 아래에서 위로 스캔됩니다. 이 원리를 위반하는 가벼운 기포는 위쪽으로 "부유"됩니다. 마지막 두 개의 거품이 위쪽의 더 가벼운 거품이고 아래쪽의 더 무거운 거품이 될 때까지 이 과정이 반복됩니다.

(1) 초기

R[1..n]은 순서가 없는 영역입니다.

(2) 첫 번째 스캔

무질서한 부분의 바닥에서 위쪽으로 인접한 두 개의 거품의 무게를 비교하면 더 가벼운 것이 바닥에 있고 더 무거운 것이 발견됩니다. 가 맨 위에 있으면 두 사람의 위치를 ​​바꿉니다. 즉, (R[n], R[n-1]), (R[n-1], R[n-2]),..., (R[2], R[1])을 비교합니다. 각 쌍 Bubble(R[j+1], R[j])에 대해 시퀀스, R[j+1].key첫 번째 스캔이 완료되면 "가장 가벼운" 버블이 간격의 상단으로 떠오릅니다. 즉, 가장 작은 키워드가 포함된 레코드가 가장 높은 위치 R[1]에 배치됩니다.

(3) 두 번째 스캔

은 R[2..n]을 스캔합니다. 스캔이 완료되면 "두 번째로 가벼운" 버블이 R[2] 위치로 떠오릅니다...
마지막으로 n-1 스캔 후 정렬된 영역 R[1..n]을 얻을 수 있습니다
참고: 아니요. i 스캔 중에 R[1..i-1] 및 R[i..n]은 각각 현재 정렬된 영역과 정렬되지 않은 영역입니다. 스캔은 여전히 ​​무질서한 영역의 바닥에서 영역의 상단까지 진행됩니다. 스캔이 완료되면 해당 영역에서 가장 가벼운 버블이 상단 위치 R로 떠오릅니다. 결과적으로 R[1..i]는 새로운 정렬된 영역이 됩니다.

2. 버블 정렬 과정의 예

키워드 순서로 파일을 버블 정렬하는 과정

3. >

특정 분류 패스에서 버블 위치의 교환이 발견되지 않으면 분류할 무질서한 영역의 모든 버블이 위쪽에 있는 거품과 아래쪽에 있는 무거운 거품의 원리를 충족한다는 의미입니다. 버블 정렬 프로세스는 여기에서 수행할 수 있습니다. 정렬 후 종료하세요. 이를 위해 아래 알고리즘에서는 부울 교환이 도입되었으며 각 정렬이 시작되기 전에 FALSE로 설정됩니다. 정렬 중에 교환이 발생하면 TRUE로 설정됩니다. 교환은 각 정렬 패스가 ​​끝날 때 확인됩니다. 교환이 발생하지 않으면 알고리즘이 종료되고 다음 정렬 패스가 ​​수행되지 않습니다.

아아아

（1）算法的最好时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
Cmin=n-1
Mmin=0。
冒泡排序最好的时间复杂度为O(n)。
（2）算法的最坏时间复杂度
若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax=n(n-1)/2=O(n2)
Mmax=3n(n-1)/2=O(n2)
冒泡排序的最坏时间复杂度为O(n2)。
（3）算法的平均时间复杂度为O(n2)
虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。
（4）算法稳定性
冒泡排序是就地排序，且它是稳定的。
5、算法改进
上述的冒泡排序还可做如下的改进：
(1)记住最后一次交换发生位置lastExchange的冒泡排序
在每趟扫描中，记住最后一次交换发生的位置lastExchange，（该位置之前的相邻记录均已有序）。下一趟排序开始时，R[1..lastExchange-1]是有序区，R[lastExchange..n]是无序区。这样，一趟排序可能使当前有序区扩充多个记录，从而减少排序的趟数。具体算法【参见习题】。
(2) 改变扫描方向的冒泡排序
①冒泡排序的不对称性
能一趟扫描完成排序的情况：
只有最轻的气泡位于R[n]的位置，其余的气泡均已排好序，那么也只需一趟扫描就可以完成排序。
【例】对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描。
需要n-1趟扫描完成排序情况：
当只有最重的气泡位于R[1]的位置，其余的气泡均已排好序时，则仍需做n-1趟扫描才能完成排序。
【例】对初始关键字序列：94，10，12，18，42，44，45，67就需七趟扫描。
②造成不对称性的原因
每趟扫描仅能使最重气泡"下沉"一个位置，因此使位于顶端的最重气泡下沉到底部时，需做n-1趟扫描。
③改进不对称性的方法
在排序过程中交替改变扫描方向，可改进不对称性。
JAVA代码：

package Utils.Sort;

/**
*@author Linyco
*利用冒泡排序法对数组排序，数组中元素必须实现了Comparable接口。
*/
public class BubbleSort implements SortStrategy
{
       /**
       *对数组obj中的元素以冒泡排序算法进行排序
       */
       public void sort(Comparable[] obj)
       {
              if (obj == null)
              {
                     throw new NullPointerException("The argument can not be null!");
              }

              Comparable tmp;

              for (int i = 0 ;i < obj.length ;i++ )
              {
                     //切记，每次都要从第一个开始比。最后的不用再比。
                     for (int j = 0 ;j < obj.length - i - 1 ;j++ )
                     {
                            //对邻接的元素进行比较，如果后面的小，就交换
                            if (obj[j].compareTo(obj[j + 1]) > 0)
                            {
                                   tmp = obj[j];
                                   obj[j] = obj[j + 1];
                                   obj[j + 1] = tmp;
                            }
                     }
              }
       }
}

更多用java实现冒泡排序算法相关文章请关注PHP中文网！