자 바스 크 립 트 10 대 정렬 알고리즘 의 실현 방법
정렬 선택:
1 var array = [];
2
3 for(var i=0;i<100000;i++){
4 var x = Math.random()*100000;
5 var y = Math.floor(x);
6 array.push(y);
7 }
8
9 function selectionSort(arr) {
10 var len = arr.length;
11 var minIndex, temp;
12 console.time(' ');
13 for (var i = 0; i < len - 1; i++) {
14 minIndex = i;
15 for (var j = i + 1; j < len; j++) {
16 if (arr[j] < arr[minIndex]) { //
17 minIndex = j; //
18 }
19 }
20 temp = arr[i];
21 arr[i] = arr[minIndex];
22 arr[minIndex] = temp;
23 }
24 console.timeEnd(' ');
25 return arr;
26 }
27
28 console.log(selectionSort(array)); // :13204.966796875ms
힐 정렬:
1 //Js
2
3 var array = [];
4
5 for(var i=0;i<100000;i++){
6 var x = Math.random()*100000;
7 var y = Math.floor(x);
8 array.push(y);
9 }
10
11
12 function shellSort(arr) {
13 var len = arr.length,
14 temp,
15 gap = 1;
16 console.time(' :');
17 while(gap < len/5) { //
18 gap =gap*5+1;
19 }
20 for (gap; gap > 0; gap = Math.floor(gap/5)) {
21 for (var i = gap; i < len; i++) {
22 temp = arr[i];
23 for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
24 arr[j+gap] = arr[j];
25 }
26 arr[j+gap] = temp;
27 }
28 }
29 console.timeEnd(' :');
30 return arr;
31 }
32
33 console.log(shellSort(array)); // :25.843994140625ms
통 정렬:
1 //Js
2
3 var array = [];
4
5 for(var i=0;i<100000;i++){
6 var x = Math.random()*100000;
7 var y = Math.floor(x);
8 array.push(y);
9 }
10
11 function bucketSort(array, num) {
12 if (array.length <= 1) {
13 return array;
14 }
15 var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0;
16
17 var index = Math.floor(len / num) ;
18 while(index<2){
19 num--;
20 index = Math.floor(len / num) ;
21 }
22
23 console.time(' ');
24 for (var i = 1; i < len; i++) {
25 min = min <= array[i] ? min : array[i];
26 max = max >= array[i] ? max : array[i];
27 }
28 space = (max - min + 1) / num; //
29 for (var j = 0; j < len; j++) {
30 var index = Math.floor((array[j] - min) / space);
31 if (buckets[index]) { // ,
32 var k = buckets[index].length - 1;
33 while (k >= 0 && buckets[index][k] > array[j]) {
34 buckets[index][k + 1] = buckets[index][k];
35 k--;
36 }
37 buckets[index][k + 1] = array[j];
38 } else { // ,
39 buckets[index] = [];
40 buckets[index].push(array[j]);
41 }
42 }
43 while (n < num) {
44 result = result.concat(buckets[n]);
45 n++;
46 }
47 console.timeEnd(' ');
48 return result;
49 }
50
51 console.log(bucketSort(array,1000)); // : 122.424072265625ms
빠 른 정렬:
1 //Js
2
3 var array = [];
4
5 for(var i=0;i<100000;i++){
6 var x = Math.random()*100000;
7 var y = Math.floor(x);
8 array.push(y);
9 }
10
11 var quickSort = function(arr) {
12 //console.time('2. ');
13 if (arr.length <= 1) { return arr; }
14 var pivotIndex = Math.floor(arr.length / 2);
15 var pivot = arr.splice(pivotIndex, 1)[0];
16 var left = [];
17 var right = [];
18 for (var i = 0; i < arr.length; i++){
19 if (arr[i] < pivot) {
20 left.push(arr[i]);
21 } else {
22 right.push(arr[i]);
23 }
24 }
25 //console.timeEnd('2. ');
26 return quickSort(left).concat([pivot], quickSort(right));
27 };
28
29 var abc = function(){
30 console.time('2. ');
31 var efg = quickSort(array);
32 console.timeEnd('2. ');
33 return efg;
34 }
35
36 abc(); // :98.901123046875ms
계수 정렬:
1 //Js
2
3 var array = [];
4
5 for(var i=0;i<100000;i++){
6 var x = Math.random()*100000;
7 var y = Math.floor(x);
8 array.push(y);
9 }
10
11 function countingSort(array) {
12 var len = array.length,
13 B = [],
14 C = [],
15 min = max = array[0];
16 console.time(' ');
17 for (var i = 0; i < len; i++) {
18 min = min <= array[i] ? min : array[i];
19 max = max >= array[i] ? max : array[i];
20 C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
21 }
22
23 //
24 for (var j = min; j < max; j++) {
25 C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
26 }
27 for (var k = len - 1; k >= 0; k--) {
28 B[C[array[k]] - 1] = array[k];
29 C[array[k]]--;
30 }
31 console.timeEnd(' ');
32 return B;
33 }
34
35
36 console.log(countingSort(array)); // :41.35205078125ms
기수 정렬:
1 //Js
2
3 /* , , 。
4 , ( , ) ,
5 10 100 。 , ( ),
6 , , ( ), , ,
7 , , 。*/
8
9 var array = [];
10
11 for(var i=0;i<100000;i++){
12 var x = Math.random()*100000;
13 var y = Math.floor(x);
14 array.push(y);
15 }
16
17 function radixSort(arr, maxDigit) {
18 var mod = 10;
19 var dev = 1;
20 var counter = [];
21 console.time(' ');
22 for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
23 for(var j = 0; j < arr.length; j++) {
24 var bucket = parseInt((arr[j] % mod) / dev);
25 if(counter[bucket]== null) {
26 counter[bucket] = [];
27 }
28 counter[bucket].push(arr[j]);
29 }
30 var pos = 0;
31 for(var j = 0; j < counter.length; j++) {
32 var value = null;
33 if(counter[j]!=null) {
34 while ((value = counter[j].shift()) != null) {
35 arr[pos++] = value;
36 }
37 }
38 }
39 }
40 console.timeEnd(' ');
41 return arr;
42 }
43
44 //console.log(radixSort(array,1)); // : 32.949951171875ms
45
46
47 console.log(radixSort(array,2)); // : 66.570068359375ms
48
49
50 // , 。
51 /* vs vs
52
53 , :
54
55 :
56 :
57 : */
병합 정렬:
1 //Js
2
3 /* , ,
4 。 ,
5 , , ,
6 1 2, , 1, ,
7 , , , 。
8 , , , , 。*/
9
10 var array = [];
11
12 for(var i=0;i<100000;i++){
13 var x = Math.random()*100000;
14 var y = Math.floor(x);
15 array.push(y);
16 }
17
18 function mergeSort(arr) { //
19 var len = arr.length;
20 if(len < 2) {
21 return arr;
22 }
23 var middle = Math.floor(len / 2),
24 left = arr.slice(0, middle),
25 right = arr.slice(middle);
26 return merge(mergeSort(left), mergeSort(right));
27 }
28
29 function merge(left, right){
30 var result = [];
31
32 while (left.length && right.length) {
33 if (left[0] <= right[0]) {
34 result.push(left.shift());
35 } else {
36 result.push(right.shift());
37 }
38 }
39
40 while (left.length){
41 result.push(left.shift());
42 }
43 while (right.length){
44 result.push(right.shift());
45 }
46
47 return result;
48 }
49
50 var abc = function(){
51 console.time(' ');
52 var efg = mergeSort(array);
53 console.timeEnd(' ');
54 }
55
56 abc(); // :194.84814453125ms
더미 정렬:
1 //Js
2
3 var array = [];
4
5 for(var i=0;i<100000;i++){
6 var x = Math.random()*100000;
7 var y = Math.floor(x);
8 array.push(y);
9 }
10
11 function heapSort(array) {
12 console.time(' ');
13 //
14 var heapSize = array.length, temp;
15 for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
16 heapify(array, i, heapSize);
17 }
18 //
19 for (var j = heapSize - 1; j >= 1; j--) {
20 temp = array[0];
21 array[0] = array[j];
22 array[j] = temp;
23 heapify(array, 0, --heapSize);
24 }
25 console.timeEnd(' ');
26 return array;
27 }
28 function heapify(arr, x, len) {
29 var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
30 if (l < len && arr[l] > arr[largest]) {
31 largest = l;
32 }
33 if (r < len && arr[r] > arr[largest]) {
34 largest = r;
35 }
36 if (largest != x) {
37 temp = arr[x];
38 arr[x] = arr[largest];
39 arr[largest] = temp;
40 heapify(arr, largest, len);
41 }
42 }
43
44 console.log(heapSort(array)); // :50.8271484375ms
삽입 정렬:
1 //Js :
2
3 /* , 。 ,
4 , 。
5 , , ,
6 , , 。*/
7
8 var array = [];
9
10 for(var i=0;i<100000;i++){
11 var x = Math.random()*100000;
12 var y = Math.floor(x);
13 array.push(y);
14 }
15
16 function insertionSort(array) {
17 console.time(' :');
18 for (var i = 1; i < array.length; i++) {
19 var key = array[i];
20 var j = i - 1;
21 while ( array[j] > key) {
22 array[j + 1] = array[j];
23 j--;
24 }
25 array[j + 1] = key;
26 }
27 console.timeEnd(' :');
28 return array;
29 }
30
31 console.log(insertionSort(array)); // :: 33019.146240234375ms
32
33
34 // ( ):
35
36 function binaryInsertionSort(array) {
37 console.time(' :');
38 for (var i = 1; i < array.length; i++) {
39 var key = array[i], left = 0, right = i - 1;
40 while (left <= right) {
41 var middle = parseInt((left + right) / 2);
42 if (key < array[middle]) {
43 right = middle - 1;
44 } else {
45 left = middle + 1;
46 }
47 }
48 for (var j = i - 1; j >= left; j--) {
49 array[j + 1] = array[j];
50 }
51 array[left] = key;
52 }
53 console.timeEnd(' :');
54 return array;
55 }
56
57 console.log(binaryInsertionSort(array)); // : 4326.103759765625ms
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.