서면 인터뷰에는 종종 다양한 알고리즘이 포함됩니다. 이 기사는 일반적으로 사용되는 일부 알고리즘을 간략하게 소개하고 JavaScript로 구현합니다.
1. 정렬 삽입
1) 알고리즘 소개
Insertion-Sort의 알고리즘 설명은 간단하고 직관적 인 정렬 알고리즘입니다. 정렬 된 시퀀스를 구축하고, 분류되지 않은 데이터의 경우, 정렬 된 시퀀스에서 뒤쪽 및 앞면을 스캔하고 해당 위치를 찾아 삽입하여 작동합니다. 삽입 분류를 구현할 때, 내면의 정렬이 일반적으로 사용되므로 (즉, O (1)의 추가 공간이 필요합니다). 스캐닝 프로세스 중에는 전면으로 정렬 된 요소가 반복적으로 뒤로 이동하여 최신 요소에 대한 삽입 공간을 제공해야합니다.
2) 알고리즘 설명 및 구현
일반적으로 삽입 분류는 내 위치를 사용하여 배열에서 구현됩니다. 특정 알고리즘은 다음과 같이 설명됩니다.
첫 번째 요소에서 시작하여 요소는 정렬 된 것으로 간주 될 수 있습니다.
다음 요소를 꺼내서 이미 정렬 된 요소 시퀀스에서 뒤쪽과 앞으로 스캔하십시오.
요소 (정렬)가 새 요소보다 크면 요소를 다음 위치로 이동하십시오.
정렬 된 요소가 새 요소가 작거나 같거나 동일 할 때까지 3 단계를 반복하십시오.
새로운 요소를 해당 위치에 삽입 한 후;
2 ~ 5 단계를 반복하십시오.
JavaScript 코드 구현 :
function insertionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var key = array [i]; var j = i -1; while (j> = 0 && array [j]> key) {배열 [j + 1] = 배열 [j]; J--; } 배열 [j + 1] = 키; } 반환 배열; } else {return 'array는 배열이 아닙니다!'; }}3) 알고리즘 분석
가장 좋은 경우 : 입력 배열은 오름차순으로 정렬됩니다. t (n) = o (n)
최악의 경우 : 입력 배열은 하강 순서로 정렬됩니다. t (n) = O (n2)
평균 : t (n) = O (n2)
둘째, 이진 삽입 정렬
1) 알고리즘 소개
바이너리-삽입 소트 정렬 정렬은 직접 삽입 분류 알고리즘을 약간 변경하는 분류 알고리즘입니다. 그것과 직접 삽입 분류 알고리즘의 가장 큰 차이점은 삽입 위치를 찾을 때 이진 검색 방법이 사용되며, 이는 속도가 특정한 개선이된다는 것입니다.
2) 알고리즘 설명 및 구현
일반적으로 삽입 분류는 내 위치를 사용하여 배열에서 구현됩니다. 특정 알고리즘은 다음과 같이 설명됩니다.
첫 번째 요소에서 시작하여 요소는 정렬 된 것으로 간주 될 수 있습니다.
다음 요소를 꺼내서 이미 정렬 된 요소 시퀀스에서 첫 번째 숫자의 위치를 찾으십시오.
새로운 요소를 해당 위치에 삽입 한 후;
위의 두 단계를 반복하십시오.
JavaScript 코드 구현 :
함수 binaryinsertionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var key = array [i], left = 0, right = i - 1; while (왼쪽 <= 오른쪽) {var middle = parseint ((왼쪽 + 오른쪽) / 2); if (키 <배열 [중간]) {오른쪽 = 중간 -1; } else {왼쪽 = 중간 + 1; }} for (var j = i-1; j> = 왼쪽; j-) {배열 [j + 1] = 배열 [j]; } 배열 [왼쪽] = 키; } 반환 배열; } else {return 'array는 배열이 아닙니다!'; }}3) 알고리즘 분석
가장 좋은 경우 : t (n) = O (nlogn)
최악의 경우 : t (n) = O (n2)
평균 : t (n) = O (n2)
3. 정렬을 선택하십시오
1) 알고리즘 소개
Selection-Sort는 간단하고 직관적 인 정렬 알고리즘입니다. 작동 방식 : 먼저 분류되지 않은 시퀀스에서 가장 작은 (큰) 요소를 찾아서 분류 된 시퀀스의 시작 위치에 저장 한 다음 나머지 분류되지 않은 요소에서 가장 작은 (큰) 요소를 계속 찾은 다음 분류 된 시퀀스의 끝에 놓습니다. 모든 요소가 정렬 될 때까지.
2) 알고리즘 설명 및 구현
N-1 패스를 통해 N 레코드의 직접 선택을 직접 선택하여 직접 선택하고 정렬 할 수 있습니다. 특정 알고리즘은 다음과 같이 설명됩니다.
초기 상태 : 정렬되지 않은 영역은 r [1..n]이며, 순서 대상 영역은 비어 있습니다.
I-ther 순서 (i = 1,2,3 ... N-1)가 시작되면 현재 순서 대상 및 비 순서 영역은 각각 r [1..i-1] 및 r (i..n)입니다. 이 순서는 현재의 순서대로에서 가장 작은 키워드를 사용하여 레코드 r [k]를 선택하고, 순서가없는 영역의 첫 번째 레코드 r과 교환하여 R [1..i] 및 r [i+1..n)가 레코드 수가 한 번 증가하고 레코드 수가 줄어든 새로운 순서가없는 영역이됩니다.
N-1 트립이 끝나고 배열이 주문됩니다.
JavaScript 코드 구현 :
함수 selectionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {var len = array.length, temp; for (var i = 0; i <len -1; i ++) {var min = array [i]; for (var j = i+1; j <len; j ++) {if (array [j] <min) {temp = min; 최소 = 배열 [j]; 배열 [j] = 온도; }} 배열 [i] = min; } 반환 배열; } else {return 'array는 배열이 아닙니다!'; }}3) 알고리즘 분석
가장 좋은 경우 : t (n) = O (n2)
최악의 경우 : t (n) = O (n2)
평균 : t (n) = O (n2)
4. 버블 분류
1) 알고리즘 소개
버블 분류는 간단한 분류 알고리즘입니다. 정렬 할 시퀀스를 반복적으로 방문하고 한 번에 두 가지 요소를 비교 한 다음 부정확 한 경우 교환합니다. 시퀀스를 방문하는 작업은 교환이 필요하지 않을 때까지 반복됩니다. 즉, 시퀀스가 분류되었습니다. 이 알고리즘의 기원은 요소가 더 작을수록 Exchange를 통해 서열의 상단에 느리게 "플로트"되기 때문입니다.
2) 알고리즘 설명 및 구현
특정 알고리즘은 다음과 같이 설명됩니다.
인접한 요소를 비교하십시오. 첫 번째 것이 두 번째보다 크면 두 개를 교환하십시오.
첫 번째 쌍의 시작부터 마지막 쌍의 끝까지 각 쌍의 인접 요소에 대해 동일한 작업을 수행하므로 마지막 요소가 가장 큰 숫자가되어야합니다.
마지막 요소를 제외한 모든 요소에 대해 위의 단계를 반복하십시오.
정렬이 완료 될 때까지 1 ~ 3 단계를 반복하십시오.
JavaScript 코드 구현 :
함수 bubblesort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {var len = array.length, temp; for (var i = 0; i <len -1; i ++) {for (var j = len -1; j> = i; j-) {if (array [j] <array [j -1]) {temp = array [j]; 배열 [j] = 배열 [j -1]; 배열 [j -1] = 온도; }}} 반환 배열; } else {return 'array는 배열이 아닙니다!'; }}3) 알고리즘 분석
가장 좋은 경우 : t (n) = o (n)
최악의 경우 : t (n) = O (n2)
평균 : t (n) = O (n2)
5. 빠른 정렬
1) 알고리즘 소개
빠른 정렬의 기본 아이디어 : 레코드를 한 순서를 통해 두 개의 독립 부품으로 분류하고 일부 레코드의 키워드는 다른 부분의 키워드보다 작습니다. 그런 다음 두 레코드는 전체 시퀀스의 순서를 달성하기 위해 별도로 분류 할 수 있습니다.
2) 알고리즘 설명 및 구현
빠른 정렬은 구분 방법을 사용하여 문자열을 두 하위 목록으로 나눕니다. 특정 알고리즘은 다음과 같이 설명됩니다.
시퀀스에서 요소를 선택하는 것은 "원칙"(피봇)이라고합니다.
시퀀스를 재정렬하면 참조 값보다 작은 모든 요소가 참조 앞에 배치되고 참조 값보다 큰 모든 요소가 참조 뒤에 배치됩니다 (동일한 숫자는 양쪽에 배치 할 수 있음). 이 파티션이 종료 된 후, 기준은 시퀀스의 중간에 있습니다. 이것을 파티션 작업이라고합니다.
기준 요소보다 작은 하단 시퀀스를 재귀 적으로 정렬하고 참조 요소보다 큰 하단 시퀀스를 더 크게 정렬합니다.
JavaScript 코드 구현 :
// 메소드 QuickSort (배열, 왼쪽, 오른쪽) {if (object.prototype.toString.call (array) .Slice (8, -1) === 'array'&& left === 'number'&& typeof right === 'number') {if (왼쪽 <오른쪽) {var x = array [left], i = temp; for (var j = left; j <= right; j ++) {if (array [j] <= x) {i ++; 온도 = 배열 [i]; 배열 [i] = 배열 [j]; 배열 [j] = 온도; }} QuickSort (배열, 왼쪽, i -1); QuickSort (배열, i + 1, 오른쪽); }; } else {return 'array는 배열이 아니거나 왼쪽 또는 오른쪽이 숫자가 아닙니다!'; }} var aaa = [3, 5, 2, 9, 1]; QuickSort (AAA, 0, AAA.Length -1); Console.log (AAA); // 메소드 2 var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotindex = math.floor (arr.length / 2); var pivot = arr.splice (pivotindex, 1) [0]; var 왼쪽 = []; var right = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return QuickSort (왼쪽) .concat ([pivot], QuickSort (오른쪽)); };3) 알고리즘 분석
가장 좋은 경우 : t (n) = O (nlogn)
최악의 경우 : t (n) = O (n2)
평균 : t (n) = O (nlogn)
6. 힙 분류
1) 알고리즘 소개
힙 정렬은 힙 데이터 구조를 사용하여 설계된 정렬 알고리즘을 나타냅니다. 스태킹은 대략적으로 이진 트리이며 스태킹의 특성을 충족시키는 구조입니다.
2) 알고리즘 설명 및 구현
특정 알고리즘은 다음과 같이 설명됩니다.
정렬 할 키워드의 초기 시퀀스 (R1, R2 ... RN)는 초기의 정렬되지 않은 영역 인 큰 상단 힙으로 구성됩니다.
힙 상부 요소 R [1]을 마지막 요소 r [n]으로 교환하고,이 시점에서, 새로운 순서가없는 영역 (R1, R2, ... RN-1)과 새로운 순서 영역 (RN)이 얻어지고 R [1,2 ... N-1] <= r [n]이 만족됩니다.
교환 후 새로운 힙 상단 R [1]가 힙의 특성을 위반할 수 있기 때문에, 현재의 정렬되지 않은 영역 (R1, R2, ... RN-1)을 새 힙으로 조정 한 다음 R1, R2 ... R2 ... RN-2) 및 새로운 순서 영역 (RN-1, RN)을 얻기 위해 R [1]을 다시 미정 영역의 마지막 요소로 교환해야합니다. 정렬 된 영역의 요소 수가 N-1이되고 전체 분류 프로세스가 완료 될 때 까지이 프로세스를 반복하십시오.
JavaScript 코드 구현 :
/*메소드 설명 : 정렬 할 힙 정렬 @Param 배열 배열*/function heapSort (array) {if (object.prototype.tostring.call (Array) .Slice (8, -1) === 'Array') {// Heap var heapsize = array.length, temp; for (var i = math.floor (Heapsize / 2); i> = 0; i-) {Heapify (Array, I, Heapsize); } // heap sort for (var j = heapsize-1; j> = 1; j-) {temp = array [0]; 배열 [0] = 배열 [j]; 배열 [j] = 온도; Heapify (Array, 0, -heapsize); }} else {return 'array는 배열이 아닙니다!'; }}/ * 메소드 설명 : heap @param arr array @param x array 첨자 @param len heap size */function heapify (arr, x, len) {if (object.prototype.tostring.call (arr) .slice (8, -1) == 'array'&& typeof x == var l = 2 * r. 1, 가장 큰 = x, 온도; if (l <len && arr [l]> arr [가장 큰]) {가장 큰 = l; } if (r <len && arr [r]> arr [가장 큰]) {가장 큰 = r; } if (가장 큰! = x) {temp = arr [x]; ARR [X] = ARR [가장 큰]; ARR [가장 큰] = 온도; Heapify (ARR, LAGE, LEN); }} else {return 'arr는 배열이 아니거나 X가 숫자가 아닙니다!'; }}3) 알고리즘 분석
가장 좋은 경우 : t (n) = O (nlogn)
최악의 경우 : t (n) = O (nlogn)
평균 : t (n) = O (nlogn)
7. 주문
1) 알고리즘 소개
병합 정렬은 병합 작업을 기반으로 한 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분열 및 정복의 매우 전형적인 적용입니다. 병합 분류는 안정적인 정렬 방법입니다. 정렬 된 후속 시퀀스를 병합하여 완전히 정렬 된 시퀀스를 얻습니다. 즉, 각 후속 순서를 첫 번째 순서로 만든 다음 후속 세그먼트를 순서로 만듭니다. 정렬 된 두 테이블이 하나의 주문 테이블로 병합되면 2 방향 병합이라고합니다.
2) 알고리즘 설명 및 구현
특정 알고리즘은 다음과 같이 설명됩니다.
길이 n의 입력 시퀀스를 길이 N/2의 두 하단 시퀀스로 나눕니다.
이 두 후속도는 개별적으로 함께 정렬됩니다.
두 개의 정렬 된 후속 시퀀스를 최종 분류 시퀀스로 병합하십시오.
JavaScript 코드 구현 :
함수 mergesort (배열, p, r) {if (p <r) {var q = math.floor ((p + r) / 2); Mergesort (Array, P, Q); Mergesort (배열, Q + 1, R); 병합 (배열, p, q, r); }} 함수 병합 (배열, p, q, r) {var n1 = q -p + 1, n2 = r- q, 왼쪽 = [], 오른쪽 = [], m = n = 0; for (var i = 0; i <n1; i ++) {왼쪽 [i] = 배열 [p+i]; } for (var j = 0; j <n2; j ++) {오른쪽 [j] = 배열 [q + 1 + j]; } 왼쪽 [n1] = 오른쪽 [n2] = 번호 .max_value; for (var k = p; k <= r; k ++) {if (왼쪽 [m] <= 오른쪽 [n]) {array [k] = 왼쪽 [m]; m ++; } else {array [k] = 오른쪽 [n]; n ++; }}}3) 알고리즘 분석
가장 좋은 경우 : t (n) = o (n)
최악의 경우 : t (n) = O (nlogn)
평균 : t (n) = O (nlogn)
8. 버킷 분류
1) 알고리즘 소개
버킷 분류의 원리 : 입력 데이터가 균일하게 분포되어 있다고 가정하면 데이터는 제한된 수의 버킷으로 나뉘어지고 각 버킷은 별도로 정렬됩니다 (다른 정렬 알고리즘을 사용하거나 재귀 방식으로 버킷 분류를 계속 사용할 수 있습니다).
2) 알고리즘 설명 및 구현
특정 알고리즘은 다음과 같이 설명됩니다.
정량적 배열을 빈 양동이로 설정합니다.
입력 데이터를 통해 반복하고 해당 버킷에 하나씩 데이터를 넣습니다.
비어 있지 않은 각 버킷을 정렬하십시오.
빈 양동이에서 정렬 된 데이터를 스플 라이스합니다.
JavaScript 코드 구현 :
/*메소드 설명 : 버킷 정렬 @Param 배열 배열 @Param Num 버킷 수*/ 함수 BucketSort (배열, num) {if (array.length <= 1) {return array; } var len = array.length = [], result = [], min = max = array [0], regex = '/^[1-9]+[0-9]*$/', space, n = 0; num = num || ((num> 1 && regex.test (num))? num : 10); for (var i = 1; i <len; i ++) {min = min <= 배열 [i]? 최소 : 배열 [i]; max = max> = 배열 [i]? 맥스 : 배열 [i]; } space = (max -min + 1) / num; for (var j = 0; if (버킷 [index]) {// 비어 있지 않은 버킷, 정렬 var k = 버킷 [index] .length -1; while (k> = 0 && 버킷 [index] [k]> 배열 [j]) {버킷 [index] [k + 1] = 버킷 [index] [k]; 케이--; } 버킷 [index] [k + 1] = 배열 [j]; } else {// 빈 버킷, 초기화 버킷 [index] = []; 버킷 [index] .push (배열 [j]); }} while (n <num) {result = result.concat (버킷 [n]); n ++; } 반환 결과; }3) 알고리즘 분석
버킷 분류의 최상의 경우 선형 시간 O (n)의 경우 버킷 분류의 시간 복잡성은 다른 부품의 시간 복잡성이 O (n)이기 때문에 버킷 사이의 데이터 분류의 시간 복잡성에 따라 다릅니다. 분명히, 버킷이 작을수록 버킷의 데이터가 적을수록 정렬하는 데 시간이 줄어 듭니다. 그러나 해당 공간 소비가 증가합니다.
9. 정렬 계산
1) 알고리즘 소개
카운팅 정렬은 안정적인 정렬 알고리즘입니다. 카운트 분류는 추가 배열 C를 사용합니다. 여기서 I-th 요소는 분류 할 배열 A에서 i와 동일한 값을 가진 요소의 수입니다. 그런 다음 배열 C에 따르면 A의 요소는 올바른 위치로 배열됩니다. 정수 만 정렬 할 수 있습니다.
2) 알고리즘 설명 및 구현
특정 알고리즘은 다음과 같이 설명됩니다.
배열에서 가장 크고 작은 요소를 정렬 할 수 있습니다.
배열에 i의 값을 가진 각 요소의 횟수를 계산하여 배열 C의 I-th 항목에 저장하십시오.
모든 카운트를 축적합니다 (C의 첫 번째 요소에서 시작하여 각 항목 및 이전 항목이 추가됩니다);
반대 채우기 대상 배열 : 각 요소 i를 새 배열의 C (I) TH 항목에 배치하고 각 요소에 대해 C (i)를 1 씩 빼냅니다.
JavaScript 코드 구현 :
함수 카운팅 소트 (배열) {var len = array.length, b = [], c = [], min = max = array [0]; for (var i = 0; i <len; i ++) {min = min <= 배열 [i]? 최소 : 배열 [i]; max = max> = 배열 [i]? 맥스 : 배열 [i]; C [array [i]] = c [array [i]]? C [배열 [i]] + 1 : 1; } for (var J = min; } for (var k = len -1; k> = 0; k--) {b [c [array [k]] -1] = 배열 [k]; C [배열 [k]]-; } 반환 b; }3) 알고리즘 분석
입력 요소가 0과 k 사이의 정수 인 경우, 실행 시간은 O (n + k)입니다. 카운트 정렬은 비교 정렬이 아니며 정렬 속도는 비교 분류 알고리즘보다 빠릅니다. 계산에 사용되는 배열 C의 길이는 정렬 될 배열의 데이터 범위에 따라 달라지기 때문에 (정렬 할 배열의 최대 값과 최소값의 차이와 동일), 카운트 분류는 큰 데이터 범위를 갖는 배열에 많은 시간과 메모리를 필요로합니다.