JavaScript 거품 알고리즘 원리 와 실현 방법 깊이 이해

이 글 의 실례 는 자 바스 크 립 트 거품 알고리즘 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
면접 에서 거품 알고리즘 을 묻 는 면접 관 을 자주 만난다.오늘 총괄 해 보 자.
개념
한 조 의 수가 있 는데,순서대로 두 개의 인접 한 수 를 비교 하 는데,만약 그들의 순서(예 를 들 어 큰 것 에서 작은 것 으로,작은 것 에서 큰 것 으로)가 틀 리 면 그들 을 교환 할 것 이다.
우 리 는 먼저 이 조 의 수가 순서 가 있다 고 가정 한다.그러면 우 리 는 그것 의 규칙 을 찾 아 냈 다.

우 리 는 작은 것 부터 큰 것 까지 순서대로 장방형 을 교환 하여 다음 과 같은 결 과 를 얻 었 다.
1 차 교환 결과:CBAD     교환 횟수:3 회
2 차 교환 결과:BACD     교환 횟수:3 회
3 차 교환 결과:ABCD     교환 횟수:3 회
결과:
1.비교 라운드 수 n-1
2.매번 비교 횟수 n-1
\#\##간단 한 거품 알고리즘

<script>
var arr = [1,2,3,4];
var temp = null;
var m = null;
var n = null;
//   for  
for(var i=0;i<arr.length-1;i++){
//           (         )
    for(var a=0;a<arr.length-1;a++){
        if(arr[a]<arr[a+1]){
        //        
            temp = arr[a+1];
            arr[a+1] = arr[a];
            arr[a] = temp;
        }
        m++;
    }
    n++;
}
console.log(arr);
console.log(m);
console.log(n);
</script>

결 과 를 얻다
[4,3,2,1]     정렬 후
9                      교환 횟수
3                          라운드 수
상술 한 예 에서 중복 교환 한 데이터 가 있 으 니 다시 분석 해 보 자.
1 라운드 교환:
처음
두번째:2,3,1,4
제 3 회:2,3,4,1
2 라운드 교환:
처음:3,2,4,1
두번째:3,4,2,1
세 번 째:3,4,2,1
3 라운드 교환:
처음:4,3,2,1
두번째:4,3,2,1
세 번 째:4,3,2,1
요약:
매 라운드 마다 최대 치 나 최소 치 를 비교 한 후에 다음 라운드 에 서 는 더 이상 비교 할 필요 가 없다.
그래서 한 바퀴 를 비교 할 때마다 한 번 을 적 게 비교한다.2 라운드 때 한 수 는 교환 에 참여 하지 않 았 다.
3 라운드 때 는 두 개의 수가 교환 에 참여 하지 않 았 다.순서대로 유추 하 다.
그래서 상기 코드 를 최적화 시 켰 다.

var arr = [1,2,3,4];
var temp = null;
var m = null;
var n = null;

//   for  
for(var i=0;i<arr.length-1;i++){
    //           (         )
    for(var a=0;a<arr.length-1-i;a++){

        if(arr[a]<arr[a+1]){

    //        
    temp = arr[a+1];
    arr[a+1] = arr[a];
    arr[a] = temp;
    }
    m++;
    }
    n++;
}
console.log(arr);
console.log(m);
console.log(n);

결 과 를 얻다.
[4,3,2,1]정렬 하고.
6 교환 횟수
3 라운드 수
좀 복잡 한 예 를 들 어 보 자.

<script>
var arr = [66,22,23,39,77,25,88];
var temp = null;
var m = null;
var n = null;

//   for  
for(var i=0;i<arr.length-1;i++){
//           (         )

    for(var a=0;a<arr.length-1;a++){

        if(arr[a]<arr[a+1]){

    //        
    temp = arr[a+1];
    arr[a+1] = arr[a];
    arr[a] = temp;
    }
    m++;
    }

    n++;

}
console.log(arr);
console.log(m);
console.log(n);
</script>

결과:
[88, 77, 66, 39, 25, 23, 22]
21.15 번 을 덜 바 꿨 어 요.
6
결 과 는 이미 앞 당 겨 완성 되 었 고 중복 교환 횟수 가 있다.이번에 우 리 는 이번 에는 어떤 요소 도 움 직 이지 않 았 다 는 것 을 비교 해 결 과 를 완성 했다 는 판단 을 내 렸 다.

<script>
var arr = [66,22,23,39,77,25,88,11,33,23];
var temp = null;
var m = null;
var n = null;
var flag = true;

//   for  
for(var i=0;i<arr.length-1;i++){
//           (         )

    flag = true;

    for(var a=0;a<arr.length-1-i;a++){

        if(arr[a]<arr[a+1]){

    //        
    temp = arr[a+1];
    arr[a+1] = arr[a];
    arr[a] = temp;
    flag = false;
    }
    m++;
    }

    n++;
    if(flag){
        break;
        }
    }

console.log(arr);
console.log(m);
console.log(n);
</script>

결과:
[88, 77, 66, 39, 33, 25, 23, 23, 22, 11]
42.39 번 덜 바 꿨 어 요.
7.2 라 운 드 를 덜 주 고 받 았 습 니 다.
관심 있 는 친 구 는 온라인 HTML/CSS/JavaScript 코드 실행 도 구 를 사용 할 수 있 습 니 다.
더 많은 자 바스 크 립 트 관련 내용 에 관심 이 있 는 독 자 는 본 사이트 의 주 제 를 볼 수 있다.,,,,,,,,,,
본 고 에서 말 한 것 이 여러분 의 자 바스 크 립 트 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.

좋은 웹페이지 즐겨찾기