버킷 정렬이란 무엇입니까?

버킷 정렬은 배열을 제한된 수의 버킷으로 나누어 작동하는 정렬 알고리즘입니다. 버킷 정렬은 정렬할 배열의 값이 고르게 분포될 때 비둘기집 정렬의 귀납적 결과입니다. 선형 시간이지만 버킷 정렬은 비교 정렬이 아니며 "O(n log n)" 하한의 영향을 받지 않습니다.

Bucket Sorting

N개의 키워드 값 범위가 0에서 M-1 사이이고 M이 N보다 훨씬 작은 것으로 알려진 경우 버킷 정렬 알고리즘은 "버킷"을 생성합니다. " 각 값에 대해 즉 M개의 버킷을 생성합니다. N개의 키워드를 스캔할 때 각 키워드를 해당 버킷에 넣은 다음 버킷 순서대로 수집합니다. 자연스럽게 질서정연해집니다

소개:

버킷 정렬, 소위 빈 정렬(bin sort)은 배열을 제한된 수의 버킷으로 나누어 작동하는 정렬 알고리즘입니다. 각 버킷은 개별적으로 정렬됩니다(다른 정렬 알고리즘을 사용하거나 버킷 정렬을 계속해서 반복적으로 사용할 수 있음). 버킷 정렬은 비둘기집 정렬의 귀납적 결과입니다. 버킷 정렬은 정렬할 배열의 값이 고르게 분포되어 있을 때 선형 시간(Θ(n))을 사용합니다. 그러나 버킷 정렬은 비교 정렬이 아니며 O(n log n) 하한의 영향을 받지 않습니다.

Definition

가정: 입력은 무작위 프로세스에 의해 생성된 간격 [0, 1)에 균일하게 분포된 실수입니다. 간격 [0, 1)을 동일한 크기의 n개의 하위 간격(버킷)으로 나눕니다. 각 버킷 크기는 1/n입니다: [0, 1/n), [1/n, 2/n), [2/n , 3/n),…,[k/n, (k+1)/n),…n개의 입력 요소를 이 버킷에 배포하고 버킷의 요소를 정렬한 다음 버킷을 순서대로 연결하여 0 ≤A를 입력합니다. [1 ..n] <1 보조 배열 B[0..n-1]은 버킷(연결된 목록)을 가리키는 포인터 배열입니다.

위 내용은 버킷 정렬이란 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!