Javascriptの中の発泡体の並べ替え、挿入順序、選択順序、迅速な並べ替え、並べ替え、積み上げアルゴリズムの性能分析
26774 ワード
アリさんの面接ではこんな問題がありました.
JavaScript言語で実現してください. ソフト 並べ替え関数、要求:sort([5, 100, 6, 3, -12)) // 戻る [-12, 3, 5, 6, 100)いろいろな解法があるなら、いろいろな解法の考え方と長所と短所を説明してください.(コードを使って一つの解法を実現するだけで、他の解法は文字で考えを説明すればいいです.)
いろいろな解法の考え方と長所短所を見てみましょう.
簡単な並べ替え
1発泡法:
原理:元のデータを保存する配列に対して、往後の方向から複数回スキャンを行い、毎回スキャンすることを一回といいます.隣接する2つのデータの順序が要求と異なることが判明した場合、2つのデータが交換されます.最初のスキャンが終了したら、すべてのデータが要求に適合するまで、2回目のスキャンが行われます.
利点:
平均時間複雑度O(n＊n)は,比較的容易に実現できるアルゴリズムであり,比較的安定している.
短所:
遅いです.隣の二つのデータしか移動できません.
利点:
簡単に実現して、安定して、速くて、少量のデータの比較に適します.時間の複雑さはO(n＊n)である.
短所:
効率が高くなく、比較回数が少ないほど、挿入点後のデータの移動が多くなります.データ量が大きいなら、チェーンを使ってこの問題を解決できます.
原理:順序付けされているデータ要素の中から最小(または最大)の要素を選択し、並べられた数列の最後に並べ替えられているデータ要素が全部並び終わるまで順番に置く.
利点:(n-1)の順序付けを行うと並べ替えができます.時間の複雑さはnの平方O(n＊n)です.
短所:比較回数が多いので、データの中から選んだ目標データは全部残りのデータと比較した結果です.
*注意と発泡体の並べ替えの違いは、順序から別のシーケンスまでで、発泡体の並べ替えは自分の順序であり、並べ替えの性能はやや発泡体の並べ替えより優れている.
クイックソート
原理:クイックソートは現在既知の速度で最も速いソート方法であり、ソート方法は私達の周知の二分法と脈々と受け継がれています.保証リストの前半部分は全部後半部以下で、それぞれ二つの部分を並べ替えます.このように前半部分を比較すると、後半部分と比較する必要がなくなります.この方法はデータ間の不必要な並べ替えが大幅に減少しました.したがって、効率が高いです.具体的な手順:一組のデータを昇順に並べ、先にデータa[x]を基準にして、a[x]を比較します.他のデータと並べ替えて、a[x]をデータのk番目に並べ、a[1]~a[k-1]の各々のデータをa[x]よりも小さくし、a[k＋1]~a[n]の各々のデータをa[k]よりも大きくして、同様の方法で両グループのデータを高速に並べ替える.
利点:速度が非常に速く、データ移動が少ない平均時間複雑度は(n＊log n)です.
短所:不安定
並べ替え:
原理:規格化された順序付けは、2つ以上の順序テーブルを新たな順序テーブルに統合することが多い.同じ元素の順序は変わらないのが特徴です.並べ替えデータには複数の情報が含まれています.その中のいずれかの情報によって並べ替えられています.他の情報ができるだけ入力順に並べられるように要求されています.これも速い順序より優位なところです.規格化された順序はデータの秩序に敏感ではなく、その時間の複雑さはいずれの場合もO(nlog 2 n)であるので、データノードのデータ量が大きいと適切ではない.インデックス操作に改造すれば効果は素晴らしいです.
長所と短所は原理で説明します.
原理:まず空のリストを作成して、帯の並べ替え数列の中で最大の数字を見つけて、空のリストの最後に追加して、元の数列から削除して、元の数列が空になるまで、上記のステップを繰り返します.
*挿入順序との違いに注意してください.積み上げ順序の複雑さはO(nlog n)、挿入順序はO(n＊n)、積み上げ順序の新しい空リストの役割は挿入順序の新しいものと同じですが、役割は同じです.
長所:効率が高く、最大数を見つけるには時間の複雑さはO(1)だけです.
短所:比較的複雑な実現
JavaScript言語で実現してください. ソフト 並べ替え関数、要求:sort([5, 100, 6, 3, -12)) // 戻る [-12, 3, 5, 6, 100)いろいろな解法があるなら、いろいろな解法の考え方と長所と短所を説明してください.(コードを使って一つの解法を実現するだけで、他の解法は文字で考えを説明すればいいです.)
いろいろな解法の考え方と長所短所を見てみましょう.
簡単な並べ替え
1発泡法:
原理:元のデータを保存する配列に対して、往後の方向から複数回スキャンを行い、毎回スキャンすることを一回といいます.隣接する2つのデータの順序が要求と異なることが判明した場合、2つのデータが交換されます.最初のスキャンが終了したら、すべてのデータが要求に適合するまで、2回目のスキャンが行われます.
利点:
平均時間複雑度O(n＊n)は,比較的容易に実現できるアルゴリズムであり,比較的安定している.
短所:
遅いです.隣の二つのデータしか移動できません.
1 var sortArray=new Array();
2 var temp;
3 sortArray=id_list.split(":");
4 for(var i=0;i<sortArray.length;i++)
5 {
6 for(var j=0;j<i;j++)
7 {
8
9 if(parseInt(sortArray[j])>parseInt(sortArray[i]))
10 {
11 temp=sortArray[j];
12 sortArray[j]=sortArray[i];
13 sortArray[i]=temp;
14 }
15 }
16 }利点:
簡単に実現して、安定して、速くて、少量のデータの比較に適します.時間の複雑さはO(n＊n)である.
短所:
効率が高くなく、比較回数が少ないほど、挿入点後のデータの移動が多くなります.データ量が大きいなら、チェーンを使ってこの問題を解決できます.
1 function insertSort(){
2 var A=[5,2,4,6,1,3];
3
4 document.write(" :")
5 for (var n = 0; n < A.length; n++) {
6 document.write(A[n] + " ");
7 }
8 document.write(" :"+A.length+"<br/>");
9 var key;
10 var i;
11 for(var j=1;j<A.length;j++){
12 key=A[j];
13 i=j-1;
14 while(i>-1&&A[i]>key){
15 A[i+1]=A[i];
16 i=i-1;
17 }
18 A[i+1]=key;
19
20 //
21 document.write(" " + j + " :")
22 for (var n = 0; n < A.length; n++) {
23 document.write(A[n] + " ");
24 }
25 document.write("<br />")
26 }
27 }原理:順序付けされているデータ要素の中から最小(または最大)の要素を選択し、並べられた数列の最後に並べ替えられているデータ要素が全部並び終わるまで順番に置く.
利点:(n-1)の順序付けを行うと並べ替えができます.時間の複雑さはnの平方O(n＊n)です.
短所:比較回数が多いので、データの中から選んだ目標データは全部残りのデータと比較した結果です.
*注意と発泡体の並べ替えの違いは、順序から別のシーケンスまでで、発泡体の並べ替えは自分の順序であり、並べ替えの性能はやや発泡体の並べ替えより優れている.
1 function selectSort(array) {
2 var min, temp; ;
3 for (var i = 0; i < array.length; i++) {
4 min = i;
5 for (var j = i + 1; j < array.length; j++) {
6 if (array[min] > array[j])
7 min = j;
8 }
9 if (min != i) {
10 temp = array[i];
11 array[i] = array[min];
12 array[min] = temp;
13 }
14 /* */
15 document.write(" + i + " :")
16 for (var n = 0; n < array.length; n++) {
17 document.write(array[n] + ",");
18 }
19
20 document.write("<br />")
21 /* */
22
23 }
24 }クイックソート
原理:クイックソートは現在既知の速度で最も速いソート方法であり、ソート方法は私達の周知の二分法と脈々と受け継がれています.保証リストの前半部分は全部後半部以下で、それぞれ二つの部分を並べ替えます.このように前半部分を比較すると、後半部分と比較する必要がなくなります.この方法はデータ間の不必要な並べ替えが大幅に減少しました.したがって、効率が高いです.具体的な手順:一組のデータを昇順に並べ、先にデータa[x]を基準にして、a[x]を比較します.他のデータと並べ替えて、a[x]をデータのk番目に並べ、a[1]~a[k-1]の各々のデータをa[x]よりも小さくし、a[k＋1]~a[n]の各々のデータをa[k]よりも大きくして、同様の方法で両グループのデータを高速に並べ替える.
利点:速度が非常に速く、データ移動が少ない平均時間複雑度は(n＊log n)です.
短所:不安定
1 var count = 0;
2 function quickSort(array, low, high) {
3 var temp;
4
5 if (low < high) {
6
7 var keypoint = QuickSortHelp(array, low, high);
8 count++;
9 document.write("<br /> ? + count + " ? ? ò ? á ? ?:")
10 for (var l = 0; l < array.length; l++) {
11 document.write(array[l] + ",");
12 }
13 quickSort(array, low, keypoint - 1);
14 quickSort(array, keypoint + 1, high);
15
16
17 }
18 }
19 function QuickSortHelp(array, low, high) {
20 while (low < high) {
21
22 while (low < high && array[low] <= array[high]) {
23 high--;
24 }
25 temp = array[low];
26 array[low] = array[high];
27 array[high] = temp;
28 while (low < high && array[low] <= array[high]) {
29 low++
30 }
31 temp = array[low];
32 array[low] = array[high];
33 array[high] = temp;
34
35 }
36 return low;
37 }
38 並べ替え:
原理:規格化された順序付けは、2つ以上の順序テーブルを新たな順序テーブルに統合することが多い.同じ元素の順序は変わらないのが特徴です.並べ替えデータには複数の情報が含まれています.その中のいずれかの情報によって並べ替えられています.他の情報ができるだけ入力順に並べられるように要求されています.これも速い順序より優位なところです.規格化された順序はデータの秩序に敏感ではなく、その時間の複雑さはいずれの場合もO(nlog 2 n)であるので、データノードのデータ量が大きいと適切ではない.インデックス操作に改造すれば効果は素晴らしいです.
長所と短所は原理で説明します.
1//source
2//dest
3//s
4//t
5 function mSort(source, dest, s, t) {
6 var m; //
7 var dest2 = new Array();
8 if (s == t) {
9 dest[s] = source[s];
10
11 }
12 else {
13 m = Math.floor((s + t) / 2);
14 mSort(source, dest2, s, m);
15 mSort(source, dest2, m+1 , t);
16 merge(dest2, dest, s, m, t);
17 /* */
18 document.write("<br /> + ++count + " :")
19 for (var n = 0; n < dest.length; n++) {
20 document.write(array[n] + ",");
21 }
22
23 }
24
25 }
26
27
28//source
29//dest
30//s
31//m
3233 function merge(source, dest, s, m, n) {
34 for (var j = m+1, k = s; j <= n && s <= m; k++) {
35 if (source[s] < source[j]) {
36 dest[k] = source[s++];
37 }
38 else {
39 dest[k] = source[j++];
40 }
41 }
42
43 // dest
44 if (s <= m) {
45 for (var l = 0; l <= m - s; l++) {
46 dest[k + l] = source[s+l];
47 }
48 }
49 if (j <= n) {
50 for (var l = 0; l <= n - j; l++) {
51 dest[k + l] = source[j+l];
52 }
53
54 }
55 } 原理:まず空のリストを作成して、帯の並べ替え数列の中で最大の数字を見つけて、空のリストの最後に追加して、元の数列から削除して、元の数列が空になるまで、上記のステップを繰り返します.
*挿入順序との違いに注意してください.積み上げ順序の複雑さはO(nlog n)、挿入順序はO(n＊n)、積み上げ順序の新しい空リストの役割は挿入順序の新しいものと同じですが、役割は同じです.
長所:効率が高く、最大数を見つけるには時間の複雑さはO(1)だけです.
短所:比較的複雑な実現
1 function heapSort(array) {
2 var temp;
3 var i;
4 for (i = Math.floor(array.length / 2); i >= 0; i--) {
5 heapAdjust(array, i, array.length - 1); // array
6 }
7 for (i = array.length - 1; i >= 0; i--) {
8 /* */
9 temp = array[i];
10 array[i] = array[0];
11 array[0] = temp;
12
13 /* */
14 heapAdjust(array, 0, i - 1);
15 /* */
16 document.write("<br /> + (array.length - i).toString() + " :")
17 for (var n = 0; n < array.length; n++) {
18 document.write(array[n] + ",");
19 }
20 /* */
21 }
22 }
23 //
24 //start
25 //max
26 function heapAdjust(array, start, max) {
27 var temp, j;
28 temp = array[start];//temp
29 for (j = 2 * start; j < max; j *= 2) {
30 if (j < max && array[j] < array[j + 1]) { //
31 ++j;
32
33 }
34 if (temp >= array[j])
35 break;
36 array[start] = array[j];
37 start = j;
38 }
39 array[start] = temp;
40
41 }