Java 버블 정렬에 대한 자세한 소개(코드 예)

이 기사는 Java 버블 정렬에 대한 자세한 소개(코드 예제)를 제공합니다. 이는 특정 참고 가치가 있으므로 도움이 될 수 있습니다.

1. 소개

정렬 알고리즘 시리즈의 첫 번째 글이므로 몇 마디 더 말씀드리겠습니다.

Sort는 가장 일반적인 알고리즘 중 하나입니다. 이제 많은 프로그래밍 언어에는 Java의 Arrays.sort() 메서드와 같은 일부 정렬 알고리즘이 통합되어 있습니다. 이 메서드를 사용하면 내부 구현 세부 사항을 신경 쓰지 않고 직접 호출할 수 있습니다. 실제 소프트웨어 개발 중에도 자주 사용됩니다. 하지만 개발자의 관점에서 무슨 일이 일어나고 있는지 알려면 그 이유를 알아야 합니다. 더 많은 정렬 알고리즘을 연습하면 일부 정렬 방법의 기본 구현 세부 사항을 알 수 있을 뿐만 아니라 사고력을 연습하고 프로그래밍 능력을 향상시킬 수 있습니다. 이제 많은 기술 인터뷰에는 기본 정렬 알고리즘도 포함되므로 더 많이 연습하는 것이 좋습니다. (추천: Java 동영상 튜토리얼)

글에 포함된 코드는 모두 Java로 구현되어 있지만 Java 언어 기능이 너무 많이 포함되어 있지 않으며, 코드를 이해하고 변환하는 데 도움이 되도록 자세한 설명을 추가하겠습니다. 당신에게 익숙한 프로그래밍 언어.

10가지 일반적인 정렬 알고리즘이 있습니다:

• 버블 정렬, 선택 정렬, 삽입 정렬, 평균 시간 복잡도는 O(n²)
• 힐 정렬, 병합 정렬, 퀵 정렬, 힙 정렬, 평균 시간 복잡도는 O(nlogn)
• 카운팅 정렬, 기수 정렬, 버킷 정렬, 평균 시간 복잡도는 O(n + k)

특정 정렬 알고리즘을 설명하기 전에 먼저 두 가지 개념을 이해해야 합니다.

1. 내부 정렬(In-Place Sorting): 정렬 과정에서 추가 저장 공간을 차지하지 않고 공간 복잡도가 O(1)임을 의미합니다.
2. 정렬 알고리즘의 안정성: 안정적인 정렬은 정렬 후에도 동일한 요소의 순서가 변경되지 않음을 의미합니다. 그렇지 않으면 불안정하다고 합니다. 예를 들어 배열 [3, 5, 1, 4, 9, 6, 6, 12]에는 두 개의 6이 있습니다(구별을 위해 6 중 하나를 굵게 표시했습니다). 정렬하면 다음과 같습니다: [ 1, 3 , 4, 5, 6, 6, 9, 12] (굵은 6이 앞에 있음) 이는 안정적인 정렬 알고리즘임을 나타냅니다.

2. 더 가까이

버블 정렬의 아이디어는 실제로 매우 간단합니다. 한 데이터의 크기를 인접한 데이터와 비교하면 두 데이터가 교환됩니다. 이 작업을 반복하면 데이터를 정렬할 수 있습니다.

예를 들어 배열 a[3,5,1,4,9,6]이 있는 경우 첫 번째 버블링 작업은 아래 그림과 같습니다.

이 작업을 반복하고 6번 버블링합니다. 그러면 데이터 정렬이 완료됩니다.

이 아이디어에 따르면 버블 정렬을 구현하려면 다음 코드를 작성하는 것이 쉬울 것입니다.

public class BubbleSort {

    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

하지만 이 정렬 알고리즘은 버블 작업에서 데이터 교환이 없을 때에도 최적화될 수 있습니다. 더 이상 버블링 작업이 완료되지 않았습니다. 예를 들어 위의 예에서 첫 번째 버블 이후의 데이터는 [3,1,4,5,6,9]이고, 다른 버블 이후의 데이터는 [1,3,4,5,6,9]입니다. ] 현재 정렬이 완료되었으며 루프를 종료할 수 있습니다.

따라서 이 배열을 정렬하려면 위 코드를 완료하는 데 6개의 거품이 필요하며 그 중 4개는 필요하지 않습니다. 따라서 코드를 최적화할 수 있습니다.

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序，返回空
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换，则直接退出循环
            if (!flag) break;
        }
    }
}

자, 버블 정렬의 기본 아이디어와 코드가 구현되었습니다. 마지막으로 요약하자면:

1. 버블 정렬은 데이터 비교를 기반으로 합니다
2. 가장 좋은 경우의 시간 복잡도는 O(n)입니다. ), 최악의 경우 시간 복잡도는 O(n²)이고 평균 시간 복잡도는 O(n²)
3. 버블 정렬은 내부 정렬 알고리즘이며 안정적입니다.

위 내용은 Java 버블 정렬에 대한 자세한 소개(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!