JavaScript_javascript 기술의 알고리즘 코드 정렬

정렬의 기초로 사용되는 데이터 항목을 "정렬 코드"라고 하며, 이는 데이터 항목의 키 코드입니다. 검색을 용이하게 하기 위해 일반적으로 컴퓨터의 데이터 테이블이 키 코드별로 정렬되어 있기를 바랍니다. 예를 들어, 정렬된 목록의 절반 검색은 검색 효율성이 더 높습니다. 또한 이진 정렬 트리, B-트리 및 B-트리의 구성 프로세스는 정렬 프로세스입니다. 키가 기본 키인 경우 정렬할 시퀀스에 대해 정렬 후 얻은 결과는 고유합니다. 키가 보조 키인 경우 정렬 결과는 동일한 키를 가진 데이터 요소가 고유하지 않을 수 있습니다. 정렬 결과에서는 이러한 요소 간의 위치 관계가 정렬 전과 같이 유지될 수 없습니다.
데이터 요소의 순서에 대해 특정 정렬 방법을 사용하면 키를 기준으로 정렬됩니다. 정렬 전후에 동일한 키를 가진 요소 간의 위치 관계가 일관되면 이 정렬 방법이 안정적이라고 합니다. 일관성을 유지할 수 없는 정렬 방법을 불안정하다고 합니다.
정렬은 내부 정렬과 외부 정렬의 두 가지 범주로 나뉩니다.
내부 정렬: 정렬할 열을 메모리에 완전히 저장하는 정렬 프로세스를 말하며, 너무 크지 않은 요소 순서에 적합합니다.
외부 정렬: 정렬 프로세스 중에 외부 메모리에 액세스해야 함을 의미합니다. 충분히 큰 요소 시퀀스를 메모리에 완전히 넣을 수 없기 때문에 외부 정렬만 사용할 수 있습니다.

이제 3가지 정렬 알고리즘의 JavaScript 구현을 게시하세요.

첫 번째는 가장 간단한 방법으로 누구나 다 아는 버블정렬입니다. 별로 할말 없고 그냥 코드 붙여넣기

코드 복사 코드는 다음과 같습니다.

/** @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]; 목록[len] = 목록[cl];
목록[cl] = 임시
}
}
목록 반환
}

>그럼 마지막 공통 퀵정렬은 기본적으로 면접에서 물어봅니다.

코드 복사 코드는 다음과 같습니다. /**@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; 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); = QuickSort( rightArr);
list = left.concat(midArr).concat(right);
}
return list

function findK(i,j) {
//기본적으로 중간 위치 찾기
return Math.floor((i j) / 2)
}


빠른 정렬의 주요 아이디어는 정렬할 분할 정복 방식 시퀀스를 2개의 블록으로 나누어 정렬의 복잡성을 줄입니다. 재귀를 영리하게 사용하는 것도 퀵 정렬의 미묘함입니다. 이전 예에서는 먼저 findK 함수를 사용하여 "참조 요소"를 찾은 다음 다른 요소를 이 요소와 차례로 비교하고, 그보다 큰 모든 요소를 ​​하나의 세트에 넣고, 그보다 작은 요소를 다른 세트에 넣습니다. . 두 개의 컬렉션을 정렬합니다. 퀵 정렬의 효율성은 주로 findK 함수의 구현과 정렬할 요소의 순서에 따라 달라집니다. 따라서 퀵정렬은 불안정한 정렬 알고리즘입니다.

그러나 퀵 정렬은 여전히 ​​비교 기반 정렬 알고리즘입니다. 모든 비교 기반 정렬 알고리즘의 한 가지 특징은 아무리 최적화하더라도 집합의 요소 수가 증가함에 따라 요소 집합의 평균 정렬 시간이 항상 증가한다는 것입니다. 비비교 정렬은 이러한 단점을 매우 잘 극복하여 정렬 시간 복잡도를 숫자와 무관하게 안정적인 값으로 만들려고 합니다. 그 대표적인 것 중 하나가 버킷 정렬(Bucket Sorting)이다. 먼저 JavaScript 구현을 살펴보겠습니다.

코드 복사


코드는 다음과 같습니다.

/**@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 count.push(0)>}

for ( j = 0; j count[list[j]]
result.push(0)
}
for ( i = 1; i count[i-1] count[i]
for (j = len - 1; j >= 0; j--) {
결과[count[list[j]]] = 목록[j]
count[list[j]]--
결과 반환; 🎜>}

function findMax(list) {
return MAX;
}


보시다시피, 버킷 정렬 구현에서 findMax는 여전히 큰 배열의 범위를 결정하기 위해 함수를 사용했지만 여기서는 상수 MAX로 직접 대체되었습니다. 먼저 길이가 MAX인 큰 배열 수를 초기화합니다. 예를 들어 값이 24인 요소가 있으면 count의 24번째 비트가 1로 표시되고 결과 배열의 길이는 1이 됩니다. 그런 다음 개수 배열에서 1로 표시된 요소의 위치와 전체 개수 배열에서 1로 표시된 요소의 위치를 ​​계산합니다. 이때, count 배열의 n번째 요소의 값은 정렬 후의 위치가 되어야 하며, n은 정렬 후 이 위치에 해당하는 값입니다. 따라서 마지막으로 count 배열의 키 값을 하나씩 결과 배열에 매핑합니다.
버킷 정렬은 요소가 집합에서 n번째로 큰 경우 이전 요소나 다음 요소가 그 요소보다 크거나 작은지 신경 쓰지 않고 n번째 순위를 매겨야 한다는 아이디어를 교묘하게 사용합니다. 비교하기 위해). 분명히 실제 상황에서는 정렬된 집합의 요소 값의 범위가 집합의 요소 수보다 훨씬 클 가능성이 높으므로 이에 상응하는 거대한 공간의 배열을 할당해야 합니다. 따라서 버킷 정렬의 일반적인 시나리오는 외부 정렬입니다.

관심 있는 학생들은 서로 다른 규모의 순서로 세 가지 종류의 정렬을 수행하는 데 시간이 많이 걸리는 작업을 테스트할 수 있습니다.