알고리즘 분석 - 분할 전략

1 분 치 전략 개념
분 치 법 은 복잡 한 문 제 를 두 개 이상 의 똑 같 거나 비슷 한 문제 로 나 누 는 것 을 말한다. 이런 서브 문 제 는 서로 독립 되 거나 형식 이 같 으 면 서브 문 제 를 더욱 작은 서브 문제 로 분해 하고 이렇게 순환 해 나 간다. 마지막 에 서브 문 제 는 간단하게 직접 해결 할 수 있 고 원래 의 문 제 는 바로 서브 문 제 를 합 친 것 이다.
예 1.
순서 표를 정 하고 최대 값 과 최소 값 을 구 하 는 분할 알고리즘 을 작성 합 니 다.
분석: 만약 에 우리 의 데이터 가 순서대로 하나의 정형 배열 에 저장 된다 고 가정 하면 배열 의 크기 가 1 이면 결 과 를 직접 제시 할 수 있 습 니 다. 만약 에 크기 가 2 라면 한 번 비교 하면 결 과 를 제시 할 수 있 습 니 다. 만약 에 문 제 를 해결 하 는 배열 의 길이 가 2 보다 크 면 우 리 는 문제 의 규 모 를 줄 이 고 문제 가 해결 할 수 있 을 때 까지 축소 할 수 있 습 니 다. 그래서 분리 전략 알고리즘 은 다음 과 같 습 니 다.

#include "pch.h"
#include 
using namespace std;
//s            ，e      ，meter      ，max，min               
void partionGet(int s, int e, int *meter, int *max, int *min)
{
	if (e - s <= 1)
	{
		if (meter[s] > meter[e])
		{
			if (meter[s] > *max)
				*max = meter[s];
			if (meter[e] < *min)
				*min = meter[e];
		}
		else
		{
			if (meter[e] > *max)
				*max = meter[e];
			if (meter[s] < *min)
				*min = meter[s];
		}
		return;
	}
	int i = s+(e-s) / 2;
	partionGet(s, i, meter, max, min);//         
	partionGet(i+1, e, meter, max, min);

}
int main()
{
	int max=0, min=0;
	int arr[10] = { 1,2,3,4,5,6,7,8,9,0 };
	partionGet(0, 9, arr, &max, &min);
	cout << max << " " << min << endl;
	return 0;
}

질문
예 1, 2
병합 정렬, 쉽게 말 하면 병합 정렬 은 바로 분할 전략 을 이용 한 것 입 니 다. 건물 주 는 병합 정렬 재 귀 알고리즘 과 비 재 귀 알고리즘 에 대한 실현 을 전문 적 으로 쓴 적 이 있 습 니 다. 여기 서 중복 적 으로 쓰 지 않 습 니 다. 연결 을 클릭 하 십시오.
https://mp.csdn.net/postedit/83180119
예 1.
빠 른 정렬 은 분할 정책 을 바탕 으로 정렬 하 는 알고리즘 이다.그 기본 사상 은 주어진 정렬 대기 서열 a [p: r] 에 대해 다음 과 같은 절차 에 따라 진행 하 는 것 이다.
(1) 분해, a [p] 를 기준 으로 배열 a [p: r] 를 3 단 a [p: q - 1], a [q] 와 a [q + 1: r] 로 나 누 어 a [p: q - 1] 중의 모든 요 소 를 a [q] 보다 작 게 하고 a [q + 1: r] 중의 모든 요 소 는 a [q] 보다 크다. 아래 표 q 는 구분 과정 에서 확정 된다.
(2) 재 귀 구 해 는 재 귀 호출 빠 른 정렬 알고리즘 을 통 해 a [p: q - 1] 와 a [q + 1: r] 를 정렬 합 니 다.
(3) 합병, a [p: q - 1] 과 a [q + 1: r] 의 순 서 는 현지에서 진행 되 기 때문에 a [p: q - 1] 와 a [q + 1: r] 가 모두 순 서 를 정 한 후에 어떠한 계산 도 할 필요 가 없습니다. a [p: r] 는 이미 순 서 를 정 했 습 니 다.
이 사상 을 바탕 으로 빠 른 정렬 알고리즘 을 실현 할 수 있 습 니 다.

void quickSort(int arr[], int left, int right)
{// arr      ，         
	if (left < right)//              
	{
		int pivotpos = Partition(arr, left, right, right - left + 1);//    
		quickSort(arr, left, pivotpos);//      
		quickSort(arr, pivotpos + 1, right);//      
	}

n 개의 요 소 를 포함 하 는 배열 arr [0: n] 에 대해 빠 른 정렬 을 하려 면 quickSort (arr, 0, n) 를 호출 하면 됩 니 다.
알고리즘 에서 Partition 은 확 정 된 기준 요소 인 arr [p] 로 하위 배열 arr [p: r] 를 구분 합 니 다.

int Partition(int arr[], int low, int high, int num)
{
	int i = low, j = high, pivot = arr[low];//    
	while (i < j)
	{
		while (i < j&&arr[j] >= pivot)//    ，           ，    
			j--;
		if (i < j)
		{
			arr[i] = arr[j];
			i++;
		}
		while (i < j&&arr[i] < pivot)//        ，    
			i++;
		if (i < j)
		{
			arr[j] = arr[i];
			j--;
		}
	}
	arr[i] = pivot;//       
	return i;
}

미완이다