깊이 들 어가 서 빠 른 정렬 (QuickSort) (2) 간단 한 위조 코드

1. 빠 른 정렬 알고리즘: QuickSort

public void QuickSort(SeqList R,int low,int high){
		// R[low...high]      
		int pivotpos;//           
		if(low

2. 구분 알고리즘: Paition
(1) 간단 한 구분 알고리즘
【 1 】 구체 적 인 방법:
첫 번 째 단계: 두 개의 포인터, i 와 j 를 설정 합 니 다. 그들의 초기 값 은 구간 의 상계 와 하계, 즉 i = low, j = high 입 니 다.무질서 구역 의 첫 번 째 기록 R [i] (즉 R [low]) 을 기준 으로 기록 하고 pivot 에 저장 합 니 다.
2 부: 첫 번 째 키 워드 를 pivot. key 보다 작은 기록 R [j] 을 찾 을 때 까지 j 를 높 은 곳 에서 왼쪽으로 스 캔 합 니 다. R [j] 를 i 가 가리 키 는 위치 로 옮 기 고 키 워드 를 기준 키워드 pivot. key 보다 작은 기록 을 기준 왼쪽 으로 옮 긴 다음 i 포인터 가 i + 1 위치 에서 오른쪽으로 스 캔 합 니 다. 첫 번 째 키 워드 를 pivot. key 보다 큰 기록 R [i] 을 찾 을 때 까지 R [i] 를 찾 습 니 다.j 가 가리 키 는 위치 로 이동 하여 키 워드 를 기준 키워드 보다 큰 기록 을 기준 오른쪽 으로 옮 겼 습 니 다.이 어 포인터 j 는 위치 j - 1 에서 왼쪽으로 스 캔 하기 시작 했다.이렇게 스 캔 방향 을 바 꾸 고 양 끝 에서 각각 중간 으로 다가 가 i = j 까지 i 는 기준 pivot 의 최종 위치 이 며 pivot 를 이 위치 에 놓 으 면 한 번 의 구분 이 완 료 됩 니 다.
이 방법 을 온라인 으로 보 여 줍 니 다.
클릭 하여 링크 열기
인터넷 에 떠 도 는 것 과 는 다 르 게 헷 갈 릴 수도 있 습 니 다. \ # ^ ^ \ #.우 리 는 인터넷 에 떠 도 는 것 을 살 펴 보 자.
만약 이러한 숫자 가 있다 면:
2,4,22,12,0,3,4
① 먼저 i 는 첫 번 째 기록 을 가리 키 고 j 는 마지막 기록 을 가리 키 며 첫 번 째 숫자 를 기준 으로 숫자 pivot = R [i] 는 2 이다.
②  j 를 사용 하여 오른쪽 에서 왼쪽으로 스 캔 을 개발 하고 첫 번 째 키 워드 를 pivot. key 보다 작은 기록 R [j] 를 찾 을 때 까지 R [j] 를 i 가 가리 키 는 위치 에 있 는 키 워드 를 교환 하 는 위치 로 옮 겼 습 니 다. 즉, 데이터 교환 을 한 번 했 습 니 다.이 단 계 를 실행 한 후 이 그룹의 숫자 는:
0,4,22,12,2,3,4
③ i + 1 위치 에서 오른쪽으로 스 캔 하여 첫 번 째 키워드 가 pivot. key 보다 큰 기록 R [i] 를 찾 을 때 까지 R [i] 를 j 가 가리 키 는 위치 에 있 는 키워드 교환 위치 로 옮 기 면 데이터 교환 을 할 수 있 습 니 다.이 단 계 를 실행 한 후 이 그룹의 숫자 는:
0,2,22,12,4,3,4
④ j - 1 의 위 치 를 왼쪽으로 스 캔 하고 첫 번 째 키 워드 는 pivot. key 보다 작은 기록 R [j] 를 찾 을 때 까지 i = = j 를 기다 리 는 동안 찾 지 못 했 습 니 다. 이때 빠 른 정렬 이 끝 납 니 다.이 숫자 는 0, 2, 22, 12, 4, 3, 4 이다.
인터넷 에 있 는 이 알고리즘 과 위의 알고리즘 을 발견 할 수 있 습 니 다. 가장 큰 차이 점 은 바로 빨 간 글 자 를 표시 하 는 곳 입 니 다. 인터넷 에 있 는 것 은 위 치 를 바 꾸 는 것 입 니 다. 위의 알고리즘 은 한 번 의 할당 입 니 다. 데이터 양 이 많 을 때 인터넷 에 떠 도 는 이 알고리즘 은 대량의 성능 을 소모 한 것 입 니 다.
【 2 】 구분 알고리즘 위조 코드:

public int Partition(SeqList R,int i,int j){
		//  Partition(R,low,high) ， R[low...high]    
		//          
		dataType pivot = R[i];//     1       ，
		while(i=pivot.key){
				--j;//      ，   1      pivot.key   R[j]
			}
			if(ipivot.key
				R[j--]=R[i];//  ，   j--
			}
		}//endWhile
		R[i]=pivot;//         ， i==j   
		return i;
	}