> Java > java지도 시간 > 삽입 정렬 알고리즘 이해(Java 예제 포함)

삽입 정렬 알고리즘 이해(Java 예제 포함)

Patricia Arquette
풀어 주다: 2025-01-18 02:16:13
원래의
593명이 탐색했습니다.

삽입 정렬은 반복 정렬 알고리즘입니다. 정렬되지 않은 각 요소를 정렬된 하위 배열 내의 올바른 위치에 삽입하여 한 번에 한 요소씩 정렬된 하위 배열을 만듭니다. 카드 패를 정렬하는 것을 생각해 보세요. 정렬된 카드 하나로 시작한 다음 각 후속 카드를 이미 정렬된 카드 중 적절한 위치에 삽입합니다.

삽입 정렬 작동 방식

오름차순으로 정렬하려는 배열의 예를 들어 설명하겠습니다.

Understanding Insertion Sort Algorithm (with Examples in Java)

첫 번째 반복:

이미 정렬된 첫 번째 요소를 고려합니다. 알고리즘은 두 번째 요소로 시작됩니다.

Understanding Insertion Sort Algorithm (with Examples in Java)

2 < 이후 2를 8과 비교합니다. 8, 8을 오른쪽으로 이동하고 왼쪽에 2를 삽입합니다.

Understanding Insertion Sort Algorithm (with Examples in Java)

두 번째 반복:

6을 정렬된 하위 배열(2, 8)과 비교합니다. 6 < 8이므로 오른쪽으로 8교대합니다. 그러면 6 > 2, 6은 2의 오른쪽에 배치됩니다.

Understanding Insertion Sort Algorithm (with Examples in Java)

이 프로세스는 전체 배열이 정렬될 때까지 계속됩니다.

Understanding Insertion Sort Algorithm (with Examples in Java) Understanding Insertion Sort Algorithm (with Examples in Java) Understanding Insertion Sort Algorithm (with Examples in Java)

Java로 구현

<code class="language-java">import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}</code>
로그인 후 복사

코드는 각 요소를 key으로 사용하여 반복됩니다. 그런 다음 key를 정렬된 부분의 요소와 비교하여 key의 올바른 위치를 찾을 때까지 더 큰 요소를 오른쪽으로 이동합니다.

예를 들어 두 번째 반복(i=2)에서는 다음과 같습니다.

Understanding Insertion Sort Algorithm (with Examples in Java)

key은 6입니다. while 루프는 올바른 위치를 찾을 때까지 요소를 이동합니다.

Understanding Insertion Sort Algorithm (with Examples in Java) Understanding Insertion Sort Algorithm (with Examples in Java)

마지막으로 6이 삽입됩니다.

Understanding Insertion Sort Algorithm (with Examples in Java)

출력:

정렬되지 않은 배열: [8, 2, 6, 4, 9, 1] 정렬된 배열: [1, 2, 4, 6, 8, 9]

복잡성 분석

  • 시간 복잡도:
    • 최상의 경우(O(n)): 이미 정렬된 배열입니다.
    • 평균 사례(O(n²)): 무작위로 배열된 요소
    • 최악의 경우(O(n²)): 역정렬된 배열.
  • 공간 복잡도: O(1)(내부 알고리즘)

결론

삽입 정렬은 2차 시간 복잡도로 인해 대규모 데이터세트에는 비효율적입니다. 그러나 이는 간단한 알고리즘이며 작은 데이터세트나 거의 정렬된 데이터에서 잘 작동합니다.

위 내용은 삽입 정렬 알고리즘 이해(Java 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿