Java 프로그래밍에서 검색 알고리즘과 정렬 알고리즘을 빠르게 마스터하는 방법

1. 검색 알고리즘

이진 알고리즘

이진 검색이라고도 하는 이진 검색은 효율적인 검색 알고리즘입니다. 기본 아이디어는 정렬된 배열(또는 집합)을 둘로 나누는 것입니다. 현재 중간 요소가 대상 요소와 같으면 검색이 성공하고, 현재 중간 요소가 대상 요소보다 크면 왼쪽 절반이 검색됩니다. ; 현재 중간 요소가 다음보다 작은 경우 대상 요소의 경우 오른쪽 절반을 검색합니다. 대상 요소를 찾거나 검색 범위가 비어 검색에 실패할 때까지 위 단계를 반복합니다.

다음은 Java에서 구현된 바이너리 알고리즘입니다.

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

위 메서드는 순서가 지정된 정수 배열 집합과 대상 값을 매개 변수로 사용하고, 대상 값이 그렇지 않은 경우 배열에 있는 대상 값의 인덱스를 반환합니다. 배열에 존재하면 -1을 반환하면 됩니다.

알고리즘의 핵심은 왼쪽과 오른쪽이 특정 조건을 충족할 때 반복적으로 실행되는 while 루프입니다.

• mid가 target과 같으면 mid가 반환되고 알고리즘이 종료됩니다.

• mid가 목표보다 작으면 오른쪽에서 계속 검색합니다. 즉, 왼쪽에서 mid + 1로 설정합니다.

• 루프를 통과할 때마다 mid = left + (right - left) / 2를 사용하여 중간 요소의 인덱스를 계산합니다. (왼쪽 + 오른쪽) / 2 형식이 아닌 왼쪽 + 오른쪽 형식을 사용해야 한다는 점에 유의해야 합니다. 그렇지 않으면 정수 오버플로 문제가 발생할 수 있습니다.

2. 정렬 알고리즘

Java에서 정렬 알고리즘은 Comparable 또는 Comparator 인터페이스를 구현하여 구현됩니다. 다음은 일반적으로 사용되는 몇 가지 정렬 알고리즘과 구현 방법입니다.

버블 정렬

버블 정렬은 간단한 정렬 알고리즘입니다. 아이디어는 인접한 두 요소를 지속적으로 비교하고 순서가 잘못된 경우 위치를 바꾸는 것입니다. 이 과정은 마치 마치 물방울이 계속해서 솟아오르는 것과 같아서 이를 버블정렬이라고 합니다.

public static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                //交换位置
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

선택 정렬

선택 정렬의 개념은 정렬되지 않은 요소 중에서 가장 작은 요소를 선택하여 정렬 마지막에 넣는 것입니다. 가장 작은 요소가 발견될 때마다 현재 정렬되지 않은 첫 번째 요소로 교체됩니다.

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

삽입 정렬

삽입 정렬의 개념은 정렬되지 않은 요소를 적절한 정렬 위치에 삽입하는 것입니다. 정렬되지 않은 요소 중 하나를 선택하고 정렬된 요소를 뒤에서 앞으로 순회합니다. 정렬된 요소보다 작은 경우 한 위치 뒤로 이동하여 정렬되지 않은 요소보다 작은 위치를 찾을 때까지 계속 비교한 다음 삽입합니다. 이 위치.

public static void insertionSort(int[] arr) {
    int preIndex, current;
    for (int i = 1; i < arr.length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

퀵 정렬

퀵 정렬은 분할 정복 개념을 기반으로 한 정렬 알고리즘입니다. 피벗점을 선택하고 배열을 피벗점보다 작거나 같고 피벗점보다 큰 두 개의 하위 배열로 분할한 다음 두 하위 배열을 재귀적으로 정렬합니다.

아아아아

위 내용은 Java 프로그래밍에서 검색 알고리즘과 정렬 알고리즘을 빠르게 마스터하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!