offer 대작 전 - JS 정렬 알고리즘 실현

1 년 에 한 번 있 는 가을 모집 이 시작 되 었 습 니 다.각 회사 의 기초 에 대한 연구 가 점점 많아 지고 있 습 니 다. 특히 컴퓨터 기초 에 대한 지식 은 독학 전단 의 학생 들 에 게 학습 전단 의 여가 시간 에 일자 리 를 구 하 는 시기 가 다가 오고 있 습 니 다. 컴퓨터 기 초 를 보충 하고 싶 은 학생 들 에 게 는 여유 가 있 고 힘 이 부족 합 니 다. 전단 에서 알고리즘 을 접 하지 않 는 다 고 하지만 여러분 (and me) 을 위해더 좋 은 일자 리 를 찾 을 수 있 고 자주 고찰 하기 쉬 운 알고리즘 을 배 워 야 합 니 다. 그래서 저 는 최근 에 배 운 지식 을 공유 하여 기록 하여 다른 친구 들 과 이 글 을 참고 하도록 하 겠 습 니 다. 주로 상비 된 배열 알고리즘 을 소개 하 는 것 입 니 다.
1. 거품 정렬 거품 정렬 의 사상 은 순서대로 크기 를 비교 한 다음 에 위치 에서 크기 를 교환 하 는 것 이다.다음은 알고리즘 으로 이 루어 지 겠 습 니 다.

function bubble(arr) {  
    for(var i = 0,len = arr.length; i < len - 1; i++) {
        for(var j=i+1; j//                 
          if(arr[i]>arr[j]) {
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

이것 이 바로 거품 정렬 의 실현 과정 이다. 사실은 순환 비교 한 다음 에 위치 상의 교환 을 하여 정렬 의 목적 을 달성 하 는 것 이다.
2. 빠 른 정렬, 빠 른 정렬 도 매우 고전적 인 정렬 입 니 다. 제 가 이해 하 는 바 에 의 하면 빠 른 정렬 사상 은 이분법 과 같 습 니 다. 2 분 의 1, 4 분 의 1, 그리고 8 분 의 1..........................................(참고 값) 그 다음 에 두 조각 으로 나 누 었 습 니 다. 하 나 는 모두 중간 값 보다 작 습 니 다. 하 나 는 중간 값 보다 큽 니 다. 그러면 우 리 는 첫 번 째 정렬 을 완성 한 다음 에 우 리 는 첫 번 째 정렬 함 수 를 재 귀적 으로 호출 하여 똑 같은 조작 을 한 다음 에.............................................

function quick(arr) {
    //       1，    
    if(arr.length <= 1) {
        return arr;
    }

    //     ，   ，   
    var lessArr = [];
    var moreArr = [];
    var consult = arr[0];
    for(let i = 1,len = arr.length; i < len; i++) {
        if(arr[i]>consult) {
            moreArr.push(arr[i]);
        }else{
            lessArr.push(arr[i]);
        }
    }

    //    ，          
    return [].concat(quick(leftArr)[q],quickSort(rightArr));
}

3. 정렬 을 선택 하면 거품 정렬 과 비슷 한 느낌 이 듭 니 다. 거품 정렬 은 두 위 치 를 조회 하지 않 고 교환 하 는 것 과 차이 가 있 습 니 다. 정렬 을 선택 하면 현재 위치 보다 작은 숫자 를 찾 을 때 교환 하 는 것 을 알 수 있 습 니 다.

function select(arr) {
    var minIndex, 
        temp;
    for(var i = 0, len = arr.length; i < len-1; i++) {
        minIndex = i;
        for(var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {   
                minIndex = j;                
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

4. 정렬 삽입 정렬 삽입 정렬 은 현재 값 의 이전 값 이 존재 하 는 전제 에서 계속 비교 하고 작 으 면 위 치 를 교환 하 며 크 면 끝 납 니 다.

function insertion(arr) {
    var pre, 
        cur;
    for (var i = 1, len = arr.length; i < len; i++) {
        pre = i - 1;
        cur = arr[i];
        while(pre >= 0 && arr[pre] > cur) {
            arr[pre + 1] = arr[pre];
            pre--;
        }
        arr[pre + 1] = cur;
    }
    return arr;
}

이것 은 현재 고찰 이 비교적 많은 몇 가지 정렬 방법 이다. 물론 정렬 방법 은 이 몇 가지 만 먼저 열거 하 는 것 이 아니 라 자신 이 복습 하기에 편리 할 뿐만 아니 라 다른 정렬 사상 도 계속 공부 할 것 이다.