JavaScript의 퀵 정렬에 대한 자세한 설명

이 글은 JavaScript의 빠른 정렬에 대해 설명합니다. JavaScript의 빠른 정렬에 대해 모르거나 JavaScript의 빠른 정렬에 관심이 있다면 이 글을 살펴보겠습니다. point

퀵 정렬은 정렬 알고리즘에서 분할 정복 아이디어를 적용한 또 다른 전형적인 예입니다. 본질적으로 퀵 정렬은 버블 정렬을 기반으로 한 재귀적분할 정복 방법으로 간주되어야 합니다.

퀵 정렬이라는 이름은 간단하고 투박합니다. 이름을 듣는 순간 그 존재 의미를 알 수 있을 만큼 빠르고 효율적이기 때문입니다. 빅 데이터를 처리하는 가장 빠른 정렬 알고리즘 중 하나입니다. Worst Case의 시간 복잡도는 O(n²)에 도달했지만 대부분의 경우 평균 시간 복잡도가 O(n log n)인 정렬 알고리즘보다 더 나은 성능을 발휘합니다. 둘 중 하나를 알아라. . . 다행히 강박 장애가 재발하여 많은 정보를 확인한 후 마침내 "알고리즘 예술 및 정보학 대회"에서 만족스러운 답을 찾았습니다.

퀵 정렬의 최악의 작동 상황은 예를 들어 O(n²)입니다. 순서 순서의 빠른 정렬. 그러나 상각 예상 시간은 O(n log n)이고 O(n log n) 표기법에 내재된 상수 인자는 매우 작습니다. 이는 복잡도가 안정적이고 O(n log와 같은 병합 정렬보다 훨씬 작습니다. N). 따라서 순서가 약한 대부분의 난수 시퀀스의 경우 빠른 정렬이 항상 병합 정렬보다 낫습니다.

빠른 정렬 애니메이션 데모

빠른 정렬 JavaScript 코드 구현:

function quickSort(arr, left, right) {  
    var len = arr.length,  
        partitionIndex,  
        left = typeof left != 'number' ? 0 : left,  
        right = typeof right != 'number' ? len - 1 : right;  
  
    if (left < right) {  
        partitionIndex = partition(arr, left, right);  
        quickSort(arr, left, partitionIndex-1);  
        quickSort(arr, partitionIndex+1, right);  
    }  
    return arr;}function partition(arr, left ,right) {     //分区操作  
    var pivot = left,                      //设定基准值（pivot）  
        index = pivot + 1;  
    for (var i = index; i <= right; i++) {  
        if (arr[i] < arr[pivot]) {  
            swap(arr, i, index);  
            index++;  
        }          
    }  
    swap(arr, pivot, index - 1);  
    return index-1;}function swap(arr, i, j) {  
    var temp = arr[i];  
    arr[i] = arr[j];  
    arr[j] = temp;}

위 내용은 이 기사의 모든 내용입니다. 잘 모르는 경우에는 양쪽을 직접 구현하면 됩니다. 마스터하기 쉽다!

관련 추천:

Js 버블 정렬 및 퀵 정렬 자세한 설명

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