자바 구현 알고리즘 빠 른 정렬

본문 은 참고 하 였 다.http://blog.csdn.net/morewindows/article/details/6684558
빠 른 정렬 은 정렬 효율 이 같은 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] 에 입력 합 니 다.
이 총 결 에 따라 구 덩이 를 파 서 채 우 는 코드 를 쉽게 실현 할 수 있다.

static void quickSort(int[] a, int left, int right) {
		if (a == null || a.length <= 1) {
			return;
		}
		if (left < right) {
			int i = left, j = right;
			int pivot = a[left];//             
			
			/**
			 *   
			 */
			while (i < j) {
				while (i < j && a[j] >= pivot) {
					j--;
				}
				if (i < j) {
					a[i] = a[j];
					i++;
				}

				while (i < j && a[i] < pivot) {
					i++;
				}
				if (i < j) {
					a[j] = a[i];
					j--;
				}
			}
			
			a[i] = pivot;
			
			/**
			 *   
			 */
			quickSort(a, left, i - 1);
			quickSort(a, i + 1, right);
		}
	}

빠 른 정렬 은 랜 덤 으로 기준 수 를 선택 하고 구간 내 데이터 가 적 을 때 다른 방법 으로 정렬 하여 재 귀 깊이 를 줄 이 는 등 개선 버 전도 많다.
다음은 의 분 제 와 중추 수의 실현 을 참고 하 는 것 이다.

static void quickSort1(int[] a, int left, int right) {
		if (a == null || a.length <= 1) {
			return;
		}
		if (left < right) {
			int i = left, j = right, temp = 0;
			int pivot = median3(a, left, right);//           
			
			/**
			 *   ，          
			 */
			while (i < j) {
				while (i < j && a[i] < pivot) {
					i++;
				}
				
				while (i < j && a[j] >= pivot) {
					j--;
				}
				
				if (i < j) {
					temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}
			
			//pivot a[i]   
			temp = a[i];
			a[i] = a[right - 1];
			a[right - 1] = temp;
			
			/**
			 *   
			 */
			quickSort(a, left, i - 1);
			quickSort(a, i + 1, right);
		}
	}

	/**
	 *      
	 * @param a
	 * @param left
	 * @param right
	 * @return
	 */
	private static int median3(int[] a, int left, int right) {
		int center = (left + right) / 2;
		int temp = 0;
		if (a[center] < a[left]) {
			temp = a[center];
			a[center] = a[left];
			a[left] = temp;
		}
		if (a[right] < a[left]) {
			temp = a[right];
			a[right] = a[left];
			a[left] = temp;
		}
		if (a[right] < a[center]) {
			temp = a[center];
			a[center] = a[right];
			a[right] = temp;
		}
		
		//place pivot at position right - 1 or left + 1，  left right     
		temp = a[center];
		a[center] = a[right - 1];
		a[right - 1] = temp;
		
		
		return a[right - 1];
	}

책 에 설명 되 어 있 습 니 다. 이 곳 에서 설명 한 분할 정책 은 좋 은 결 과 를 내 놓 을 수 있다 는 것 이 증명 되 었 습 니 다.그리고 중추 원 의 선택 은 세 가지 중 치 법 을 사용 하 는 것 을 추천 합 니 다.