JavaScript 의 정렬 알고리즘 코드

정렬 근거 로 하 는 데이터 항목 을'정렬 코드',즉 데이터 요소 의 핵심 코드 라 고 합 니 다.찾기 편 하도록 컴퓨터 의 데이터 시트 는 키 코드 에 따라 질서 가 있 기 를 바 랍 니 다.예 를 들 어 질서 표 의 절반 을 찾 으 면 검색 효율 이 비교적 높다.그리고 이 진 트 리,B-트 리 와 B+트 리 의 구조 과정 은 바로 정렬 과정 이다.만약 에 관건 코드 가 주 관건 코드 라면 임의로 정렬 을 기다 리 는 서열 에 대해 정렬 을 거 친 후에 얻 은 결 과 는 유일 하 다.만약 에 키 코드 가 차 키 코드 라면 정렬 결과 가 유일 하지 않 을 수 있 습 니 다.이것 은 같은 키 코드 의 데이터 요 소 를 가지 기 때 문 입 니 다.이런 요 소 는 정렬 결과 에서 그들의 위치 관계 와 정렬 전에 유지 할 수 없습니다.만약 에 임의의 데이터 요소 서열 에 대해 특정한 정렬 방법 을 사용 하여 관건 적 인 코드 에 따라 정렬 합 니 다.만약 에 같은 관건 적 인 코드 요소 간 의 위치 관계 가 있 으 면 정렬 전과 정렬 후 일치 하 며 이 정렬 방법 이 안정 적 이 라 고 합 니 다.일치 하지 않 는 정렬 방법 을 불안정 이 라 고 한다.정렬 은 두 가지 로 나 뉜 다.내부 정렬 과 외부 정렬 이다.내 정렬:정렬 대기 열 이 메모리 에 완전히 저장 되 어 있 는 정렬 과정 을 말 합 니 다.큰 요소 서열 에 적합 하지 않 습 니 다.외부 정렬:정렬 과정 에서 외부 메모리 에 접근 해 야 하 며 충분 한 요소 서열 을 말 합 니 다.메모리 에 완전히 넣 을 수 없 기 때문에 외부 정렬 만 사용 할 수 있 습 니 다.현재 3 가지 정렬 알고리즘 을 붙 인 자바 스 크 립 트 가 구현 되 었 습 니 다.우선 가장 간단 한 것 은 개인 이 모두 할 수 있 는 거품 서열 이다.더 이상 말 하지 않 겠 습 니 다.바로 코드 를 붙 입 니 다

 
/** @name      
* @lastmodify 2010/07/13 
* @desc      
    O(n*n) 
*/ 
function BubbleSort(list){ 
var len = list.length; 
var cl,temp; 
while(len--){ 
cl = list.length; 
while(cl--){ 
if(list[cl]>list[len] && cl < len){ 
temp = list[len]; 
list[len] = list[cl]; 
list[cl] = temp; 
} 
} 
} 
return list; 
} 

그 다음 에 가장 흔히 볼 수 있 는 빠 른 순위 입 니 다.면접 에서 대체적으로 물 어 봅 니 다

 
/** @name      
* @lastmodify 2010/07/14 
* @desc      
      O(n*n); 
      O(nlogn) 
*/ 
function QuickSort(list){ 
var i = 0; 
var j = list.length; 
var len = j; 
var left; 
var right; 
var k = findK(i , j); 
if(k != 0){ 
var leftArr = []; 
var rightArr = []; 
var midArr = [list[k]]; 
while(len--) { 
if(len != k){ 
if(list[len] > list[k]){ 
rightArr.push(list[len]); 
} 
else{ 
leftArr.push(list[len]); 
} 
} 
} 
left = QuickSort(leftArr); 
right = QuickSort(rightArr); 
list = left.concat(midArr).concat(right); 
} 
return list; 
} 

function findK(i,j){ 
//          
return Math.floor((i + j) / 2); 
} 

빠 른 정렬 의 주요 사상 은 바로 분 치 법 으로 정렬 된 서열 을 2 조각 으로 나 누 어 정렬 의 복잡 도 를 낮 추 는 것 이다.재 귀적 인 유용 도 빠 른 정렬 의 정교 한 점 이다.이전 예 에서 먼저 findK 함 수 를 사용 하여'참조 요소'를 찾 고 다른 요 소 는 순서대로 이 요소 와 비교 하 며 모든 큰 것 은 하나의 집합 에 넣 고 작은 것 은 다른 집합 에 넣 은 다음 에 각각 두 개의 집합 을 정렬 합 니 다.빠 른 정렬 의 효율 은 주로 findK 함수 의 실현 과 정렬 대기 요소 의 질서 정도 에 달 려 있다.따라서 빠 른 정렬 은 불안정한 정렬 알고리즘 이다.그러나 빠 른 정렬 은 여전히 비교 에 기반 한 정렬 알고리즘 이다.모든 비교 에 기반 한 정렬 알고리즘 은 하나의 특징 이 있 는데 그것 이 아무리 최적화 되 더 라 도 하나의 요소 집합 에 대한 평균 정렬 시간 은 항상 이 집합 요소 의 수량 이 증가 함 에 따라 증가한다.비교 적 인 정렬 이 아니 라 이 단점 을 잘 극복 하고 정렬 시간 복잡 도 를 수량 과 무관 한 안정 치 로 만 들 려 고 한다.그 중에서 도 대표 적 인 것 은 통 정렬 이다.우선 그것 의 자 바스 크 립 트 실현 을 보 세 요

 
/** @name     
* @author lebron 
* @lastmodify 2010/07/15 
* @desc       
*/ 
function BucketSort(list) { 
var len = list.length; 
var range = findMax(list); 
var result = [], 
count = []; 
var i,j; 
for (i = 0; i < range; i++) { 
count.push(0); 
} 

for ( j = 0; j < len; j++) { 
count[list[j]]++; 
result.push(0); 
} 
for (i = 1; i < range; i++) { 
count[i] = count[i-1] + count[i]; 
} 
for (j = len - 1; j >= 0; j--) { 
result[count[list[j]]] = list[j]; 
count[list[j]]--; 
} 
return result; 
} 

function findMax(list) { 
return MAX; 
} 

통 정렬 의 실현 에서 하나의 findMax 함 수 를 사용 하여 큰 배열 의 범 위 를 확정 하 는 것 을 볼 수 있 습 니 다.여 기 는 상수 MAX 로 직접 대체 합 니 다.먼저 MAX 길이 의 큰 배열 count 를 초기 화 합 니 다.정렬 집합 에 있 는 값 을 대응 하 는 위치 에 넣 습 니 다.예 를 들 어 하나의 요소 값 이 24 이면 count 의 24 위 는 1 로 표시 되 고 result 배열 의 길 이 는+1 입 니 다.count 배열 에서 1 로 표 시 된 요소 의 위 치 를 계산 하여 전체 count 배열 에서 1 로 표 시 된 순 위 를 계산 합 니 다.이때 count 배열 에서 n 번 째 요소 의 값 은 정렬 후의 위치 이 고 n 은 이 정렬 후의 이 위치 에 대응 하 는 값 입 니 다.따라서 마지막 으로 count 배열 의 키 값 을 결과 배열 에 거꾸로 표시 하면 됩 니 다.통 순 서 는 이러한 사상 을 교묘 하 게 이용 했다.만약 에 하나의 요소 가 하나의 집합 에서 n 번 째 로 크다 면 n 번 째 로 해 야 한다.앞 자리 나 뒤 자리 가 그것 보다 큰 지 작은 지 에 관심 을 가 질 필요 가 없다(비교 할 필요 가 없다).분명 한 것 은 실제 상황 에서 정렬 된 집합 요소 의 값 범 위 는 이 집합 요소 의 수량 보다 훨씬 클 수 있 기 때문에 해당 하 는 커 다란 공간의 배열 도 분배 해 야 한다.따라서 통 정렬 의 흔 한 장면 은 밖에서 정렬 하 는 것 이다.관심 있 는 학생 은 세 가지 정렬 이 서로 다른 수량 급 에서 소모 되 는 시간 을 테스트 할 수 있다.