이 빠른 정렬을 사용해 보세요-java지도 시간-php.cn

Tente Isto A classificação rápida

5장에서는
이라는 간단한 분류 방법을 보았습니다. 버블 정렬. 당시
가 있다고 언급되었습니다. 훨씬 더 나은 평가를 받았습니다. 여기서는 최고의 버전 중 하나인 빠른 정렬(Quicksort)을 개발하게 됩니다.
C.A.R.이 발명하고 명명한 신속한 분류. Hoare는 현재 사용 가능한 최고의 범용 분류 알고리즘입니다. 퀵 정렬의 가장 좋은 구현은 재귀를 기반으로 하기 때문에 5장에서는 이를 보여주지 못했습니다. 우리가 개발할 버전은 문자 배열을 분류하지만 논리는 모든 유형의 개체를 분류하도록 조정할 수 있습니다.
퀵 정렬은 파티션 개념을 기반으로 합니다. 일반적인 절차에는 비교라고 하는 값을 선택한 다음 배열을 두 섹션으로 나누는 작업이 포함됩니다. 파티션 값보다 크거나 같은 모든 요소는 한쪽에 삽입되고 더 작은 요소는 다른쪽에 삽입됩니다. 배열이 정렬될 때까지 나머지 각 섹션에 대해 이 프로세스가 반복됩니다. 예를 들어, fedacb 배열이 있고 d 값을 비교로 사용하면 빠른 정렬의 첫 번째 단계는 아래와 같이 배열을 재정렬합니다.

초기 피드 a c b
통로 1 b c d e f

그런 다음 각 섹션(예: bca 및 def)에 대해 이 프로세스를 반복합니다. 보시다시피 프로세스는 본질적으로 재귀적이며 실제로 퀵 정렬의 가장 깔끔한 구현은 재귀적입니다.
두 가지 방법으로 비교 값을 선택할 수 있습니다. 무작위로 선택하거나 배열에서 가져온 작은 값 집합의 평균을 찾아 선택할 수 있습니다. 최적의 분류를 얻으려면 값 범위의 정확히 중간에 있는 값을 선택해야 합니다. 그러나 대부분의 데이터세트에서는 이 작업을 수행하기가 쉽지 않습니다. 최악의 경우는 선택한 값이 한쪽 끝에 있는 경우입니다. 그렇더라도 퀵 정렬은 올바르게 실행됩니다.
우리가 개발할 퀵 정렬 버전은 배열의 중간 요소를 비교 대상으로 선택합니다.