데이터 구조를 알게 된 이후 다양한 알고리즘 기본 사항에 노출되었지만 시험을 마친 이후로 연습 한 적이 없습니다. 내가 개발할 때, 나는 그것을 사용했을 때도 확인했다. 이제 저는 JavaScript를 배우고 있습니다. 이 시간은 다양한 기본 알고리즘을 구성하고 JS 및 PHP 구문에서 각각 코드를 작성합니다.
1. 버블 분류
원리 : 쌍의 인접한 숫자를 비교하고 작은 것에서 크거나 큰 또는 작은 것까지 순서대로 교환하십시오. 여행 후, 가장 크거나 작은 숫자는 마지막 숫자로 교환 된 다음 처음부터 두 번째 숫자에서 마지막 숫자 끝까지 비교하고 교환합니다.
시간 복잡성 : 평균 사례 : O (N2) 최상의 사례 : O (N) 최악의 경우 : O (N2)
공간 복잡성 : O (1)
안정성 : 안정
// javaScript syntax var array = [23,0,32,45,56,75,43,0,34]; for (var i = 0; i <array.length; i ++) {var issort = true; for (var j = 0; j <array.length -1 -i; j ++) {if (array [j]> array [j+1]) {issort = false; var temp = 배열 [j]; 배열 [j] = 배열 [j + 1]; 배열 [j + 1] = 온도; }} if (issort) {break; }} console.log (배열); <? php $ array = [23,0,32,45,56,75,43,0,34]; for ($ i = 0; $ i <count ($ array); $ i ++) {$ issort = true; for ($ j = 0; $ j <count ($ array) -1; $ j ++) {if ($ array [$ j]> $ array [$ j+1]) {$ issort = false; $ temp = $ 배열 [$ j]; $ array [$ j] = $ array [$ j + 1]; $ array [$ j + 1] = $ temp; }} if ($ issort) {break; }} var_dump ($ array);?>2. 간단한 선택 분류
원칙 : NI 키워드를 비교하여 N-I+1 레코드에서 가장 작은 키워드로 레코드를 선택하고 I (1 <= i <= n) TH 레코드와 교환하십시오. 간단한 선택 분류의 성능은 버블 분류보다 약간 낫습니다.
시간 복잡성 : 평균 사례 : O (N2) 최상의 사례 : O (N) 최악의 경우 : O (N2)
공간 복잡성 : O (1)
안정성 : 불안정
// javaScript var array = [23,0,32,45,56,75,43,0,34]; for (var i = 0; i <array.length -1; i ++) {var pos = i; for (var j = i+1; }} var temp = 배열 [i]; 배열 [i] = 배열 [pos]; 배열 [pos] = 온도; } console.log (배열); <? php $ array = [23,0,32,45,56,75,43,0,34]; for ($ i = 0; $ i <count ($ array); $ i ++) {$ pos = $ i; for ($ j = $ i+1; $ j <count ($ array); $ j ++) {if ($ array [$ j] <$ array [$ pos]) {$ pos = $ j; }} $ temp = $ 배열 [$ i]; $ array [$ i] = $ array [$ pos]; $ array [$ pos] = $ temp; } var_dump ($ array);?>3. 직접 정렬을 삽입하십시오
원칙 : 정렬 된 정렬 테이블에 레코드를 삽입하여 1 단위의 레코드가있는 새 주문 테이블을 얻습니다. 즉, 먼저 시퀀스의 첫 번째 레코드를 순서대로 한 후속 시퀀스로 취급 한 다음 전체 시퀀스가 순서가 될 때까지 두 번째 레코드에서 하나씩 삽입하십시오. 버블 방법 및 선택 분류보다 더 나은 성능
시간 복잡성 : 평균 사례 : O (N2) 최상의 사례 : O (N) 최악의 경우 : O (N2)
공간 복잡성 : O (1)
안정성 : 안정
// javaScript var array = [23,0,32,45,56,75,43,0,34]; for (var j = 0; j <array.length; j ++) {var key = array [j]; var i = j -1; while (i> -1 && array [i]> key) {배열 [i + 1] = 배열 [i]; i = i -1; } 배열 [i + 1] = 키; } console.log (배열); <? php // 직접 삽입 정렬 $ array = [23,0,32,45,75,43,0,34]; for ($ i = 0; $ i <count ($ array); $ i ++) {$ key = $ array [$ i]; $ j = $ i -1; while ($ j> -1 && $ array [$ j]> $ key) {$ array [$ j +1] = $ array [$ j]; $ j = $ j -1; } $ 배열 [$ j + 1] = $ 키; } var_dump ($ array);?>4. 빠른 정렬
원칙 : 정렬을 통해 정렬 할 데이터는 두 개의 독립적 인 부분으로 나뉘고 모든 데이터는 다른 부분의 모든 데이터보다 작고 데이터의 두 부분은이 방법에 따라 빠르게 정렬됩니다. 전체 분류 프로세스는 전체 데이터를 순서 시퀀스가되기 위해 재귀 적으로 수행 될 수 있습니다.
시간 복잡성 : 평균 사례 : O (NLOG2N) 최고의 사례 : O (NLOG2N) 최악의 경우 : O (N2)
공간 복잡성 : O (NLOG2N)
안정성 : 불안정
// JavaScript Quick Sort var array = [23,0,32,45,56,75,43,0,34]; var quicksort = function (arr) {if (arr.length <= 1) {return arr; } // 배열의 요소 수를 확인하십시오. 1보다 작거나 같으면 반환됩니다. var pivotindex = math.floor (arr.length/2); // var pivot = Ar for (var i = 0; i <arr.length; i ++) // 배열을 트랜스 웨이프하고 "벤치 마크"보다 작은 요소를 왼쪽의 서브 세트에 넣고 오른쪽의 서브 세트에 벤치 마크보다 큰 요소를 넣습니다. {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} QuickSort (왼쪽) .concat ([pivot], QuickSort (오른쪽)); // 정렬 된 배열을 가져 오려면이 프로세스를 계속 반복합니다. }; var newArray = QuickSort (배열); Console.log (NewArray); <? php $ array = [23,0,32,45,56,75,43,0,34]; function Quick_Sort ($ arr) {// 먼저 $ length = count ($ arr)를 계속 해야하는지 결정합니다. if ($ length <= 1) {return $ arr; } $ base_num = $ arr [0]; // 첫 번째 요소를 선택하려는 통치자를 선택하십시오. // 두 배열 초기화 $ left_array = array (); // $ right_array는 intray = array (); // for ($ i = 1; $ i <$ lenger; $ i ++) {// 2 개의 배열을 제외하고 ($ i = 1; $ i <$ length; $ i ++)를 제외하고 ($ i = 1; $ i <$ lenger; $ arr [$ i]) {// 왼쪽 배열에 넣습니다. $ left_array [] = $ arr [$ i]; } else {// 오른쪽에 올바른 right_array [] = $ arr [$ i]; }} // 그러면 왼쪽 및 오른쪽 배열에 대해 각각 동일한 정렬 방법을 재귀 적으로 호출하고 결과를 녹음하고 left_array = quick_sort ($ left_array); $ right_array = quick_sort ($ right_array); // 왼쪽 눈금자를 오른쪽 반환 array_merge ($ left_array, Array ($ base_num), $ right_array)로 병합합니다. } $ newArray = Quick_Sort ($ array); var_dump ($ newArray);?>5. 힐 정렬
원리 : 먼저, 전체 레코드 시퀀스를 나누어 직접 삽입 및 정렬을 위해 여러 하단 시퀀스로 분류하십시오. 전체 시퀀스의 레코드가 "기본적으로 순서"되면 전체 레코드를 순서대로 삽입하고 정렬하십시오. .
시간 복잡성 : 평균 사례 : O (nold) 최상의 사례 : O (nlog2n) 최악의 경우 : O (N2)
공간 복잡성 : O (1)
안정성 : 불안정
// JavaScript Hill Sort var array = [23,0,32,45,75,43,0,34]; var shellsort = function (arr) {var length = arr.length; var h = 1; while (h <length/3) {h = 3*h+1; // set interval} while (h> = 1) {for (var i = h; i <길이; i ++) {for (var j = i; j> = h && arr [jh]; var emp = arr [jh]; arr [jh] = arr [j]; ARR [J] = 온도; }} h = (H-1)/3; } rack arr; } var newArray = shellsort (배열); Console.log (NewArray); <? php // hill sort $ array = [23,0,32,45,56,75,43,0,34]; 함수 shellsort ($ arr) {$ length = count ($ arr); $ h = 1; while ($ h <$ length/3) {$ h = 3*$ h+1; // 간격} while ($ h> = 1) {($ i = $ h; $ i <$ length; $ i ++) {($ j = $ j> = $ h && $ j <$ arr [$ j- $ h] $ arr [$ j- $ h] = $ arr [$ j]; $ arr [$ j] = $ temp; }} $ h = ($ h-1)/3; } return $ arr; } $ newArray = shellsort ($ array); var_dump ($ newArray)?>6. 주문
원리 : 초기 시퀀스에 N 레코드가 포함된다고 가정하면, 순서대로 간주 될 수 있고, 순서대로 간주 될 수 있고, 각 하속은 길이 1의 길이를 갖고, 가장 작은 정수 (N/2보다 작은 정수)는 길이 2 또는 1의 길이를 가진 순서 대상 후속 시퀀스를 얻고 길이 N이있는 순서 시퀀스가 얻어 질 때 까지이 방식으로 반복합니다.
시간 복잡성 : 평균 사례 : O (NLOG2N) 최상의 사례 : O (NLOG2N) 최악의 경우 : O (NLOG2N)
공간 복잡성 : O (1)
안정성 : 안정
// javaScript 병합 정렬 함수 isArray1 (arr) {if (object.prototype.tostring.call (arr) == '[개체 배열]') {return true; } else {return false; }} 함수 병합 (왼쪽, 오른쪽) {var result = []; if (! isarray1 (왼쪽)) {왼쪽 = [왼쪽]; } if (! isArray1 (오른쪽)) {오른쪽 = [오른쪽]; } while (left.length> 0 && right.length> 0) {if (왼쪽 [0] <오른쪽 [0]) {result.push (left.shift ()); } else {result.push (right.shift ()); }} return result.concat (왼쪽) .concat (오른쪽); } 함수 mergesort (arr) {var len = arr.length; var lim, work = []; var i, j, k; if (len == 1) {return arr; } for (i = 0; i <len; i ++) {work.push (arr [i]); } work.push ([]); for (lim = len; lim> 1;) {// lim은 (j = 0, k = 0; k <lim; j ++, k = k+2)에 대한 그룹화 길이입니다. } 작업 [j] = []; lim = math.floor ((lim+1)/2); } 반환 작업 [0]; } var array = [23,0,32,45,56,75,43,0,34]; Console.log (Mergesort (Array)); <? php // 분류 함수 이해 mergesort (& $ arr) {$ len = count ($ arr); // 배열 길이 msort 찾기 ($ arr, 0, $ len-1); } // 실제로 분류 함수 msort 병합 msort (& $ arr, $ left, $ right) {if ($ 왼쪽 <$ right) {// 후속에 추가 요소가 1 개의 추가 요소가 있음을 나타냅니다. 그러면 별도로 분할, 병합, 길이 /2는 전체 $ 중심으로 이동해야합니다. // 재귀 호출은 왼쪽을 다시 정렬합니다. // 오른쪽을 다시 정렬하려면 재귀 적으로 전화를 걸어 MSORT ($ ARR, $ CENTRE+1, $ RIGHT); // 정렬 결과 mergearray ($ arr, $ 왼쪽, $ center, $ right)를 병합합니다. }} // 순서대로 두 개의 숫자를 순서대로 결합합니다. MergearRay (& $ arr, $ 왼쪽, $ center, $ 오른쪽) {// 두 개의 시작 위치를 설정하십시오. $ a_i = $ left; $ b_i = $ center+1; while ($ a_i <= $ center && $ b_i <= $ right) {// 어레이 A 또는 배열 B가 경계를 가로 지르면 ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++]; } else {$ temp [] = $ arr [$ b_i ++]; }} // 배열 A의 모든 요소가 사용되었는지 판단합니다. 그렇지 않은 경우 배열 C에 모든 요소를 삽입하십시오. } // 배열 B의 모든 요소가 사용되는지 판단합니다. 그렇지 않은 경우 배열 C에 모든 요소를 삽입하십시오. } // $ arrc에 정렬 된 부품을 $ arr로 작성하십시오. }} $ arr = 배열 (23,0,32,45,56,75,43,0,34); Mergesort ($ ARR); var_dump ($ arr);?>7. 힙 분류
원리 : 힙 분류는 힙을 사용하여 분류하는 방법입니다. 기본 아이디어는 : 큰 상단 힙으로 분류 할 시퀀스를 구성하는 것입니다. 현재 전체 시퀀스의 최대 값은 힙 상단의 루트 노드입니다. 제거 (실제로, 힙 배열의 끝 요소와 교환하는 것이고, 끝 요소가 최대 값) 나머지 n-1 시퀀스를 힙으로 재구성하여 n 요소의 하위 값을 얻을 수 있도록합니다. 이로 인해 반복적 인 실행이 발생하고 순서 시퀀스가 얻을 수 있습니다.
시간 복잡성 : 평균 사례 : O (NLOG2N) 최상의 사례 : O (NLOG2N) 최악의 경우 : O (NLOG2N)
공간 복잡성 : O (1)
안정성 : 불안정
// JavaScript 힙 Sort var array = [23,0,32,45,56,75,43,0,34]; 함수 Heapsort (Array) {for (var i = math.floor (array.length / 2); i> = 0; i-) {HeaPadjust (Array, I, Array.Length-1); // (i = array.length-1; i> = 0; i--)에 대한 배열 배열을 큰 상단 힙으로 빌드하십시오. {/*루트 노드*/var temp = array [i]; 배열 [i] = 배열 [0]; 배열 [0] = 온도; /*나머지 배열은 큰 상단 힙에 계속 내장되어 있습니다*/ HeaPadjust (Array, 0, I -1); } 반환 배열; } function heapadjust (배열, 시작, max) {var temp = array [start]; // temp는 (var j = 2 * start; } if (temp> = array [j]) break; 배열 [start] = 배열 [j]; 시작 = J; } 배열 [start] = temp; } var newArray = heapSort (배열); Console.log (NewArray); <? php // heap sort 함수 heapsort (& $ arr) {#initheap ($ arr, 0, count ($ arr) -1); #헤드와 테일 노드를 스왑하고 한 번에 하나의 끝 노드를 줄이고 ($ end = count ($ arr) -1; $ end> 0; $ end--) {$ temp = $ arr [0]; $ arr [0] = $ arr [$ end]; $ arr [$ end] = $ temp; Ajustnodes ($ arr, 0, $ end -1); }} ##Initialize 최대 힙을, 마지막 비 잎 노드에서 시작하면 마지막 비 잎 노드는 배열 길이/2 라운드 다운 함수 initheap (& $ len = count ($ arr)로 번호가 매겨집니다. for ($ start = floor ($ len / 2) -1; $ start> = 0; $ start- -) {Ajustnodes ($ arr, $ start, $ len -1); }}#조정 노드#@param $ ARR ARRAY 조정#@param $ 조정할 부모 노드의 좌표#@param $ END END NODE의 좌표 조정 기능 AJUSTNODES (& $ arr, $ start, $ end) {$ maxInx = $ start; $ len = $ end + 1; #조정할 부품의 길이 $ $ leftChildInx = ($ start + 1) * 2-1; #left child coordinate $ rightchildinx = ($ start + 1) * 2; #right child coordinate #조정할 부품에 왼쪽 자식이있는 경우 ($ leftChildInx + 1 <= $ len) { # #최소 노드 좌표 if ($ arr [$ maxinx] <$ arr [$ leftchildinx]) {$ maxinx = $ leftchildinx; } #조정할 부품에 오른쪽 하위 노드가있는 경우 ($ rightchildinx + 1 <= $ len) {if ($ arr [$ maxInx] <$ arr [$ rightchildInx]) {$ maxInx = $ rightChildInx; }}} #swap 상위 노드 및 최대 노드 if ($ start! = $ maxInx) {$ temp = $ arr [$ start]; $ arr [$ start] = $ arr [$ maxInx]; $ ARR [$ maxInx] = $ temp; #교환 후 자식 노드가 하위 노드가있는 경우 (($ maxinx + 1) * 2 <= $ len) {ajustnodes ($ arr, $ maxinx, $ end); }}} $ arr = 배열 (23,0,32,45,56,75,43,0,34); Heapsort ($ ARR); var_dump ($ arr);?>8. 카디널리티 분류
원리 : 정수를 숫자로 다른 숫자로 자른 다음 각 자리로 별도로 비교하십시오. 정수는 또한 특정 형식의 문자열 (예 : 이름 또는 날짜)과 부동 소수점 번호를 표현할 수 있으므로 Radix 정렬은 정수에만 사용되지 않습니다.
시간 복잡성 : 평균 사례 : O (d (r+n)) 최상의 사례 : O (d (n+rd)) 최악의 경우 : O (d (r+n)) r : 키워드의 기차 정보 d : 길이 n : 키워드 수 : 키워드 수
공간 복잡성 : O (RD+N)
안정성 : 안정
<? php #blassorting, 여기서는 양의 정수 만 정렬됩니다. 음수 및 부동 소수점 번호의 경우 보완이 필요합니다. #counting sort #@param $ arr 배열을 정렬 할 #@param $ digit_num 정렬 숫자 함수 counting_sort (& $ arr, $ digit_num = false) {if ($ digit_num! == false) {#if $ digit_num im count ($ arr); $ i ++) {$ arr_temp [$ i] = get_specific_digit ($ arr [$ i], $ digit_num); }} else {$ arr_temp = $ arr; } $ max = max ($ arr); $ time_arr = array (); #요소 배열 발생#초기화 발생 배열 ($ i = 0; $ i <= $ max; $ i ++) {$ time_arr [$ i] = 0; } #($ i = 0; $ i <count ($ arr_temp); $ i ++) {$ time_arr [$ arr_temp); $ i ++) {$ time_arr [$ arr_temp [$ i]] ++; } # #($ i = 0; $ i <count ($ time_arr) -1; $ i ++) {$ time_arr [$ i +1] += $ time_arr [$ i]; } # #($ i = count ($ arr) -1; $ i> = 0; $ i--) {$ time_arr [$ time_arr [$ arr_temp [$ i]] -$ arr [$ i]; $ time_arr [$ arr_temp [$ i]]-; } $ arr = $ sorted_arr; KSORT ($ ARR); #이번에 키 분류의 효율 손실} # # #특정 번호 함수 get_digit ($ 번호) {$ i = 1; while ($ number> = pow (10, $ i)) {$ i ++; } return $ i; } #단일 자릿수에서 숫자의 i 번째 숫자 번호를 얻습니다. } 반환 바닥 ($ num % pow (10, $ i) / pow (10, $ i -1)); } #black 정렬, 하위 서체 프로세스 기능 Radix_Sort (& $ ARR)로 정렬을 세십시오. {#First는 배열에서 가장 큰 숫자를 찾으십시오. $ max = max ($ arr); $ max_digit = get_digit ($ max); for ($ i = 1; $ i <= $ max_digit; $ i ++) {counting_sort ($ arr, $ i); }} $ arr = 배열 (23,0,32,45,56,75,43,0,34); radix_sort ($ arr); var_dump ($ arr);?>위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.