JS는 Hill 정렬을 구현합니다.-JS 튜토리얼-php.cn

JS는 Hill 정렬을 구현합니다.

不言

풀어 주다： 2018-07-07 17:39:45

원래의

1872명이 탐색했습니다.

이 글에서는 JS에서 Hill 정렬을 구현하는 방법을 주로 소개합니다. 이제 이를 공유합니다. 도움이 필요한 친구들이 참고할 수 있습니다.

Hill 정렬은 본질적으로 An입니다. 삽입 정렬이지만 시퀀스는 동일한 간격으로 그룹화되고 각 그룹에서 삽입 정렬이 수행됩니다. 이 최적화는 원래 시간 복잡도를 O(nlogn)로 줄입니다.

기본 아이디어

Hill 정렬은 배열을 일정한 간격으로 그룹화한 다음 각 그룹에서 삽입 정렬을 수행한 다음 점차적으로 간격을 줄이고 각 그룹에서 삽입을 수행하는 것입니다. 정렬... 간격이 1이 될 때까지 삽입 정렬을 한 번 수행한 후 종료됩니다.

그럼 문제는 간격을 얼마나 크게 하고 어떻게 줄여야 하는가 하는 것입니다. 일반적으로 초기 간격은 시퀀스 길이의 절반인 간격 = 길이/2로 취하고 간격 = 간격/2의 형태로 줄입니다. 전체 프로세스는 아래에 자세히 설명되어 있습니다.

원래 배열 배열은 다음과 같습니다.

JS는 Hill 정렬을 구현합니다.

먼저 간격을 간격 = 길이/2로 취합니다. = 4, 그리고 배열을 다음 4개 그룹으로 나누고 각 그룹별로 삽입 정렬을 수행합니다. 정렬, 각 그룹이 더 작습니다. 요소가 상대적으로 앞쪽으로 이동했습니다(이 상태를 n 정렬이라고 할 수 있습니다. 즉, 그룹화가 n을 간격으로 정렬되어 있음). 후속 정렬에 더 도움이 됩니다. 그런 다음 간격 = 간격/2 = 2로 계속 그룹화하고 각 그룹에 대해 삽입 정렬을 구현합니다. gap = gap/2 = 1, 즉 모든 요소가 그룹을 형성하고 삽입 정렬 알고리즘이 완료됩니다.

JS는 Hill 정렬을 구현합니다.

# 🎜🎜##🎜 🎜#코드 구현

내부 루프에 사용되는 삽입 정렬은 기본적으로 각 이동의 단계 크기가 1이 아닌 간격이 된다는 점을 제외하면 일반 삽입 정렬과 동일합니다. # 🎜🎜#

// shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
    for(let i = gap; i  0; j -= gap) {
        if(temp >= arr[j-gap]) {
          break;
        }
        arr[j] = arr[j-gap];
      }
      arr[j] = temp;
    }
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));

로그인 후 복사