JavaScript_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] = 임시
}
}
목록 반환
}

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

* @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 구현을 살펴보겠습니다.