JS 빠 른 정렬 알고리즘 구현

빠 른 정렬
빠 른 순 서 는 C. A. R. Hoare 가 1962 년 에 제출 했다.그의 기본 사상 은 한 번 의 정렬 을 통 해 정렬 할 데 이 터 를 독립 된 두 부분 으로 나 누 는 것 이다. 그 중에서 일부분 의 모든 데 이 터 는 다른 부분의 모든 데이터 보다 작다. 그 다음 에 이 방법 에 따라 이 두 부분의 데 이 터 를 각각 신속하게 정렬 하고 전체 정렬 과정 을 거 쳐 재 귀적 으로 진행 하여 전체 데 이 터 를 질서 있 는 서열 로 바 꿀 수 있다.
빠 른 정렬 은 거품 정렬 알고리즘 에 대한 개선 입 니 다. 거품 알고리즘 은 독자 들 이 낯 설 지 않 을 것 입 니 다.일상 코딩 생활 에서 즐겨 듣 는 정렬 알고리즘 은 시간 복잡 도 는 O (n * n) 이 고 그 중에서 n 은 배열 의 길이 이다.거품 정렬 과 마찬가지 로 빠 른 정렬 도 원래 주소 정렬 이 므 로 추가 메모리 교환 장치 1 개 만 있 으 면 됩 니 다.
배열 Array [1, N] 를 가정 하고 빠 른 정렬 을 사용 하여 정렬 하 는 핵심 적 인 사 고 는 배열 Array 에서 하나의 값 을 특징 값 으로 하 는 것 이다. 실적 평가 전에 반드시 기준 이 있 는 것 처럼 이 값 은 기준 이다. 모든 것 이 그의 왼쪽 에 있 고 모든 것 이 그의 오른쪽 에 있다. 그러면 배열 은 Array [1, keyIndex - 1], key, Array 로 나 뉜 다.[keyIndex + 1] 을 한 다음 에 Array [1, keyIndex - 1] 과 Array [keyIndex + 1] 를 이 원칙 에 따라 계속 분할 배열 하면 최종 적 으로 얻 은 서열 은 반드시 왼쪽 에서 오른쪽 순서 로 증가 하 는 서열 로 정렬 목적 을 완성 할 것 이다.
다음은 알고리즘 절 차 를 간단하게 설명 합 니 다.

1. 배열 의 마지막 값 을 특징 값 으로 한다

2. 배열 의 시작 값 을 설정 하 는 위 치 는 왼쪽 탐색 지침 이 고 배열 의 마지막 위 치 는 오른쪽 탐색 지침

이다.

3. 왼쪽 에서 탐문 을 하고 값 이 특징 치보다 작 으 면 지침 위치 가 오른쪽으로 이동 하여 첫 번 째 특징 치보다 큰 값 을 찾 을 때 까지 멈춘다

4. 오른쪽 에서 탐문 을 하고 값 이 특징 치보다 크 면 바늘 위치 가 왼쪽으로 이동 하여 첫 번 째 가 특징 치보다 작은 값 을 찾 을 때 까지 멈춘다

5. 왼쪽 포인터 가 검색 할 배열 범 위 를 초과 하 는 지 판단 하고 초과 하지 않 으 면 왼쪽 포인터 위치의 수치 와 특징 치 를 교환 합 니 다

6. 왼쪽 포인터 가 멈 춘 위 치 를 배열 의 분리 위치 로 하고 배열 을 2 단 으로 나 누 어 한 단락 씩 계속 처리

코드
(아래 코드 는 본인 테스트 를 거 쳐 nodejs 환경 으로 실행 할 수 있 습 니 다)

/**
 * Created by cluo on 2017/2/22.
 */
var arr = [5,2,4,6,1,3];
//var arr = [6,5,4,3,2,1];

/**
 *        ，       ，      ，      
 * @param arr :     
 * @param start :         
 * @param end :         
 * */
function partition(arr,start,end) {
    //            
    if(start >= end){
        return;
    }
    //                     
    var key = arr[end];

    //         
    var left = start;
    var right = end - 1;

    //          ，       
    while (left <= right){
        //                     
        while(arr[left] <= key){
            left++;
        }
        //                     
        while(arr[right] > key){
            right--;
        }
        //                    
        if(left >= right){
            break;
        }else{
            //                      
            exchange(arr,left,right);
        }
    }

    //        ，              
    if(left <= end){
        exchange(arr,left,end);
        //                 
        partition(arr,start,left - 1);
        partition(arr,left + 1,end);
    }else{
        //          ，              
        partition(arr,start,end - 1);
    }

}
/**
 *       2      
 * */
function exchange(arr,i,j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
/**
 *             
 * @param arr :       
 * @param flag :   or  
 * */
const quickSort = function(arr) {
    partition(arr,0,arr.length - 1);
};
//    
quickSort(arr);

빠 른 정렬 알고리즘 은 현재 비교적 빠 른 정렬 알고리즘 이 고 공간 에 대한 점용 이 비교적 적 지만 불안정 하 며 알고리즘 의 효율 은 소스 데이터 의 특징 에 큰 영향 을 받는다.