>  기사  >  웹 프론트엔드  >  JavaScript의 버킷 정렬에 대한 자세한 설명

JavaScript의 버킷 정렬에 대한 자세한 설명

韦小宝
韦小宝원래의
2018-03-14 14:28:372628검색

이 기사에서는 JavaScript의 버킷 정렬에 대해 설명합니다. JavaScript의 버킷 정렬에 관심이 있다면 이 기사를 살펴보겠습니다. point

버킷 정렬은 카운팅 정렬의 업그레이드 버전입니다. 함수의 매핑 관계를 활용합니다. 효율성의 핵심은 이 매핑 함수를 결정하는 데 있습니다.

버킷 정렬을 보다 효율적으로 수행하려면 다음 두 가지를 수행해야 합니다.

1. 추가 공간이 충분할 때 버킷 수를 늘려보세요.

2. 입력 N을 변환합니다. 데이터는 K개의 버킷에 균등하게 분산됩니다

동시에 버킷의 요소를 정렬할 때 어떤 비교 정렬 알고리즘을 선택하느냐가 성능에 결정적인 영향을 미칩니다.

가장 빠른 때는 언제


입력 데이터를 각 버킷에 균등하게 분산할 수 있을 때

가장 느린 때는 언제


입력 데이터를 동일한 버킷에 분산할 때

버킷 정렬 JavaScript 코드 구현:

function bucketSort(arr, bucketSize) {  
    if (arr.length === 0) {  
      return arr;  
    }  
  
    var i;  
    var minValue = arr[0];  
    var maxValue = arr[0];  
    for (i = 1; i < arr.length; i++) {  
      if (arr[i] < minValue) {  
          minValue = arr[i];                //输入数据的最小值  
      } else if (arr[i] > maxValue) {  
          maxValue = arr[i];                //输入数据的最大值  
      }  
    }  
  
    //桶的初始化  
    var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5  
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;  
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;     
    var buckets = new Array(bucketCount);  
    for (i = 0; i < buckets.length; i++) {  
        buckets[i] = [];  
    }  
  
    //利用映射函数将数据分配到各个桶中  
    for (i = 0; i < arr.length; i++) {  
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);  
    }  
  
    arr.length = 0;  
    for (i = 0; i < buckets.length; i++) {  
        insertionSort(buckets[i]);                      //对每个桶进行排序,这里使用了插入排序  
        for (var j = 0; j < buckets[i].length; j++) {  
            arr.push(buckets[i][j]);                        
        }  
    }  
  
    return arr;}

위 내용이 이 글의 전부입니다. 잘 모르신다면 양쪽 모두 직접 구현해 보시면 익히기 쉬울 것입니다!

관련 권장 사항:
버킷 정렬 알고리즘 예제 공유의 PHP 구현

위 내용은 JavaScript의 버킷 정렬에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.