교환 정렬: 빠른 정렬
빠른 정렬의 주요 사상:
빠른 정렬의 알고리즘 사상을 통해 알 수 있듯이 이것은 귀속적인 과정이다.
두 가지 질문:
빠른 정렬을 철저히 이해하려면 두 가지 문제를 해결해야 한다.
질문 1: 축 값 선택?
축값의 중요성은 분할을 통해 서열을 가능한 한 길이가 같은 두 부분으로 나누어야 분치법이 작용할 수 있다는 데 있다.만약 축값이 서열의 최치라면 분할 후 원소가 모두 한쪽으로 도망가면 분치법은 무효가 된다.알고리즘 효율이 향상되지 않습니다. -다른 사람이 빠른 줄을 쓰는 것을 볼 때, 그의 축 값의 선택에 주의해라.
문제2: 어떻게 분할합니까?
이것은 구체적인 기교와 전략과 관련된다.잠시 후의 코드에서 우리는 하나하나 소개한다.
버전 1 빠른 정렬:
첫 번째 요소 또는 마지막 요소를 축 값으로 직접 선택합니다.이것도 국내 많은 교재 중의 작법이다.
예:
원래 순서 4 8 12 1 9 6
아래 0 1, 2, 3, 4, 5
축 값 pivot=4
ij 초기화
iji부동, 이동 j,while(i
요소 이동
1 8 12 1 9 6
ijj부동, 이동 i,while(i
i, j 다시 이동 j, i와 j가 만나 종료
마지막 1 4 12 8 9 6 pivot
축값 4의 좌우 두 부분을 이어서 분할하다.
나는 네가 틀림없이 알아볼 것이라고 생각한다. 그리고 이 축의 값은 4, 정말 잘 선택하지 못했다. 왜냐하면 분할 후 왼쪽 부분에 원소가 하나밖에 없기 때문이다.
어떤 사람들은 위의 방법은 구덩이를 파서 채우는 것이라고 말한다.이런 묘사는 정말 형상적이다.간단하게 설명하자면 먼저 첫 번째 원소를 축값으로 하고 변수 pivot로 축값을 저장한다. 이것이 바로 구덩이를 파는 것이다.이때 a[0]는 구덩이다.이어서 j를 이동하여 적당한 위치의 j를 a[0]에 채워서 a[j]는 새로운 구덩이가 되었다.낡은 구덩이가 메워지면 새로운 구덩이가 나타난다.i와 j가 만날 때까지 이 마지막 구덩이는pivot에 채워진다.이로써 두 번째 분할을 완성하였다.
알아들었으니 코드를 두드려라!
void QuickSort(int a[], int n) // ，
{
if (a && n > 1)
{
int i, j, pivot; //pivot
i=0, j = n - 1;
pivot = a[0]; //
while (i < j)
{
while (i < j && a[j] >= pivot)
j--;
if (i < j)
a[i++] = a[j];
while (i < j && a[i] <= pivot)
i++;
if (i < j)
a[j--] = a[i];
}
a[i] = pivot; //
QuickSort(a, i);
QuickSort(a + i + 1, n - i -1);
}
} 이제 마지막 원소를 축값으로 하는 코드를 생각해 보세요. 서두르지 말고 먼저 움직이세요!코드는 다음과 같습니다.
void QuickSort(int a[], int n)
{
if (a && n > 1)
{
int i, j, pivot; //pivot
i = 0, j = n - 1;
pivot = a[j]; //
while (i < j)
{
while (i < j && a[i] <= pivot)
i++;
if (i < j)
a[j--] = a[i];
while (i < j && a[j] >= pivot)
j--;
if (i < j)
a[i++] = a[j];
}
a[i] = pivot; //
QuickSort(a, i);
QuickSort(a + i + 1, n - i - 1);
}
}축 값 선택 정책
축 값인 pivot가 무효가 되지 않도록 하기 위해서.우리는 pivot의 선택을 개선하기 위해 정책을 사용할 수 있습니다.
전략 1:
임의로 시퀀스에서 요소를 축 값으로 선택합니다.
int SelectPivot(int a[], int low, int high)
{
int size = high - low + 1;
srand((unsigned)time(0));
return a[low + rand()%size];
}수미 요소를 선택하는 것은 이 전략의 특례가 아니다!
전략 2:
무작위로 세 수를 선택하여 중위수를 얻다.
int SelectPivot(int a[], int low, int high)
{
int size = high - low + 1;
int p1, p2, p3;
srand((unsigned)time(0));
p1 = low + rand()%size;
p2 = low + rand()%size;
p3 = low + rand()%size;
/*
* ：
* ，p1 ，
* ， p2
*/
if(a[p1] > a[p2])
swap(p1, p2);
if(a[p1] > a[p3])
swap(p1, p3);
if(a[p2] > a[p3])
swap(p2, p3);
return a[p2];
}그것의 한 가지 특례는 원래 서열의 첫 번째를 선택하는 것이다.
꼬리, 중간 세 수를 세어 그것들의 중위수를 얻다.
현재로서는 기본적으로 상용하는 것이 이 두 가지 전략에 있다.
그러나 나는 한마디 해야 한다. 만약에 원 서열 중의 원소 자체가 무작위로 저장된 것이다. 즉, 각 원소가 각 위치에 나타날 확률이 같다는 것이다.그렇다면 특별히 수미원소를 선택하는 것과 무작위로 선택하는 것은 어떤 차이가 있을까?어떻게 보셨는지 모르겠어요.
또 한마디 덧붙여야 한다. 무작위로 축 값을 선택한 후, 그것을 머리나 꼬리의 요소와 교환하는 것을 기억해야 한다.왜?알잖아!
버전 2 빠른 정렬:
이것도 알고리즘 도론의 판본이다.그것의 보편적인 방법은 꼬리 요소를 pivot로 선택하는 것이다.중점은 분할 함수:partition () 을 사용했다는 것이다.
위조 코드는 다음과 같습니다.
PARTITION(A, low, high)
1.pivot<- A[high]//꼬리 요소를 축값으로 선택
2.i<-low-1//low-1을 i에게 부여하고 아래와 같이
3. for j<-low to high-1//j의 변화 범위 [low, high-1]
4. do if A[j] <= pivot
5. then i <- i+1
6. exchange A[i]<->A[j]
7. exchange A[i+1} <-> A[high]
8. return i+1;//분할된 위치를 반환합니다.
그런 다음 전체 배열을 차례로 정렬합니다.
QUICKSORT(A, low, high)
1 if low < high
2 then q <- PARTITION(A, low, high)//요소를 분할하는 것은 여기에 있습니다.
3 QUICKSORT(A, low, q - 1)
4 QUICKSORT(A, q + 1, high)
만약 네가 위조 코드를 보는 것에 익숙하지 않다면, 내가 예를 들겠다. (아니면 위의 서열)
원래 순서 4 8 12 1 9 6
아래 표. - 1, 2, 3, 4, 5 축값. pivot은 6.
ija[j]=a[0]=4<6, 다음 i++ 초기화;다시 swap(a[i], a[j]);다음 j++;
교환 4 8 12 1 9 6
계속 이동 j
ij a[j]=a[3]=1<6, 다음...
교환 4 1 12 8 9 6
i j
i j
교환 41 68 9 12 마지막 swap(a[i+1], a[high]);또는 swap(a[i+1], a[j]);
그래서 마지막으로 돌아온 건 i+1입니다.
대백화로 위의 정렬 과정을 설명한다. 두 개의 바늘 i, j로 초기화하면 i=-1이다.j=0, 이어서 j를 끊임없이 증가시키고 a[j]>pivot를 만나면 i와 교환하여 j가 끝까지 가리킨다.
더 직설적인 말: 처음부터 원래 서열을 훑어보고 축 값보다 작은 것을 만나면 서열 앞으로 교환한다.
알아듣고 코드를 썼는데...
int partition(int a[], int low, int high)
{
int i, j;
i = low - 1;
j = low;
while (j < high)
{
if (a[j] < a[high])
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[high]); //
return i; // ++i， i+1
}
void quicksort(int a[], int low, int high)
{
if (low < high) // ，
{
int i = partition(a, low, high);
quicksort(a, low, i - 1);
quicksort(a, i + 1, high);
}
}
void QuickSort(int a[], int n)
{
if (a && n>1)
quicksort(a, 0, n - 1);
}문외한: 있는 Api 디자인을 보면 다음과 같다. QuickSort(int a[], int low, int high).사용자에게 0을 하나 더 쓰게 하다니!이렇게 하면 사용자를 고려하지 않는다.간결할수록 좋다.정렬은 그룹 이름과 그룹 크기만 주면 됩니다.
위의 절차에 대해 다시 생각하기: 초기화 i=-1 보기;이상하지 않아요?왜 i는 반드시 -1부터 시작해야 하는지 i의 작용을 자세히 이해하면 i본은 0부터 시작할 수 있다는 것을 알게 될 것이다.이러한 방법의 파티션 () 방법은 다음과 같습니다.
int partition(int a[], int low, int high)
{
int i, j;
i = low; // ！
j = low;
while(j < high)
{
if (a[j] < a[high])
swap(a[i++], a[j]);
j++;
}
swap(a[i], a[high]); //
return i;
}다시 생각: 왜 j는 하이를 가리킬 수 없습니까?만약if(a[j]
int partition(int a[], int low, int high)
{
int i, j;
i = low;
j = low;
while (j <= high)
{
if (a[j] <= a[high])
swap(a[i++], a[j]);
j++;
}
return i-1; // i-1， ？
}때때로 quicksort () 와partition () 을 함수로 쓰는 것은 더 이상 간단하지 않은 일이다.
버전 3의 빠른 정렬:
위에서 사용한 것은 모두 귀속의 방법이다. 귀속을 비귀속으로 바꾸는 것은 항상 간단하지 않고 사람을 흥분시킨다.이 판본은 바로 빠른 정렬의 비귀속 쓰기이다.
void QuickSort(int a[], int low, int high)
{
if (low < high)
{
stack<int> s; // STL
int l,mid,h;
mid = partition(a, low, high);
/*
[low, mid-1] [mid+1, high]
： ，
*/
if (low < mid-1)
{
s.push(low);
s.push(mid - 1);
}
if (mid + 1 < high)
{
s.push(mid + 1);
s.push(high);
}
// ，
while(!s.empty())
{
h=s.top();
s.pop();
l=s.top();
s.pop();
mid = partition(a, l, h);
if (l < mid - 1)
{
s.push(l);
s.push(mid - 1);
}
if (mid + 1 < h)
{
s.push(mid + 1);
s.push(h);
}
}
}
}이 비귀속적인 작법은 매우 재미있어서 기교가 매우 필요하다.잘 생각해 봐, 너는 알 수 있어.
알림: 정렬할 하위 시퀀스의 맨 끝 요소를 창고에 저장하고 다음while 순환할 때 이 범위를 꺼내서 이 하위 시퀀스를partition 조작합니다.
소결:
빠른 정렬은 빠른 처리라고 불리며 시간 복잡도는 O(nlogn)이다.기본적으로 가장 좋은 정렬 방법이다.그것의 작법은 상기 세 가지 외에 대동소이하다.여기 봐.너는 반드시 그것을 철저히 이해했을 것이다.이상의 글쓰기는 모두 본인의 테스트를 거쳤는데, 당신의 테스트가 나와 같은지 모르겠습니다.
전재는 출처를 밝히십시오. 본문 주소:http://blog.csdn.net/zhangxiangdavaid/article/details/25436609
도움이 된다면, 기껏해야 하나!
본 칼럼의 목록
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 백엔드에서 데이터를 트리로 변환하고 맵은 json 트리를 생성하여 백엔드로 되돌려줍니다. (백엔드 변환)java 백엔드, 데이터를 트리로 변환하고,map는 json 트리를 생성하여 전방으로 되돌려줍니다(백엔드 변환) 1. 왜 이런 블로그를 쓰나요? 2.java 백엔드 코드 3. 전환된 데이터는 다음과 유사한 형식으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
