js를 사용하여 빠른 정렬을 구현하는 방법

실제로 가장 일반적으로 사용되는 정렬 알고리즘이기도 한 퀵 정렬은 빠르고 효율적입니다. 이름처럼 퀵 정렬은 최고의 정렬 알고리즘입니다.

1) 알고리즘 원리

퀵 정렬의 기본 아이디어 : 한 번의 정렬을 통해 독립적인 두 부분으로 정렬할 레코드를 분리하고, 레코드의 한 부분에 대한 키워드를 지정 다른 부분의 키워드보다 더 나은 경우, 레코드의 두 부분을 별도로 정렬하여 전체 시퀀스의 순서를 달성할 수 있습니다.

2) 알고리즘 설명

퀵 정렬은 분할 정복 방식을 사용하여 문자열(리스트)을 두 개의 하위 목록(하위 목록)으로 나눕니다. 특정 알고리즘은 다음과 같이 설명됩니다.

f35d6e602fd7d0f0edfa6f7d103c1b57 "피벗"이라고 하는 요소를 선택합니다.

2cc198a1d5eb0d3eb508d858c9f5cbdb 모든 요소가 피벗 값보다 작도록 배열을 재정렬합니다. 베이스 앞에 배치하면 베이스 값보다 큰 모든 요소가 베이스 뒤에 배치됩니다(양쪽에 동일한 숫자가 들어갈 수 있음). 이 파티션이 종료된 후 베이스는 시퀀스의 중간에 있습니다. 이를 파티션 작업이라고 합니다.

5bdf4c78156c7953567bb5a0aef2fc53 기준 값보다 작은 요소의 하위 배열과 기준 값보다 큰 요소의 하위 배열을 반복적으로 정렬합니다.

3) JavaScript 코드 구현

function paritition(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
function quickSort(arr, low, high) {
  if (low < high) {
    let pivot = paritition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
}
  var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];    
  console.log(quickSort(arr,0,arr.length-1));

4) 알고리즘 분석

최상의 사례: T(n) = O(nlogn )
최악의 시나리오: T(n) = O(n^2)
평균 사례: T(n) = O(nlogn)

상위 10개 알고리즘 목록:

1.JavaScript를 사용하여 다음을 구현합니다. 상위 10개 알고리즘 고전 정렬 알고리즘--버블 정렬

2.JavaScript를 사용하여 상위 10개 고전 정렬 알고리즘 구현--선택 정렬

3 JavaScript를 사용하여 상위 10개를 구현합니다. 고전적인 정렬 알고리즘--정렬 삽입

위 내용은 js를 사용하여 빠른 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!