집 >웹 프론트엔드 >JS 튜토리얼 >JS Hill 정렬 알고리즘 정보(자세한 튜토리얼)

JS Hill 정렬 알고리즘 정보(자세한 튜토리얼)

亚连원래의: 2018-06-21 11:29:001807검색

이 글에서는 주로 JS 정렬 알고리즘의 Hill 정렬과 퀵 정렬의 구현 방법을 소개하고 있으며, Hill 정렬과 퀵 정렬의 원리를 분석하고 JavaScript 구현 기술이 필요한 친구들이 참고할 수 있습니다. 이 기사의 예제에서는 JS 정렬 알고리즘 Hill 정렬 및 빠른 정렬의 구현 방법을 설명합니다. 참조를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

힐 정렬: 간격 순서를 정의합니다(예: 5, 3, 1). 처음 처리될 때는 간격이 5인 모든 요소가 처리되고, 다음 번에는 간격이 3인 요소가 처리되며, 마지막에는 간격이 1인 요소가 처리됩니다. 즉, 인접한 요소는 표준 삽입 정렬을 수행합니다.

마지막 처리가 시작될 때 대부분의 요소가 올바른 위치에 있으며 알고리즘은 요소를 삽입하는 것보다 더 발전된 많은 요소를 교체할 필요가 없습니다.

시간 복잡도

O(n*logn)

function shellSort(){
  var N=arr.length;
  var h=1;
  while(h<N/3){
    h=3*h+1;//设置间隔
  }
  while(h>=1){
    for(var i=h; i<N; i++){
      for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){
        swap(arr, j, j-h);
      }
    }
    h=(h-1)/3;
  }
}
function swap(array, i, j){//两个数调换
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

빠른 정렬: 데이터를 더 작은 요소와 더 큰 요소를 포함하는 여러 하위 시퀀스로 재귀적으로 분해하고 모든 데이터가 순서대로 될 때까지 이 단계를 계속 반복합니다.

벤치마크 값을 선택하고, 벤치마크 값보다 작은 값을 배열에 담습니다. 벤치마크 값보다 큰 값은 배열에 배치됩니다.

시간 복잡도

O(n*logn)

function quickSort(arr){
  if(arr.length==0){
    return [];
  }
  var left=[];
  var right=[];
  var p=arr[0];
  for(var i=1; i<arr.length; i++){
    if(arr[i]<p){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(p,quickSort(right));
}

위 내용은 제가 모든 사람을 위해 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.

JS Hill 정렬 알고리즘 정보(자세한 튜토리얼)

관련 기사