JavaScript 거품 알고리즘 원리 와 실현 방법 깊이 이해
4244 단어 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 코드 실행 도 구 를 사용 할 수 있 습 니 다.
더 많은 자 바스 크 립 트 관련 내용 에 관심 이 있 는 독 자 는 본 사이트 의 주 제 를 볼 수 있다.,,,,,,,,,,
본 고 에서 말 한 것 이 여러분 의 자 바스 크 립 트 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
기초 정리 - 1문자 (String) 숫자 (Number) 불린 (Boolean) null undefined 심볼 (Symbol) 큰정수 (BigInt) 따옴표로 묶어 있어야 함 Not-A-Number - 숫자 데이터 / 숫자로 표...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.