[JAVA] 거품 서열 이 뭐야? -면접 가산 점 문제

거품 정렬 은 컴퓨터 과학 분야 의 비교적 간단 한 정렬 알고리즘 으로 유심 한 사람 이 코드 를 계속 최적화 하고 개량 하 며 본인 은 일부 코드 를 발췌 하여 학습 합 니 다.
글 은 중국 에서 기원 되 었 고 프로그래머 재 에서 전재 되 었 다.만화: 거품 서열 이란 무엇 인가?
 
거품 정렬 1 판

public class BubbleSort {

private static void sort(int array[])

{

    int tmp  = 0;



for(int i = 0; i < array.length; i++){

        for(int j = 0; j < array.length - i - 1; j++)

        {

            if(array[j] > array[j+1])

            {

                tmp = array[j];

                array[j] = array[j+1];

                array[j+1] = tmp;

            }

        }

    }

}

public static void main(String[] args){

    int[] array = new int[]{5,8,6,3,9,2,1,7};

    sort(array);

    System.out.println(Arrays.toString(array));

}

}

 
두 순환 으로 정렬 합 니 다.외부 순환 은 모든 라 운 드 를 제어 하고 내부 순환 은 모든 라운드 의 거품 처 리 를 대표 하 며 먼저 요 소 를 비교 한 다음 에 요소 교환 을 한다.
 
문제: 꼴찌 3 라운드 때 는 이미 순서 가 있 으 니 더 이상 정렬 할 필요 가 없습니다!
 
거품 정렬 2 판

public class BubbleSort {
private static void sort(int array[])
{
    int tmp  = 0;
    for(int i = 0; i < array.length; i++)
    {
        //    ，       true
        boolean isSorted = true;
        for(int j = 0; j < array.length - i - 1; j++)
        {
            if(array[j] > array[j+1])
            {
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                //     ，      ，    false
                isSorted = false;
            }
       }
        if(isSorted){
            break;
        }
    }
}
public static void main(String[] args){
    int[] array = new int[]{5,8,6,3,9,2,1,7};
    sort(array);
    System.out.println(Arrays.toString(array));
}
}

이 코드 는 불 변수 isSorted 를 사용 하여 작은 변경 을 했 습 니 다.이 라운드 정렬 에서 요소 가 교환 되면 수열 이 무질서 하 다 는 것 을 설명 합 니 다.원소 교환 이 없 으 면 수열 이 이미 질서 가 있다 는 것 을 설명 하고, 바로 큰 순환 에서 튀 어 나온다.
 
문제: 만약 후반 부 원소 가 이미 질서 가 있다 면 매 라운드 마다 헛되이 비교 해 야 한다.
 
거품 정렬 3 판
매 라운드 정렬 의 마지막 에 마지막 요소 교환 위 치 를 기록 합 니 다. 그 위 치 는 바로 무질서 수열 의 경계 이 고 그 다음은 질서 있 는 구역 입 니 다.
이 코드 에서 sortBorder 는 무질서 한 수열 의 경계 입 니 다.매 라운드 정렬 과정 에서 sortBorder 이후 의 요 소 는 비교 할 필요 가 없고 질서 가 있 을 것 입 니 다.
 

public class BubbleSort {
private static void sort(int array[])
{
    int tmp  = 0;
    //           
    int lastExchangeIndex = 0;
    //       ，             
    int sortBorder = array.length - 1;
    for(int i = 0; i < array.length; i++)
    {
        //    ，       true
        boolean isSorted = true;
        for(int j = 0; j < sortBorder; j++)
        {
            if(array[j] > array[j+1])
            {
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                //     ，      ，    false
                isSorted = false;
                //                      
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if(isSorted){
            break;
        }
    }
}

public static void main(String[] args){
    int[] array = new int[]{3,4,2,1,5,6,7,8};
    sort(array);
    System.out.println(Arrays.toString(array));
}
}