백화 고전 알고리즘 시리즈 의 6 고속 정렬 고속 해결

고속 정렬 은 정렬 효율 이 같은 O (N * logN) 인 몇 가지 정렬 방법 에서 효율 이 높 기 때문에 자주 사용 된다. 게다가 고속 정렬 사상 - 분 치 법 도 확실히 유용 하기 때문에 매우 많은 소프트웨어 회사 의 필기시험 면접 은 텐 센트, 마이크로소프트 등 유명 IT 회사 들 이 모두 이 시험 을 즐겨 본다. 그리고 큰 크기 의 프로그램 시험 도 있다.대학원 진학 에서 도 빠 른 속도 로 순 위 를 매 기 는 모습 이 자주 나타난다.
전체적으로 말 하면 고속 정렬 을 직접 외 워 쓰 는 것 은 어느 정도 어렵 습 니 다. 왜냐하면 저 는 자신의 이해 에 대해 고속 정렬 에 대해 백화 해석 을 했 기 때문에 여러분 의 이해 에 도움 이 되 고 고속 정렬 에 이 르 러 고속 으로 해결 하 기 를 바 랍 니 다.
 
고속 정렬 은 C. R. A. Hoare 가 1962 년 에 제기 한 구분 교환 정렬 이다.그것 은 일반적으로 분 치 법 (Divide - and - ConquerMethod) 이 라 고 부 르 는 분 치 전략 을 채택 했다.
이 방법의 기본 사상 은:
1. 먼저 수열 에서 하나의 수 를 꺼 내 기준 수로 한다.
2. 파 티 션 과정 은 이 숫자 보다 큰 수 를 모두 오른쪽 에 놓 고 작 거나 같은 수 를 모두 왼쪽 에 놓 습 니 다.
3. 좌우 구간 에 두 번 째 단 계 를 반복 하여 각 구간 에 한 개의 숫자 만 있 을 때 까지 한다.
 
비록 고속 정렬 을 분 치 법 이 라 고 부 르 지만 분 치 법 이라는 세 글 자 는 고속 정렬 의 모든 절 차 를 잘 요약 할 수 없다.그래서 저 는 고속 정렬 에 대해 진일보 한 설명 을 했 습 니 다. 굴착 매 립 수 + 분 치 법:
먼저 실례 를 살 펴 보고 정 의 를 내 린 다음 에 (자신의 말로 정 의 를 정리 하 는 것 이 코드 를 실현 하 는 데 도움 이 될 것 입 니 다).
 
하나의 배열 을 시범 사례 로 삼 아 구간 의 첫 번 째 수 를 기준 으로 한다.
0
1
2
3
4
5
6
7
8
9
72
6
57
88
60
42
83
73
48
85
초기, i = 0;  j = 9;   X = a[i] = 72
이미 a [0] 의 수 를 X 에 저 장 했 기 때문에 배열 a [0] 에 구 덩이 를 파 서 다른 데 이 터 를 여기에 채 울 수 있다 고 이해 할 수 있 기 때문이다.
j 부터 앞으로 X 보다 작 거나 X 와 같은 수 를 찾 아 라.j = 8, 조건 에 부합 되면 a [8] 를 파 서 위의 구덩이 a [0] 에 채 웁 니 다.a[0]=a[8]; i++;  이렇게 하나의 구덩이 a [0] 가 해결 되 었 지만 또 하나의 새로운 구덩이 a [8] 가 형성 되 었 습 니 다. 어떻게 합 니까?간단 합 니 다. 다시 숫자 를 찾 아 a [8] 이 구 덩이 를 채 웁 니 다.이번 에는 i 부터 뒤로 X 이상 의 수 를 찾 습 니 다. i = 3 이 조건 에 부합 되면 a [3] 를 파 서 이전 구덩이 에 a [8] = a [3] 를 채 웁 니 다.j--;
 
배열 변경:
0
1
2
3
4
5
6
7
8
9
48
6
57
88
60
42
83
73
88
85
 i = 3;   j = 7;   X=72
위의 절 차 를 반복 해서 먼저 뒤에서 앞으로 찾 은 다음 에 앞에서 뒤로 찾 아 라.
j 부터 앞으로 찾 습 니 다. j = 5 가 조건 에 부합 되면 a [5] 를 파 서 위의 구덩이 에 채 웁 니 다. a [3] = a [5];i++;
i 부터 뒤로 찾 습 니 다. i = 5 시, i = = j 가 종료 되 었 기 때 문 입 니 다.
이때 i = j = 5, a [5] 는 마침 지난번 에 판 구덩이 이기 때문에 X 를 a [5] 에 채 웁 니 다.
 
배열 변경:
0
1
2
3
4
5
6
7
8
9
48
6
57
42
60
72
83
73
88
85
a [5] 앞의 숫자 는 모두 그것 보다 작고 a [5] 뒤의 숫자 는 모두 그것 보다 크다 는 것 을 알 수 있다.따라서 a [0... 4] 와 a [6... 9] 두 개의 구간 에 대해 상술 한 절 차 를 반복 하면 된다.
 
 
굴착 매 립 수 를 총 결 하 다.
1．i =L; j = R; 기준 수 를 파 서 첫 번 째 구 덩이 를 만들다.
2. j - 뒤에서 그것 보다 작은 수 를 찾 아 이 수 를 파 서 앞의 구덩이 a [i] 에 채 웁 니 다.
3. i + 는 앞에서 뒤로 그 보다 큰 수 를 찾 고 찾 은 후에 도 이 수 를 파 서 앞의 구덩이 a [j] 에 채 웁 니 다.
4. i = = j 까지 2, 3, 2 단 계 를 반복 해서 실행 하고 기준 수 를 a [i] 에 입력 합 니 다.
이 총 결 에 따라 매우 쉽게 구 덩이 를 파 서 채 우 는 코드 를 실현 합 니 다.

int AdjustArray(int s[], int l, int r) //           

{

	int i = l, j = r;

	int x = s[l]; //s[l] s[i]      

	while (i < j)

	{

		//        x    s[i]

		while(i < j && s[j] >= x) 

			j--;  

		if(i < j) 

		{

			s[i] = s[j]; // s[j]  s[i] ，s[j]         

			i++;

		}



		//           x    s[j]

		while(i < j && s[i] < x)

			i++;  

		if(i < j) 

		{

			s[j] = s[i]; // s[i]  s[j] ，s[i]         

			j--;

		}

	}

	//   ，i  j。 x      。

	s[i] = x;



	return i;

}

분 치 법의 코드 를 다시 쓰 십시오:

void quick_sort1(int s[], int l, int r)

{

	if (l < r)

    {

		int i = AdjustArray(s, l, r);//         s[]

		quick_sort1(s, l, i - 1); //      

		quick_sort1(s, i + 1, r);

	}

}

이런 코드 는 분명히 간결 하지 않 아서 그 조합 을 정리 했다.

//    

void quick_sort(int s[], int l, int r)

{

    if (l < r)

    {

		//Swap(s[l], s[(l + r) / 2]); //                  1

        int i = l, j = r, x = s[l];

        while (i < j)

        {

            while(i < j && s[j] >= x) //           x  

				j--;  

            if(i < j) 

				s[i++] = s[j];

			

            while(i < j && s[i] < x) //             x  

				i++;  

            if(i < j) 

				s[j--] = s[i];

        }

        s[i] = x;

        quick_sort(s, l, i - 1); //      

        quick_sort(s, i + 1, r);

    }

}

고속 정렬 에는 랜 덤 으로 기준 수 를 선택 하고 구간 내 데이터 가 적 을 때 다른 방법 으로 정렬 하여 재 귀 깊이 를 줄 이 는 등 버 전 번호 도 많이 개선 되 어 있다.관심 있 는 통 은 좀 더 깊이 연구 할 수 있다.
 
주 1, 어떤 책 에 서 는 중간의 수 를 기준 수로 하 는데 이 편리 함 을 실현 하기 위해 서 는 중간의 수 와 첫 번 째 수 를 직접 교환 하면 된다.
 
 전재 출처 를 표시 해 주 십시오.