Java에서 삽입 정렬 알고리즘을 작성하는 방법 및 원리

삽입 정렬 알고리즘의 단계와 아이디어

삽입 정렬은 정렬할 요소를 정렬된 순서의 적절한 위치에 삽입하는 것이 기본 아이디어입니다.

구체적인 단계는 다음과 같습니다.

1. 먼저 배열을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나눕니다. 처음에는 정렬된 부분에 배열의 첫 번째 요소인 단 하나의 요소만 있습니다.
2. 정렬되지 않은 부분의 요소를 차례로 꺼내어 정렬된 부분의 요소들과 하나씩 비교하여 삽입할 적절한 위치를 찾습니다.
3. 비교 과정에서 삽입된 요소를 위한 공간을 확보하기 위해 정렬된 부분의 요소를 뒤로 이동합니다.
4. 마지막으로 정렬되지 않은 부분의 모든 요소를 ​​정렬된 부분의 적절한 위치에 삽입하면 정렬이 완료됩니다.

다음은 Java 언어로 삽입 정렬 알고리즘을 작성하기 위한 샘플 코드입니다.

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; 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;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        System.out.println("原数组：");
        printArray(arr);
        insertionSort(arr);
        System.out.println("排序后的数组：");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

이 코드 예제에서는 정수 배열을 매개 변수로 받아들이고 다음을 수행하는 insertionSort 메서드를 정의합니다. 배열의 함수 삽입 정렬을 수행합니다. n을 사용하여 배열의 길이를 나타내고 for를 사용하여 정렬되지 않은 부분의 요소를 반복합니다. 각 순회에서 현재 요소 arr[i]를 key 변수에 저장한 다음 정렬된 부분을 앞으로 순회하여 키를 삽입할 적절한 위치를 찾습니다. . 비교 프로세스 중에 키를 위한 공간을 확보하기 위해 더 큰 요소를 한 위치 뒤로 이동합니다. 마지막으로 키를 올바른 위치에 삽입하면 정렬이 완료됩니다. insertionSort方法，它接受一个整数数组作为参数，并对数组进行插入排序。我们用n表示数组的长度，并使用for循环遍历未排序部分的元素。在每一次遍历中，我们将当前元素arr[i]保存到key变量中，然后向前遍历已排序部分，找到合适的位置插入key。在比较的过程中，我们将较大的元素往后移动一位，为key腾出位置。最后，我们将key插入到正确的位置上，排序完成。

在main方法中，我们初始化一个整数数组arr，并调用insertionSort方法对数组进行排序。最后，我们调用printArray

main 메서드에서 정수 배열 arr을 초기화하고 insertionSort 메서드를 호출하여 배열을 정렬합니다. 마지막으로 printArray 메서드를 호출하여 정렬된 배열을 인쇄합니다.

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

原数组：
5 2 8 1 9 3 
排序后的数组：
1 2 3 5 8 9 

삽입 정렬 알고리즘의 시간 복잡도는 O(n^2)입니다. 여기서 n은 배열의 길이입니다. 삽입 정렬 알고리즘은 시간 복잡도가 높지만 구현이 간단하고 소규모 배열 정렬에 적합합니다. 동시에 실제 응용에서 삽입 정렬 알고리즘은 안정성이라는 특성도 가지고 있습니다. 🎜

위 내용은 Java에서 삽입 정렬 알고리즘을 작성하는 방법 및 원리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!