빠 른 정렬 중 각종 파 티 션 알고리즘 학습

빠 른 순 서 는 많은 교과서 에서 거품 정렬 의 개선 이 라 고 불 린 다. 그러나 이것 은 나 에 게 빠 른 순 서 를 잘 이해 하지 못 하고 억지로 외 워 서 시험 이 끝나 면 쉽게 잊 혀 진다.
알고리즘 디자인 과 분석 한 책 에서 거품 은 보통 만력 법 으로 분류 되 고 빠 른 배열 은 분 치 기술 중의 하나 이다.빠 른 배열 의 사고방식 은:

1.    “  ”
2.    
3.                

이런 분류 가 있 으 니 이해 와 기억 이 한 단계 올 라 갔다.분 치 법의 정 수 는 한 가지 일 을 두 가지 (또는 여러 가지) 작은 일 로 나 누 어 각각 처리 하 는 것 이다.이런 사상 으로 처리 할 수 있 는 문제 만 있다 면 모두 분 치 법 으로 해 볼 수 있다.
빠 른 배열 의 주 함수 코드 는 이렇게 쓸 수 있 고 상당히 전형 적 인 분 치 법 이 실현 된다.

	public void quicksort(int[] n,int i,int j){
		if(i<j){
			int s = partition(n,i,j);
			quicksort(n,i,s-1);
			quicksort(n,s+1,j);
		}
	}

난점 과 중점 은 분 구 의 실현 이다. 분 구 의 주요 임 무 는 선택 한 중축 의 최종 위 치 를 찾 아 집합 을 두 개의 구역 으로 나 누 는 것 이다. 왼쪽 은 모두 그 보다 크 지 않 고 오른쪽 은 모두 그 보다 작 지 않다.우 리 는 다음 과 같은 단원 테스트 (groovy 단원 테스트, 중축 의 선택, 기본 값 은 가장 왼쪽 요소 입 니 다. 물론 중축 이 선택 한 전략 을 추상 화 할 수 있 지만 최종 적 으로 중축 과 가장 왼쪽 요 소 를 이 출발점 으로 바 꿀 수 있 습 니 다) 가 있 습 니 다.

	static int[] data = [2,40,1,10,6,8,7,80,28]
	
	@Test
	public void testPartition(){
	        //           
		assertEquals 0,Median.partition(data,0,1)
		assertEquals 2,Median.partition(data,1,2)
		assertEquals 1,Median.partition(data,0,8)
	}

간단 하고 직관 적 인 방법 이 있 는데 '구 덩이 를 파 서 숫자 를 채 워 라' [1] 라 는 댓 글 이 있 는데 정말 이미지 가 있다.엄 울 민 선생님 의 《 데이터 구 조 》 에서 도 이러한 실현 방식 이다.자바 구현 은 대체로 다음 과 같다.

	public static int partition(int[] array,int low,int high){
		int pivot = array[low];
		while(low < high){
			while(array[high] >= pivot && low < high) high--;
			array[low] = array[high];
			while(array[low] <= pivot && low < high) low++;
			array[high] = array[low];
		}
		array[low] = pivot;
		return low;
	}

그러나 이런 '구 덩이 를 파 서 메 우 는 수' 방법 은 매 층 순환 에서 low < high 가 성립 되 었 는 지 검 측 해 야 구역 이 완 성 될 때 low = = high 를 확보 할 수 있 고 이 위 치 는 중축 의 최종 위치 이다.
한편, 알고리즘 디자인 과 분석 을 바탕 으로 하 는 책 에서 준 구역 구분 방법 은 다음 과 같다. 이 는 두 끝 에서 스 캔 하여 i, j 가 교차 할 때 까지 j 는 중축 의 최종 위치 이다.

	public int partition(int[] n,int l,int r){
		int mid = n[l];	//          
		int i=l,j=r+1;
		do{
			while(n[++i]<mid && i<r);	//  i  
			while(n[--j]>mid );		//  n[l]==mid，  j     j==l，    
			swap(n,i,j);
		}while(i<j);
		swap(n,i,j);	//        
		swap(n,l,j);
		return j;
	}
	
	public void swap(int[] n,int i,int j){
		int temp = n[i];
		n[i] = n[j];
		n[j] = temp;
	}

이런 구역 구분 방법 은 아래 표 (여 기 는 i 와 j) 가 경 계 를 넘 지 않도록 보증 하면 된다.교묘 한 기 교 는 '삼 평 균 분 법' 으로 중축 을 선택 하 는 것 이다. '보초병' 과 같은 사상 으로 하 표 가 경 계 를 넘 지 않도록 하고 비교 비용 을 줄 이 는 것 이다.(물론 '보초병' 의 사상 으로 n 말미 에 mid 의 요 소 를 추가 하여 i 가 경 계 를 넘 지 않도록 보장 할 수 있 습 니 다)

	public int partition(int[] n,int l,int r){
		int midpos = getMidPosition(n, l, r);
		swap(n,l,midpos);	//              
		int mid = n[l];		//          
		int i=l,j=r+1;
		do{
			while(n[++i]<mid );	
			while(n[--j]>mid );	//  n[l] == mid，  j      ,     j==l
			swap(n,i,j);
		}while(i<j);
		swap(n,i,j);	//        
		swap(n,l,j);
		return j;
	}
	
	public void swap(int[] n,int i,int j){
		int temp = n[i];
		n[i] = n[j];
		n[j] = temp;
	}
	
	//       ，      l-r<2 ，           ，      i  
	public int getMidPosition(int[] n,int l,int r){
		int a=l,b=(l+r)/2+(l+r)%2,c=r;
		if(n[a]>=n[b] && n[b]>=n[c]) return b;
		if(n[c]>=n[b] && n[b]>=n[a]) return b;
		if(n[b]>=n[a] && n[a]>=n[c]) return a;
		if(n[c]>=n[a] && n[a]>=n[b]) return a;
		return c;
	}

분 구 된 사상 은 계산 중 값 과 선택 문 제 를 해결 하 는 데 도 쓸 수 있다.

	//    
	public static int getMedian(int[] array){
		return getKth(array,array.length/2);
	}
	//    
	public static int getKth(int[] array,int k){
		int low =0,high = array.length -1;
		int s = 0;
		do{
			s = partition(array,low,high);
			if(s>k) high = s-1;
			else low = s+1;
		}while(s != k);
		return array[s];
	}

참고 자료:
【 1 】 백화 고전 알고리즘 시리즈http://blog.csdn.net/morewindows/article/details/6684558