javascript 기본 상용 정렬 알고리즘 분석

비고:내용 은 대부분 인터넷 에서 복사 되 고 코드 는 자신 이 직접 쓴다.지식의 온고지신 만 하 는 것 은 오리지널 이 아니다.
1.거품 정렬(버 블 정렬)
(1)알고리즘 설명
거품 정렬 은 간단 한 정렬 알고리즘 이다.그것 은 정렬 할 수열 을 반복 적 으로 방문 하여 한 번 에 두 요 소 를 비교 한 적 이 있 으 며,만약 그들의 순서 가 틀 리 면 그것들 을 교환 할 것 이다.방문 수열 작업 은 더 이상 교환 이 필요 하지 않 을 때 까지 반복 적 으로 진행 된다.즉,이 수열 은 이미 정렬 이 완료 되 었 다 는 것 이다.이 알고리즘 의 이름 은 작은 요소 일수 록 교환 을 통 해 서서히 수열 의 맨 위로 떠 오 르 기 때문이다.
(2)알고리즘 설명 과 실현
구체 적 인 알고리즘 설명 은 다음 과 같다.
<1>.비교적 인접 한 원소.첫 번 째 가 두 번 째 보다 크 면 두 개 를 교환 합 니 다.<2>.모든 인접 요소 에 대해 똑 같은 작업 을 합 니 다.첫 번 째 쌍 부터 마지막 쌍 까지 마지막 요소 가 가장 큰 숫자 일 것 입 니 다.<3>.모든 요 소 를 대상 으로 이상 의 절 차 를 반복 합 니 다.마지막 을 제외 하고<4>.정렬 이 완 료 될 때 까지 1~3 절 차 를 반복 합 니 다.
JavaScript 코드 구현:

거품 정렬 개선:모든 정렬 에서 마지막 으로 교환 하 는 위 치 를 기록 하 는 상징적 변수 pos 를 설정 합 니 다.pos 위치 이후 의 기록 이 모두 바 뀌 었 기 때문에 다음 정렬 을 진행 할 때 pos 위 치 를 스 캔 하면 됩 니 다.
개선 후 알고리즘 은 다음 과 같 습 니 다.

전통 적 인 거품 정렬 에서 모든 정렬 작업 은 하나의 최대 치 나 최소 치 만 찾 을 수 있 습 니 다.우 리 는 모든 정렬 에서 정방 향 과 역방향 으로 거품 을 일 으 키 는 방법 을 이용 하여 한 번 에 두 개의 최종 치(최대 자 와 최소 자)를 얻 을 수 있 고 정렬 횟수 를 거의 절반 으로 줄 일 수 있 습 니 다.
개 선 된 알고리즘 은:

세 가지 알고리즘 의 운행 시간 은 다음 과 같다.

운행 결 과 를 보면 시간 복잡 도가 더 낮 고 시간 이 더 짧 아진 것 을 알 수 있다.직접 시도 해 보 세 요.실행 할 때 세 가지 알고리즘 을 한 파일 에 써 서 실행 하 는 것 이 좋 습 니 다.그렇지 않 으 면 브 라 우 저 등 으로 인해 오차 가 발생 할 수 있 습 니 다.
거품 정렬 의 동적 그림 설명:

(3)알고리즘 분석
최 적 상황:T(n)=O(n)
입력 한 데이터 가 정렬 되 었 을 때
최 악의 경우:T(n)=O(n2)
입력 한 데이터 가 역순 일 때
평균 상황:T(n)=O(n2)
2.정렬 선택(선택 정렬)
가장 안정 적 인 정렬 알고리즘 중 하 나 를 표현 합 니 다.어떤 데이터 가 들 어가 도 O(n)이기 때 문 입 니 다.²)시간 복잡 도..................................................................유일한 장점 은 아마도 추가 메모리 공간 을 차지 하지 않 는 것 일 것 이다.이론 적 으로 정렬 을 선택 하 는 것 도 평소에 일반인 들 이 가장 많이 생각 하 는 정렬 방법 일 것 이다.
(1)알고리즘 안내
정렬 선택(Selection-sort)은 간단 하고 직관 적 인 정렬 알고리즘 입 니 다.그의 작업 원리:먼저 정렬 되 지 않 은 시퀀스 에서 최소(큰)요 소 를 찾 아 정렬 된 시퀀스 의 시작 위치 에 저장 한 다음 에 나머지 정렬 되 지 않 은 요소 에서 최소(큰)요 소 를 계속 찾 은 다음 에 정렬 된 시퀀스 의 끝 에 놓 습 니 다.모든 요소 가 정렬 될 때 까지 유추 합 니 다.
(2)알고리즘 설명 과 실현
n 개 기록 의 직접 선택 정렬 은 n-1 번 의 직접 선택 정렬 을 통 해 질서 있 는 결 과 를 얻 을 수 있 습 니 다.구체 적 인 알고리즘 설명 은 다음 과 같다.
<1>.초기 상태:무질서 구역 은 R[1.n]이 고 질서 구역 은 비어 있 습 니 다.<2>.i 번 째 정렬(i=1,2,3...n-1)을 시작 할 때 현재 질서 구역 과 무질서 구역 은 각각 R[1.i-1]과 R(i.n)이다.이 순 서 는 현재 무질서 구역 에서-키워드 가 가장 작은 기록 R[k]을 선택 하여 무질서 구역 의 첫 번 째 기록 R 과 교환 하여 R[1.i]과 R[i+1.n)을 각각 기록 개수 가 1 개 증가 하 는 새로운 질서 구역 과 기록 개수 가 1 개 감소 하 는 새로운 무질서 구역 으로 바 꿉 니 다.<3>.n-1 번 이 끝나 고 배열 이 질서 화 되 었 습 니 다.
Javascript 코드 구현:


(3)알고리즘 분석
최 적 상황:T(n)=O(n2)최 악의 상황:T(n)=O(n2)평균 상황:T(n)=O(n2)
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.