이 빠른 정렬을 사용해 보세요

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

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

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

QSDemo.java를 참조하세요.

빠른 정렬:

• 가장 효율적이고 널리 사용되는 분류 알고리즘 중 하나입니다.
• C.A.R.이 발명했습니다. 하아.
• 파티션 개념을 바탕으로 배열을 여러 섹션으로 나누어 재귀적으로 정렬하는 방식입니다.
• 버블 정렬 및 기타 간단한 방법보다 효율적입니다.

작전:

• 비교값(피벗):
• 값이 참조(피벗)로 선택되고 해당 값을 중심으로 배열이 구성됩니다.
• 피벗보다 작은 요소는 한쪽으로 이동하고 큰 요소는 다른 쪽으로 이동합니다.
• 배열이 완전히 정렬될 때까지 각 섹션마다 이 과정을 반복적으로 반복합니다.

퀵소트

QS데모

위 내용은 이 빠른 정렬을 사용해 보세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!