기본 알고리즘 - 빠 른 정렬 (C 언어 버 전)

기본 알고리즘 - 빠 른 정렬 (C 언어 버 전)

빠 른 정렬 기본 사상 - 분 치 는 어떻게 무질서 한 서열 을 질서 있 게 배열 합 니까?우 리 는 문 제 를 두 가지 로 나 눌 수 있다. 특정한 수 k 보다 큰 부분 에 대해 정렬 하고 k 보다 작은 부분 에 대해 정렬 할 수 있다.두 부분 을 다 배열 한 후에 전체 서열 의 순 서 를 실현 했다.분명히 이것 은 재 귀적 으로 해결 해 야 할 문제 이다.그렇다면 가장 중요 한 것 은 어떻게 서열 을 어떤 수로 경계 점 을 두 부분 으로 나 누 느 냐 하 는 것 이다.먼저 하나의 수 를 분계 점 으로 마음대로 찾 은 다음 에 두 개의 지침 을 사용 하여 각각 서열 좌우 양쪽 에서 스 캔 을 하고 스 캔 하 는 과정 에서 교환 할 수 있 으 며 두 지침 이 만 났 을 때 배열 은 두 부분 으로 나 뉜 다.이 과정 에서 기준 치 는 반드시 정격 치 입 니 다!!

기본 절차 (1) 기준 수 찾기: 배열 에서 하나의 수 k 를 기준 으로 합 니 다!!틀림없이 정 해진 값 이 야!!(규칙: 좌우 점, 중간 점, 무 작위 점 을 선택 할 수 있 으 나 경계 문제 에 주의해 야 합 니 다. l 과 i, r 는 j, (l + r) / 2 와 r, (r + l + 1) / 2 와 l) (2) 조정 구간: 구간 분계 점 (i 또는 j) 왼쪽 구간 을 기준 수 보다 작 게 하고 구간 분계 점 오른쪽 은 기준 수 보다 큽 니 다. (3) 재 귀 처리: 두 구간 에 대해 중복 (2), (3) 작업

예제 예 1: n 길이 의 정수 수열 을 지정 합 니 다. 빠 른 정렬 을 사용 하여 이 수열 을 작은 것 부터 큰 것 까지 정렬 하 십시오. 정렬 된 수열 을 순서대로 출력 합 니 다. 입력 형식 은 두 줄 이 고 첫 줄 은 정수 n 을 포함 합 니 다. 두 번 째 줄 은 n 개의 정수 (모든 정 수 는 1 ~ 10 ^ 9 범위 내) 를 포함 합 니 다.전체 수열 을 표시 합 니 다. 출력 형식 출력 은 모두 한 줄 이 고 n 개의 정 수 를 포함 하 며 정렬 된 수열 을 표시 합 니 다. 데이터 범위 1 ≤ n ≤ 100000 입력 사례: 5 3 1 2 4 5 출력 사례: 1 2 3 4 5

#include
#include

#define N 100000

void quick_sort(int q[], int l, int r);

int main(void)
{
     
	int n, q[N], i;

	scanf("%d", &n);
	for(i=0; i<n; i++) scanf("%d", &q[i]);

	quick_sort(q, 0, n-1);

	for(i=0; i<n; i++) printf("%d ", q[i]);
	return 0;
}

void quick_sort(int q[], int l, int r)
{
     
	if(l>=r) return;  //      ：           

	int k=q[(l+r)/2], i=l-1, j=r+1;  //              k，     do-while ，   “  ”           
	
	while(i<j)              //        ：    
	{
     
		do i++; while(q[i]<k);	// i              k  
		do j--; while(q[j]>k);	// j              k  
		if(i<j) swap(q[i], q[j]); 
	}
	
	quick_sort(q, l, j);	//   k     
	quick_sort(q, j+1, r);	//   k     
}	

다시 한 번 강조: k = i + j > > 1 이런 오 법 은 흔 하 다!!!
예 2: k 번 째 수 는 n 의 정수 수열 과 하나의 정수 k 를 정 합 니 다. 빠 른 선택 알고리즘 으로 수열 의 k 번 째 작은 수가 얼마 인지 구 하 십시오.
입력 형식 첫 줄 은 두 개의 정수 n 과 k 를 포함 합 니 다. 두 번 째 줄 은 n 개의 정수 (모든 정 수 는 1 ~ 109 범위 내) 를 포함 하여 정수 수열 을 표시 합 니 다. 출력 형식 은 하나의 정 수 를 출력 하여 수열 의 k 소 수 를 표시 합 니 다. 데이터 범위 1 ≤ n ≤ 100000 1 ≤ k ≤ n
입력 샘플: 5, 3, 2, 4, 1, 5, 3
출력 사례: 3 일반 해법: 모든 정렬, k 번 째 수 를 찾 습 니 다. 시간 복잡 도: O (nlogn)

#include
#define N 100000

void quick_sort(int q[], int l, int r);
void swap(int *a, int *b);

int main(void)
{
     
	int q[N], i, n, k;
	
	scanf("%d %d", &n, &k);
	for(i=0; i<n; i++) scanf("%d", &q[i]);

	quick_sort(q, 0, n-1);

	printf("%d", q[k-1]);

	return 0;
}

void swap(int *a, int *b)
{
     	
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void quick_sort(int q[], int l, int r)
{
     
	if(l>=r) return;

	int k=q[(l+r)/2], i=l-1, j=r+1;
	while(i<j)
	{
     
		do i++; while(q[i]<k);
		do j--; while(q[j]>k);
		if(i<j) swap(&q[i], &q[j]);
	}

	quick_sort(q, l, j);
	quick_sort(q, j+1, r);
}		
	

빠 른 정렬 쓰기 수정: 분계 점 오른쪽 수 에 따라 분계 점 왼쪽 수의 성질 보다 적 고 불필요 한 구간 시간 복잡 도 를 계속 버 립 니 다: O (n)

#include
#define N 100000

using namespace std;

int q[N];
int llen; 	//        

int quick_search(int l, int r, int k)
{
     
	if (l >= r) return q[r];	//   k  

	int t = q[l], i = l - 1, j = r + 1;
	while(i<j)
	{
     
		do i++; while(q[i] < t);
		do j--; while(q[j] > t);
		if(i<j) swap(q[i], q[j]);
	}

	llen = j - l + 1;
	if(k <= llen) quick_search(l, j, k);	//k       ，         ，     
	else quick_search(j+1, r, k - llen);	//k       ，         ，     
}		

int main()
{
     
	int i, n, k;
	
	scanf("%d %d", &n, &k);
	for(i = 0; i<n; i++) scanf("%d", &q[i]);

	printf("%d", quick_search(0, n-1, k));
	return 0;
}