알고리즘 학습 의 정렬 알고리즘: 빠 른 정렬
4599 단어 데이터 구조데이터 구조 와 알고리즘 분석
빠 른 정렬 방법:
1. 두 개의 지침 low 와 high 를 첨부 합 니 다. 그들의 초기 값 은 각각 low 와 high 이 고 중추 기록 의 키 워드 는 pivotkey 입 니 다.
2. 우선 하 이 가 가리 키 는 위치 에서 앞으로 검색 하여 첫 번 째 키 워드 를 찾 으 면 pivotkey 보다 작은 기록 과 중추 기록 이 서로 교환 된다.
3. low 가 가리 키 는 위치 에서 뒤로 검색 하여 첫 번 째 키 워드 를 찾 으 면 pivotkey 보다 큰 기록 과 중추 기록 이 서로 교환 된다.
4. low = high 까지 2, 3 단 계 를 반복 합 니 다.
예 를 들 어 위의 절 차 를 설명 한다.
초기 키워드: 49 38 65 97 76 13 27 49
1. low 와 high, 그리고 중추 기록 을 설정 하 는 키 워드 는 pivotkey 입 니 다.
49 38 65 97 76 13 27 49
↑(low) ↑(high)
↑(pivotkey)
2. 하 이 가 가리 키 는 위치 에서 앞으로 검색 하여 pivotkey 보다 작은 첫 번 째 기록 (여 기 는 27) 과 중추 기록 이 서로 교환 되 는 것 을 찾 습 니 다.
27 38 65 97 76 13 49 49
↑(low) ↑(high)
↑(pivotkey)
3. low 가 가리 키 는 위치 에서 뒤로 검색 하여 pivotkey 보다 큰 첫 번 째 기록 (여 기 는 65) 과 중추 기록 이 서로 교환 되 는 것 을 찾 습 니 다.
27 38 49 97 76 13 65 49
↑(low) ↑(high)
↑(pivotkey)
4. low = high 까지 2, 3 단 계 를 반복 합 니 다.
27 38 13 97 76 49 65 49
↑(low) ↑(high)
↑(pivotkey)
27 38 13 49 76 97 65 49
↑(low) ↑(high)
↑(pivotkey)
27 38 13 49 76 97 65 49
↑(low=high)
↑(pivotkey)
위 에서 제시 한 것 은 빠 른 정렬 과정 으로 전체 빠 른 정렬 과정 을 재 귀적 으로 진행 할 수 있다.정렬 대기 열 에 기록 이 하나 밖 에 없다 면 분명히 질서 가 있 습 니 다. 그렇지 않 으 면 빠 른 정렬 을 한 다음 에 분 할 된 두 개의 하위 서열 에 대해 빠 른 정렬 을 합 니 다.
예제 코드 1 (C 언어 설명):
/*********************************************************************
Author： date：2014-9-11
Email：[email protected]
@array: the pointer to the records
@low high
*********************************************************************/
//
void Swap(int *num1, int *num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//
int Partition(int array[], int low, int high)
{
int pivotkey = array[low];
while(low < high){
while(low < high && array[high] >= pivotkey)
high--;
Swap(&array[low], &array[high]);
while(low < high && array[low] <= pivotkey)
low++;
Swap(&array[low], &array[high]);
}
return low;
}
//
void QuickSort(int array[], int low, int high)
{
int pivotloc;
if(low < high){
pivotloc = Partition(array, low, high);
QuickSort(array, low, pivotloc - 1);
QuickSort(array, pivotloc + 1, high);
}
}
위의 빠 른 정렬 과정 에서 3 이 기록 의 할당 작업, 즉 swap 함수 중의 세 번 의 할당 을 사 용 했 으 나 중추 기록 에 대한 할당 은 불필요 하 다. 빠 른 정렬 이 끝 날 때, 즉 low = high 시의 위치 만 이 중추 기록 의 마지막 위치 이기 때문이다.따라서 고 쳐 쓰 는 알고리즘 은 다음 과 같다.
예제 코드 2 (C 언어 설명):
//
int Partition(int array[], int low, int high)
{
int pivotkey = array[low];
while(low < high){
while(low < high && array[high] >= pivotkey)
high--;
array[low] = array[high];
while(low < high && array[low] <= pivotkey)
low++;
array[high] = array[low];
}
array[low] = pivotkey;
return low;
}
//
void QuickSort(int array[], int low, int high)
{
int pivotloc;
if(low < high){
pivotloc = Partition(array, low, high);
QuickSort(array, low, pivotloc - 1);
QuickSort(array, pivotloc + 1, high);
}
}
주의:
1. 평균 시간 에 있어 빠 른 정렬 은 현재 가장 좋 은 내부 정렬 방법 으로 여 겨 진다.
2. 빠 른 정렬 은 모든 동 수량 급 (O (nlogn) 의 정렬 방법 중에서 평균 성능 이 가장 좋 은 것 으로 여 겨 진다.
3. 중심 축 수 치 를 선택 할 때 '삼자 취 중' 의 법칙 에 따라 중심 축 기록 을 선택 할 수 있다. 즉, low, high 와 mid 가 가리 키 는 값 중 중간 에 있 는 것 을 중심 축 값 으로 하면 최 악의 상황 에서 빠 른 정렬 의 성능 을 크게 개선 할 수 있다.
요약:
1. 시간 적 으로 볼 때 빠 른 정렬 의 평균 성능 은 다른 각종 정렬 방법 보다 우수 합 니 다.
2. 공간 적 으로 볼 때 빠 른 정렬 은 스 택 공간 이 필요 합 니 다.
참고 문헌:
1. 엄 울 민 오위 동 편저
2、http://blog.csdn.net/morewindows/article/details/6668714
3、http://blog.csdn.net/to_be_it_1/article/details/37866391
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
