집 > 기사 > 웹 프론트엔드 > JavaScript가 빠른 정렬을 구현하는 방법에 대한 자세한 코드 설명

JavaScript가 빠른 정렬을 구현하는 방법에 대한 자세한 코드 설명

零到壹度원래의: 2018-04-10 10:27:442299검색

이 글의 내용은 JavaScript로 빠른 정렬을 구현하는 방법을 공유하는 것입니다. 이는 특정 참조 값을 가지고 있습니다. 도움이 필요한 친구는 이를 참조할 수 있습니다.

루안 이펑 선생님의 블로그에서 우연히 빠른 정렬 알고리즘을 보았습니다. 각 루프는 두 개의 추가 배열을 생성하며, 이는 데이터 양이 클 경우 많은 추가 메모리를 차지합니다. 그러나 배열은 참조 유형이며 수정될 수 있습니다. 원본 배열 자체를 직접 조작하여 메모리를 절약할 수 있습니다.

빠른 정렬 방법의 핵심은 값을 선택하고 전체 배열을 두 부분으로 나누는 것입니다. 왼쪽의 작은 부분과 오른쪽의 큰 부분입니다.

//该函数的主要目的是交换数组中两个元素的位置
function swap(arr, index1, index2) {

    let data = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = arr[index1];

    //数组是引用类型，允许修改原数组。
}

//选取随机值，将数组分为两部分
function partition(arr, start, end) {
    let keyIndex = end,
        key = arr[keyIndex]; //将随机值(以后称key值)定为最后一个数，也可以真的随机选取，见下一行
    // let keyIndex = Math.floor(Math.random() * (end - start)) + start;

    let i = start,
        j = end,
        order = true;
    //当order为true时正向筛选，当order为false时逆向筛选
    //先从正向开始，因为我们把key值保存到了数组的结尾处。
    while(i != j) {
        if(order) {
            //正向筛选
            if (arr[i]>key) {
                swap(arr, i, j); //将大于key的数字和key进行交换
                order = false;
            } else {
                i++;
            }

        } else {
            //逆向筛选
            if(arr[j]<key) {
                swap(arr, i, j); //将小于key的数字和key进行交换
                order = true;
            } else {
                j--;
            }
        }
    }
    return i;//返回key值最终的位置
}

입니다. 실제로 i 위치에는 항상 j 위치에 키 값이 저장되어 있으며, 그 이후에는 그보다 크거나 작은 값으로 교환됩니다. 그런 다음 단방향 그룹화 방법으로 작성할 수도 있습니다.

function partition2(arr, start, end) {
    let keyIndex = end,
        key = arr[end];
    let i = start -1,
        j = start;
    for (;j<end;j++) {
        if (arr[j]< key) {
        // i位置的值永远比key值小
            i++;
            if (i != j) {
                swap(arr, i, j);
            }
        }
    } 
    ++i;
    swap(arr, i, end);

    return i; //返回key值最终的位置
}

다음으로 그룹화 함수를 재귀적으로 호출하여 전체 배열을 정렬합니다.

function quickSort(arr, start, end) {
    if (start == end) return;
    let index = partition(arr, start, end);
    if (index > start){
        quickSort(arr, start, index-1);
    }
    if (index<end) {
        quickSort(arr, index+1, end);
    }
}

JavaScript가 빠른 정렬을 구현하는 방법에 대한 자세한 코드 설명

관련 기사