書かれたインタビューには、多くの場合、さまざまなアルゴリズムが含まれます。この記事では、一般的に使用されるいくつかのアルゴリズムを簡単に紹介し、それらをJavaScriptに実装します。
1.並べ替えを挿入します
1)アルゴリズムの紹介
挿入ソートのアルゴリズムの説明は、シンプルで直感的なソートアルゴリズムです。順序付けされたシーケンスを構築し、アンソートされていないデータのために動作し、ソートされたシーケンスの後方と前方をスキャンし、対応する位置を見つけて挿入します。挿入ソートの実装では、通常、インプレースのソートが使用されます(つまり、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){array [j + 1] = array [j]; j--; } array [j + 1] = key; } return array; } else {return '配列は配列ではありません!'; }}3)アルゴリズム分析
最良のケース:入力配列は昇順でソートされます。 t(n)= o(n)
最悪の場合:入力配列は降順でソートされます。 t(n)= o(n2)
平均:t(n)= o(n2)
2つ、バイナリ挿入ソート
1)アルゴリズムの紹介
Binary-Insert Sortingは、直接挿入ソートアルゴリズムをわずかに変更するソートアルゴリズムです。それと直接挿入ソートアルゴリズムの最大の違いは、挿入位置を探すときにバイナリ検索方法が使用され、速度が一定の改善があることです。
2)アルゴリズムの説明と実装
一般的に、挿入ソートは、インプレースを使用して配列に実装されます。特定のアルゴリズムは次のように説明されています。
最初の要素から始めて、要素はソートされたと見なすことができます。
次の要素を取り出し、すでにソートされた一連の要素シーケンスで最初の数値の位置を見つけます。
新しい要素をその位置に挿入した後。
上記の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(key <array [middle]){right = middle -1; } else {left = middle + 1; }} for(var j = i-1; j> = left; j-){array [j + 1] = array [j]; } array [左] = key; } return array; } else {return '配列は配列ではありません!'; }}3)アルゴリズム分析
ベストケース:t(n)= o(nlogn)
最悪の場合:t(n)= o(n2)
平均:t(n)= o(n2)
3.ソートを選択します
1)アルゴリズムの紹介
選択ソートは、シンプルで直感的なソートアルゴリズムです。それがどのように機能するか:まず、非オルティングシーケンスで最小の(大きな)要素を見つけ、ソートされたシーケンスの開始位置に保存し、残りの未解決の要素から最小(大きな)要素を探し続けてから、ソートされたシーケンスの端に配置します。すべての要素がソートされるまで。
2)アルゴリズムの説明と実装
Nレコードの直接選択は、N-1パスを介して取得して、直接選択してソートすることができます。特定のアルゴリズムは次のように説明されています。
初期状態:順序付けられていない領域はR [1..n]であり、順序付けられた領域は空です。
I-Th-Ordering(i = 1,2,3 ... n-1)が開始されると、現在の順序付き領域と順序付けられていない領域はそれぞれR [1..i-1]とR(i..n)です。この順序は、現在の順序付けられていない領域から最小のキーワードでレコードr [k]を選択し、順序付けられていない領域の最初のレコードRと交換するため、R [1..I]とr [I+1..n)は、記録数が1つ増加し、記録数が1つ減少した新しい順序領域が1つ増加する新しい秩序領域になります。
N-1トリップは終了し、配列が順序付けられます。
JavaScriptコードの実装:
function 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; min = array [j];配列[j] = temp; }} array [i] = min; } return array; } else {return '配列は配列ではありません!'; }}3)アルゴリズム分析
最良のケース:t(n)= o(n2)
最悪の場合:t(n)= o(n2)
平均:t(n)= o(n2)
4。バブルソート
1)アルゴリズムの紹介
バブルソートは、シンプルなソートアルゴリズムです。ソートするシーケンスを繰り返し訪れ、一度に2つの要素を比較し、それらが正しくない場合にそれらを交換します。シーケンスにアクセスする作業は、交換が不要になるまで繰り返されます。つまり、シーケンスがソートされました。このアルゴリズムの起源は、要素が小さいほど、Exchangeを介してシーケンスの上部にゆっくりと「フロート」するためです。
2)アルゴリズムの説明と実装
特定のアルゴリズムは次のように説明されています。
隣接する要素を比較します。最初のものが2番目のものよりも大きい場合、それらの2つを交換します。
最初のペアの先頭から最後のペアの終わりまで、隣接する要素の各ペアに対して同じ作業を行い、最後の要素が最大の数字であるようにします。
最後の要素を除くすべての要素の上記の手順を繰り返します。
ソートが完了するまで手順1〜3を繰り返します。
JavaScriptコードの実装:
function 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]; array [j] = array [j -1];配列[j -1] = temp; }}} return array; } else {return '配列は配列ではありません!'; }}3)アルゴリズム分析
最良のケース:t(n)= o(n)
最悪の場合:t(n)= o(n2)
平均:t(n)= o(n2)
5。クイックソート
1)アルゴリズムの紹介
クイックソートの基本的なアイデア:レコードを1つの順序で2つの独立した部分に分割すると、一部のレコードのキーワードは他の部分のキーワードよりも小さいです。その後、2つのレコードを継続して、シーケンス全体の順序を達成するために個別にソートします。
2)アルゴリズムの説明と実装
クイックソートでは、分割方法を使用して、文字列を2つのサブリストに分割します。特定のアルゴリズムは次のように説明されています。
シーケンスから要素を選択することは、「原理」(ピボット)と呼ばれます。
シーケンスを並べ替え、基準値よりも小さいすべての要素が参照の前に配置され、参照値よりも大きいすべての要素が参照の後ろに配置されます(同じ数字を両側に配置できます)。このパーティションが終了すると、参照はシーケンスの中央にあります。これはパーティション操作と呼ばれます。
参照要素よりも小さいサブシーケンスと、参照要素よりも大きいサブシーケンスを再帰的に並べ替えます。
JavaScriptコードの実装:
// 1つの関数QuickSort(配列、左、右){if(object.prototype.tostring.call(array).slice(8、-1)========= === == 'array' && typeof左=== 'number' && typeof右=== 'number') for(var j =左; j <=右; j ++){if(array [j] <= x){i ++; temp = array [i];配列[i] = array [j];配列[j] = temp; }} QuickSort(配列、左、i -1); QuickSort(配列、I + 1、右); }; } else {return '配列は配列ではないか、左または右は数字ではありません!'; }} 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 left = []; var right = []; 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(右))を返します。 };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 ... RN-2)(RN-2)と新しい順序領域(RN-2)を取得するために再び順序付きエリアの最後の要素を交換する必要があります。順序付けられた領域の要素の数がN-1になり、並べ替えプロセス全体が完了するまで、このプロセスを繰り返します。
JavaScriptコードの実装:
/*メソッドの説明:ヒープソート@param配列のソートをソートする*/function heapsort(array){if(object.prototype.tostring.call).slice(8、-1)=== 'array'){//ビルドヒープvar heapsize = array.length、temp; for(var i = math.floor(Heapsize / 2); i> = 0; i-){heapify(array、i、Heapsize); } //(var j = Heapsize-1; j> = 1; j-){temp = array [0]; array [0] = array [j];配列[j] = temp; heapify(array、0、 - heapsize); }} else {return '配列は配列ではありません!'; }}/ *メソッド説明:ヒープのプロパティを維持@param array @param x array subscript @param len heap size */function heapify(arr、x、len){if(object.prototype.tostring.call(arr).slice(arr).slice(8、-1)== 'array' && typof x = = 'x x x x x x x x = 2 2 1、最大= x、温度; if(l <len && arr [l]> arr [最大]){最大= l; } if(r <len && arr [r]> arr [rigast]){olagest = r; } if(最大!= x){temp = arr [x]; arr [x] = arr [最大]; arr [最大] = temp; Heapify(arr、light、len); }} else {return 'arrは配列ではないか、xは数字ではありません!'; }}3)アルゴリズム分析
ベストケース:t(n)= o(nlogn)
最悪の場合:t(n)= o(nlogn)
平均:t(n)= o(nlogn)
7。注文
1)アルゴリズムの紹介
マージソートは、マージ操作に基づいて効果的なソートアルゴリズムです。このアルゴリズムは、Divide and Conquerの非常に典型的なアプリケーションです。マージソートは、安定した選別方法です。順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、各サブセンセンスを最初に行い、次にサブシーケンスセグメントを順序にします。 2つの順序付けられたテーブルが1つの順序テーブルにマージされている場合、2ウェイマージと呼ばれます。
2)アルゴリズムの説明と実装
特定のアルゴリズムは次のように説明されています。
長さnの入力シーケンスを長さn/2の2つのサブシーケンスに分けます。
これらの2つのサブシーケンスは、個別にソートされます。
2つのソートされたサブシーケンスを最終的なソートされたシーケンスにマージします。
JavaScriptコードの実装:
関数mergesort(array、p、r){if(p <r){var q = math.floor((p + r) / 2); Mergesort(配列、P、Q); mergesort(array、q + 1、r);マージ(配列、P、Q、R); }} function merge(array、p、q、r){var n1 = q -p + 1、n2 = r -q、left = []、right = []、m = n = 0; for(var i = 0; i <n1; i ++){left [i] = array [p+i]; } for(var j = 0; j <n2; j ++){right [j] = array [q + 1 + j]; }左[n1] =右[n2] = number.max_value; for(var k = p; k <= r; k ++){if(left [m] <= right [n]){array [k] = left [m]; M ++; } else {array [k] = right [n]; n ++; }}}3)アルゴリズム分析
最良のケース:t(n)= o(n)
最悪の場合:t(n)= o(nlogn)
平均:t(n)= o(nlogn)
8。バケットソート
1)アルゴリズムの紹介
バケットソートの原理:入力データが均一に分散されていると仮定すると、データは限られた数のバケツに分割され、各バケットは個別にソートされます(他のソートアルゴリズムを使用するか、バケットソートを再帰的に使用し続けることができます)。
2)アルゴリズムの説明と実装
特定のアルゴリズムは次のように説明されています。
定量的な配列を空のバケツとして設定します。
入力データを繰り返し、データを対応するバケットに1つずつ入れます。
空ではない各バケツを並べ替えます。
空のバケツからソートされたデータをスプライスします。
JavaScriptコードの実装:
/*メソッド説明:バケットソート@paramアレイ@param num num num num of buckets*/ function bucketsort(array、num){if(array.length <= 1){return array; } var len = array.length、backets = []、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 <= array [i]? min:array [i]; max = max> = array [i]? max:array [i]; } space =(max -min + 1) / num; for(var j = 0; j <len; j ++){var index = math.floor((array [j] - min) / space); if(buckets [index]){//空だったバケツ、sort var k = buckets [index] .length -1; while(k> = 0 && buckets [index] [k]> array [j]){buckets [index] [k + 1] = buckets [index] [k]; k--; } buckets [index] [k + 1] = array [j]; } else {//空のバケット、バケツを初期化[index] = [];バケット[index] .push(array [j]); }} while(n <num){result = result.concat(buckets [n]); n ++; } return result; }3)アルゴリズム分析
バケットソートの最良のケース、線形時間O(n)では、バケットソートの時間の複雑さは、他の部分の時間の複雑さがO(n)であるため、バケツ間のデータソートデータの時間の複雑さに依存します。明らかに、バケツが小さいほど、バケットのデータが少ないほど、それを並べ替えるのに時間が短くなります。しかし、対応するスペース消費は増加します。
9。カウントソート
1)アルゴリズムの紹介
カウントソートは、安定したソートアルゴリズムです。 Count Sortingは追加の配列Cを使用します。ここで、i番目の要素は、ソートされる配列Aのiに等しい値を持つ要素の数です。次に、配列Cによると、Aの要素は正しい位置に配置されます。整数のみをソートすることができます。
2)アルゴリズムの説明と実装
特定のアルゴリズムは次のように説明されています。
ソートする配列内の最大の要素と最小の要素を見つけます。
配列内のiの値を持つ各要素の数をカウントし、それを配列cのi番目のアイテムに保存します。
すべてのカウントを蓄積します(Cの最初の要素から始まり、各アイテムと前のアイテムが追加されます)。
逆ターゲットアレイ:各要素を新しい配列のc(i)項目に配置し、各要素に対してc(i)を1 x rupctryします。
JavaScriptコードの実装:
function countingsort(array){var len = array.length、b = []、c = []、min = max = array [0]; for(var i = 0; i <len; i ++){min = min <= array [i]? min:array [i]; max = max> = array [i]? max:array [i]; c [array [i]] = c [array [i]]? c [配列[i]] + 1:1; } for(var j = min; j <max; j ++){c [j + 1] =(c [j + 1] || 0) +(c [j] || 0); } for(var k = len -1; k> = 0; k-){b [c array [k]] -1] = array [k]; c [array [k]] - ; } burten b; }3)アルゴリズム分析
入力要素が0からkの間のn整数である場合、その実行時間はO(n + k)です。カウントソートは比較ソートではなく、ソート速度はどの比較ソートアルゴリズムよりも高速です。カウントするために使用される配列cの長さは、ソートする配列内のデータの範囲に依存するため(ソートする配列の最大値と最小値の差に等しいと等しい)、これにより、カウントソートには、大きなデータ範囲を持つ配列に多くの時間とメモリが必要になります。