정렬 원리 와 구현 선택 (JS)
3869 단어 데이터 구조
실현 원리
정렬 을 선택 하 는 것 은 원래 주소 비교 정렬 알고리즘 이다.대체적으로 데이터 구조 에서 가장 작은 값 을 찾 아 첫 번 째 에 두 고 두 번 째 작은 값 을 찾 아 두 번 째 에 두 는 것 으로 유추 된다.
구현 코드
function selectionSort(arr) {
if (arr.length < 2) {
return arr;
}
for (var i = 0; i < arr.length - 1; i++) {
// , ,
var minIndex = i;
//
for (var j = i + 1; j < arr.length; j++) {
// arr[minIndex] minIndex
minIndex = arr[minIndex] > arr[j] ? j : i;
// ES6
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
총결산
정렬 을 선택 하 는 데 있어 서 시간 복잡 도:
첫 번 째 내부 순환 비교 N - 1 번, 그 다음 N - 2 번, N - 3 번.
총 비교 횟수 는 (N - 1) + (N - 2) +... + 1, 등차 수열 과 득 (N - 1 + 1) * (N - 1) / 2 = N ^ 2 - N / 2 입 니 다.최고 항 계 수 를 버 리 고 시간 복잡 도 는 O (N ^ 2) 입 니 다.
정렬 알고리즘 이 불안정 하면 원본 시퀀스 를 파괴 할 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.