JS 정렬 알고리즘 의 힐 정렬 과 빠 른 정렬 실현 방법

본 고 는 JS 정렬 알고리즘 의 힐 정렬 과 빠 른 정렬 실현 방법 을 실례 로 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
힐 정렬:
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));
}

빠 른 정렬 은 대형 데이터 집합 에 적합 하 며,작은 데이터 집합 을 처리 할 때 오히려 성능 이 떨어진다.
PS:정렬 에 관 한 프 리 젠 테 이 션 도 구 를 추천 합 니 다.참고 하 시기 바 랍 니 다.
온라인 애니메이션 프레젠테이션 삽입/선택/거품/병합/힐/빠 른 정렬 알고리즘 프로 세 스 도구:
http://tools.jb51.net/aideddesign/paixu_ys
자 바스 크 립 트 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 고 에서 말 한 것 이 여러분 의 자 바스 크 립 트 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.

좋은 웹페이지 즐겨찾기