빠 른 정렬 (프로 세 스 도해)

우리 가 지금  1  2 7  9  3  4  5 10  8. 이 10 개의 수 를 정렬 합 니 다.우선 이 서열 에서 마음대로 하나의 수 를 기준 으로 한다 (이 명사 에 놀 라 지 마라. 바로 참조 할 수 있 는 숫자 이다. 조금 있 으 면 그것 이 무엇 을 하 는 지 알 게 될 것 이다).편 의 를 위해 서 는 첫 번 째 6 을 기준 으로 합 시다.다음은 이 서열 의 모든 기준 수 보다 큰 수 를 6 의 오른쪽 에 놓 고 기준 수 보다 작은 수 를 6 의 왼쪽 에 놓 아야 한다. 아래 와 같은 배열 이다.
       3  1  2 5  4  6  9 7  10  8
 
        초기 상태 에서 숫자 6 은 서열 의 1 위 에 있다.우리 의 목 표 는 6 을 서열 중간의 어느 위치 로 옮 기 는 것 이다. 이 위치 가 k 라 고 가정 하 는 것 이다.지금 이 k 를 찾 아야 합 니 다. 그리고 k 위 를 분계 점 으로 하고 왼쪽 의 수 는 모두 6 보다 적 으 며 오른쪽 의 수 는 모두 6 보다 큽 니 다.생각해 봐, 너 는 이 정도 까지 할 수 있 는 방법 이 있 니?
 
        힌트 하나 드릴 게 요.거품 을 일 으 켜 정렬 하 는 것 이 어떻게 '교환' 을 통 해 한 걸음 한 걸음 씩 모든 수 를 제자리 로 돌려 놓 는 지 기억 해 보 세 요.이때 너 도 '교환' 의 방법 을 통 해 목적 을 달성 할 수 있다.구체 적 으로 어떻게 한 걸음 한 걸음 교환 합 니까?어떻게 교환 해 야 편리 할 뿐만 아니 라 시간 도 절약 할 수 있 습 니까?우선 서둘러 아래 를 보지 말고 펜 을 꺼 내 종이 에 그림 을 그 려 보 세 요.저 는 고등학교 때 거품 정렬 알고리즘 을 처음 배 웠 을 때 거품 정렬 이 시간 낭비 라 고 생각 했 습 니 다. 매번 에 인접 한 두 개의 숫자 만 비교 할 수 있다 는 것 은 너무 불합리 합 니 다.그래서 저 는 방법 을 생각 했 습 니 다. 나중에 알 고 보 니 이것 이 바로 '빠 른 정렬' 이 었 습 니 다. 제 작은 자 뻑 을 허락 해 주 십시오 (^ o ^).
 
        방법 은 사실 매우 간단 하 다. 각각 초기 서열 에서 6.  1  2 7  9  3  4  5 10  8. 양 끝 에서 탐 사 를 시작한다.먼저 오른쪽 에서 왼쪽으로 6 보다 작은 수 를 찾 은 다음 에 왼쪽 에서 오른쪽으로 6 보다 큰 수 를 찾 은 다음 에 그들 과 교환 합 니 다.여 기 는 두 개의 변수 i 와 j 를 사용 하여 각각 서열 의 가장 왼쪽 과 가장 오른쪽 을 가리 킬 수 있다.우 리 는 이 두 변 수 를 위해 듣 기 좋 은 이름 인 '보초병 i' 와 '보초병 j' 를 지 었 다.처음에 보초병 i 가 서열 의 맨 왼쪽 (즉 i = 1) 을 가리 키 고 숫자 6 을 가리킨다.보초병 j 가 서열 의 맨 오른쪽 (즉 j = 10) 을 가리 키 고 숫자 8 을 가리킨다.
 
       우선 보초병 j 가 출동 하기 시작 했다.이곳 에 설 치 된 기준 수 는 가장 왼쪽 숫자 이기 때문에 보초병 j 가 먼저 출동 하도록 해 야 한 다 는 점 이 매우 중요 하 다 (왜 그런 지 스스로 생각해 보 세 요).보초병 j 는 6 보다 작은 숫자 를 찾 을 때 까지 한 걸음 한 걸음 왼쪽으로 옮 겼 다.다음 보초병 i 는 6 이상 의 숫자 가 멈 출 때 까지 오른쪽으로 한 걸음 더 움 직 였 다.마지막 으로 보초병 j 는 숫자 5 앞 에 멈 추 었 고 보초병 i 는 숫자 7 앞 에 멈 추 었 다.
 
 
 
       현재 보초병 i 와 보초병 j 가 가리 키 는 원소 의 값 을 교환 합 니 다.교환 후의 서열 은 다음 과 같다.
        6  1  2  5  9 3  4  7  10  8
 
 
 
        여기 서 첫 교환 이 끝 났 습 니 다.그 다음 에 보초병 j 가 계속 왼쪽으로 움 직 이기 시작 했다.그 는 4 (기준 6 보다 작 아 요 구 를 충족 시 키 는 것) 를 발견 하고 멈 추 었 다.보초병 i 도 계속 오른쪽으로 움 직 였 다. 그 는 9 (기준 6 보다 크 고 요 구 를 만족 시 키 는 것) 를 발견 하고 멈 추 었 다.이때 다시 교환 을 하고 교환 후의 순 서 는 다음 과 같다.
        6  1  2 5  4  3  9  7 10  8
 
        2 차 교환 이 끝나 고 '탐사' 가 계속 됐다.보초병 j 는 계속 왼쪽으로 움 직 였 다. 그 는 3 (기준 6 보다 작 고 요 구 를 만족 시 키 는 것) 을 발견 한 후에 다시 멈 추 었 다.보초병 i 계속 오른쪽으로 이동, 큰일 났 어!이때 보초병 i 와 보초병 j 가 만 났 고 보초병 i 와 보초병 j 는 모두 3 앞으로 걸 어 갔다.이때 '탐지' 가 끝났다 는 뜻 이다.우 리 는 기준 수 6 과 3 을 교환 할 것 이다.교환 후의 서열 은 다음 과 같다.
        3  1 2  5  4  6  9 7  10  8
 
 
        이로써 1 차 탐측 이 진정 으로 끝났다.이때 기준 수 6 을 분계 점 으로 하고 6 왼쪽 의 수 는 모두 6 보다 적 으 며 6 오른쪽 의 수 는 모두 6 보다 크다.아까 의 과정 을 돌 이 켜 보면 보초병 j 의 사명 은 기준 수 보다 적은 수 를 찾 는 것 이 고 보초병 i 의 사명 은 기준 수 보다 큰 수 를 찾 는 것 이다. i 와 j 가 만 날 때 까지.
 
        OK, 설명 완료.현재 기준 수 6 은 이미 제자리 로 돌 아 왔 는데, 그것 은 마침 서열 의 6 위 에 있다.이때 우 리 는 원래 의 서열 을 6 을 분계 점 으로 두 개의 서열 로 나 누 었 고 왼쪽 의 서열 은 '3' 이다.  1 2  5  4. 오른쪽 서열 은 '9' 입 니 다.  7  10  8”。다음은 이 두 서열 을 각각 처리 해 야 한다.6. 왼쪽 과 오른쪽 서열 이 아직 혼 란 스 러 워 서 요.그러나 괜 찮 습 니 다. 우 리 는 이미 방법 을 익 혔 습 니 다. 그 다음 에 아까 의 방법 을 모 의 해서 각각 6 왼쪽 과 오른쪽의 서열 을 처리 하면 됩 니 다.이제 6 왼쪽 서열 을 처리 하 겠 습 니 다.
 
        왼쪽 서열 은 '3' 입 니 다.  1  2 5  4”。이 서열 을 3 을 기준 으로 조정 하여 3 왼쪽 의 수 를 모두 3 보다 적 게 하고 3 오른쪽 의 수 는 모두 3 보다 많 게 하 십시오.자, 이제 붓 을 들 어 봅 시다.
 
        만약 당신 이 시 뮬 레이 션 한 것 이 틀 리 지 않 았 다 면, 조정 이 끝 난 후의 순 서 는 마 땅 히.
        2  1  3  5  4
 
        OK, 지금 3 은 귀 위 했 습 니 다.다음은 3 왼쪽 서열 인 '21' 과 오른쪽 서열 인 '54' 를 처리 해 야 한다.서열 '21' 을 2 를 기준 으로 조정 하고 처리 가 끝 난 후의 서열 은 '12' 이 며 이 2 는 이미 제자리 로 돌 아 왔 다.서열 '1' 은 하나의 숫자 만 있 고 어떠한 처리 도 할 필요 가 없다.이로써 우 리 는 서열 '21' 을 모두 처 리 했 고 서열 은 '12' 이다.서열 '54' 의 처리 도 이 방법 을 본 떠 마지막 으로 얻 은 서열 은 다음 과 같다.
        1  2  3 4  5  6 9  7  10  8
 
        시퀀스  7  10  8. 새로운 하위 서열 을 분리 할 수 없 을 때 까지 아까 의 과정 을 모 의 한다.최종 적 으로 이러한 서열 을 얻 게 될 것 이다. 다음 과 같다.
        1  2  3 4  5  6  7  8 9  10
 
        여기까지 정렬 이 완전히 끝 났 습 니 다.세심 한 학생 들 은 빠 른 정렬 의 모든 라운드 처 리 는 바로 이 라운드 의 기준 수 를 제자리 로 돌려 모든 숫자 가 제자리 로 돌아 갈 때 까지 정렬 이 끝났다 는 것 을 알 게 되 었 을 것 이다.아래 의 위의 패기 있 는 그림 은 전체 알고리즘 의 처리 과정 을 묘사 합 니 다.
 
 
        빠 른 정렬 이 빠 릅 니 다. 거품 정렬 보다 매번 교환 이 점프 식 이기 때 문 입 니 다.정렬 할 때마다 기준점 을 설정 하고 기준점 보다 작은 수 를 모두 기준점 의 왼쪽 에 놓 으 며 기준점 보다 큰 수 를 모두 기준점 의 오른쪽 에 놓 습 니 다.이렇게 하면 매번 교환 할 때마다 거품 정렬 처럼 매번 인접 한 수 사이 에서 만 교환 할 수 있 고 교환 하 는 거리 가 훨씬 크다.그래서 전체적인 비교 와 교환 횟수 가 적어 지면 서 속도 가 자 연 스 럽 게 높 아 졌 다.물론 최 악의 경우 에 도 인접 한 두 수 를 교환 한 것 으로 보인다.따라서 빠 른 정렬 의 최 악의 시간 복잡 도와 거품 정렬 은 모두 O (N2) 이 고 평균 시간 복잡 도 는 O (NLogN) 이다.

#include 
int a[101],n;//      ，              
void quicksort(int left, int right) {
	int i, j, t, temp;
	if(left > right)
		return;
    temp = a[left]; //temp        
    i = left;
    j = right;
    while(i != j) { //     ，        
    	while(a[j] >= temp && i < j)
    		j--;
    	while(a[i] <= temp && i < j)//     
    		i++;       
    	if(i < j)//            
    	{
    		t = a[i];
    		a[i] = a[j];
    		a[j] = t;
    	}
    }
    //        
    a[left] = a[i];
    a[i] = temp;
    quicksort(left, i-1);//       ，          
    quicksort(i+1, right);//        ，          
}
int main() {
	int i;
    //    
	scanf("%d", &n);
	for(i = 1; i <= n; i++)
		scanf("%d", &a[i]);
    quicksort(1, n); //      
    //        
    for(i = 1; i < n; i++)
    	printf("%d ", a[i]);
    printf("%d
", a[n]);
    return 0;
}