> 백엔드 개발 > C++ > 본문

분할 정복 알고리즘에 C++ 재귀 함수를 적용합니까?

WBOY
풀어 주다: 2024-04-19 13:21:02
원래의
451명이 탐색했습니다.

분할 정복 알고리즘은 큰 문제를 더 작은 하위 문제로 분해합니다. C++ 재귀 함수는 분할 정복 알고리즘을 구현할 수 있습니다. 기본 요소를 선택하고 기본 요소의 두 측면으로 분할합니다. 두 부분, 정렬된 부분을 병합합니다.

C++ 递归函数在分治算法中的应用?

C++ 분할 정복 알고리즘에 재귀 함수 적용

분할 정복 알고리즘은 큰 문제를 더 작은 하위 문제로 분해한 다음 하위 문제를 재귀적으로 해결하는 전략입니다. C++의 재귀 함수는 이해하고 디버깅하기 쉬운 코드를 작성할 수 있으므로 분할 정복 알고리즘을 구현하는 데 이상적입니다.

빠른 정렬 사례 연구

빠른 정렬은 가장 인기 있는 분할 정복 알고리즘 중 하나입니다. 다음 단계에 따라 순서가 지정되지 않은 배열을 정렬합니다.

  1. 기본 요소를 선택합니다.
  2. 배열의 요소를 두 부분, 즉 기본 요소보다 작은 요소와 기본 요소보다 큰 요소로 나눕니다.
  3. 이 두 부분을 재귀적으로 정렬하세요.
  4. 정렬된 두 부분을 다시 원래 배열로 병합하세요.

다음은 C++에서 빠른 정렬 기능을 구현한 예입니다.

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);  // 获取分区索引
        
        // 递归地排序两部分
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // 指向最终小于基准的元素的索引
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
로그인 후 복사

이 빠른 정렬 기능을 사용하면 다음과 같이 배열을 정렬할 수 있습니다.

int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
로그인 후 복사

위 내용은 분할 정복 알고리즘에 C++ 재귀 함수를 적용합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

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