JS 삽입 정렬 실현
2476 단어 JS 알고리즘
3, 알고리즘 분석
만약 목표 가 오름차 순 정렬 이 라면, 삽입 정렬 은 가장 좋 은 상황 과 최 악의 상황 두 가지 가 있다.가장 좋 은 상황 은 서열 이 이미 오름차 순 으로 배열 되 었 다 는 것 이다. 그러면 n - 1 번 만 비교 해 야 한다. 서열 이 내림차 순 으로 배열 되면 비교 횟수 는 n (n - 1) / 2 이 고 할당 작업 은 비교 횟수 에서 (n - 1) 번 을 뺀 것 이다.평균 적 으로 삽입 알고리즘 시간 복잡 도 는 O (n ^ 2) 이 고 공간 복잡 도 는 O (1) 입 니 다.n 이 비교적 클 때 시간 복잡 도가 너무 크기 때문에 정렬 을 삽입 하 는 것 은 빅 데이터 양의 정렬 에 적합 하지 않다 는 것 을 알 수 있다. 일반적으로 작은 데이터 양의 정렬 에 적합 하 다. 예 를 들 어 n < 1000, 삽입 정렬 도 빠 른 배열 의 보충 으로 하고 n < 8 시 에 삽입 을 사용 하지 않 으 면 빠 른 배열 을 사용한다.
시간 복잡 도 는 o (n) 가 가장 좋 고 최 악 은 (n ^ 2) 평균 o (n ^ 2) 이다. 공간 복잡 도 o (1) 안정 4, 코드 구현
function insertSort(arr) {
var len =arr.length;
for (var i=1;i=0 && arr[j]>temp) { //
arr[j+1]=arr[j]; // ，
j--;
}
arr[j+1]=temp;
}
return arr
} 5. 고찰 점, 중점 과 고찰 빈도 분석 삽입 은 효율 이 높 지 않 고 속도 가 느 리 며 큰 문제 의 고찰 이 적 고 빈도 가 높 지 않 으 며 시간 복잡 도, 공간 복잡 도, 이동 횟수 에 대한 고찰 에 중심 을 둔다.
2. 2 분 삽입 정렬 1. 알고리즘 소개 2 분 삽입 정렬 시 삽입 정렬 에 직접 변경 하 는 알고리즘 입 니 다. 직접 삽입 과 가장 큰 차이 점 은 삽입 위 치 를 찾 을 때 2 분 검색 방식 을 사용 하 는 것 입 니 다. 2. 알고리즘 설명 1. 첫 번 째 요소 부터 이 요소 가 정렬 되 었 다 고 생각 합 니 다.2. 다음 요 소 를 꺼 내 정렬 된 시퀀스 에서 2 분 동안 첫 번 째 큰 수의 위 치 를 찾 습 니 다. 3. 요 소 를 이 위치 에 삽입 한 후 4. 상기 두 단 계 를 반복 합 니 다.
3, 알고리즘 분석
삽입 위치 찾기 방법 만 개선 되 었 기 때문에 공간 복잡 도 는 여전히 O (1) 입 니 다. 각 기록 을 삽입 하려 면 logi 회 를 찾 아야 하고 최대 i + 1 회 이동 해 야 합 니 다. 따라서 가장 좋 은 상황 시간 복잡 도 는 O (nlogn) 이 고 최 악의 상황 과 평균 상황 은 O (n ^ 2) 입 니 다.
4, 코드 구현
function binaryInsertSort(arr) {
var len =arr.length;
for (var i=1;i=left;j--){
arr[j+1]=arr[j];
}
arr[left]=key;
}
return arr;
}
5. 고찰 점, 중점, 빈도 분석
직접 삽입 하 는 것 과 마찬가지 로 2 분 삽입 효율 은 여전히 높 지 않 을 수 있다. 이것 은 초기 서열 에 의존 하지만 2 분 검색 사상 은 좋 은 사상 이 고 중점적으로 파악 하 는 것 이다.
좋은 웹페이지 즐겨찾기
