JSフロントエンドの面接は必須です。基本的な並べ替えアルゴリズムの原理と実現方法を詳しく解説します。
本論文の実例は、JSフロントエンドの面接に必要なものである。皆さんに参考にしてあげます。具体的には以下の通りです。
並べ替えのアルゴリズムは面接と筆記試験の中で必ず試験するので、本文はアニメーションの方式を通じて実証して、実例を通じて説明して、最後にJavaScript版の並べ替えのアルゴリズムを提供します。
並べ替えの挿入
アルゴリズムの説明:
1.最初の要素から、この要素は並べ替えられたと考えられます。
2.次の要素を取り出して、並べ替えられた元素系列の中で後ろから前へスキャンします。
3.要素が新しい要素より大きい場合は、要素を次の位置に移動します。
4.並べ替えられた要素が新しい要素より小さいかまたは等しい位置にあるまで、ステップ3を繰り返します。
5.新しい要素をその位置に挿入した後
6.手順2~5を繰り返す
既存の配列arr=[5,6,3,1,8,7,2,4]
並べ替えを選択
アルゴリズムの説明:直接並べ替え行列から最小(または最大)の数字を選択して、新しい配列に入れます。
並べ替え
アルゴリズムの説明:
1.n個の記録をn個の長さlの秩序子表と見なす。
2.二つの帰納を行い、記録キーワードを秩序化させ、n/2個の長さが2の秩序あるサブテーブルを得る。
3.すべての記録がnの長さの秩序表になるまで、第2のステップを繰り返す。
クイックソート
アルゴリズムの説明:は、データセットの中から、一つの要素を「基準」として選択します。 「基準」以下の要素は、「基準」の左側に移動します。「基準」より大きいすべての要素は、「基準」の右側に移動します。この操作はパーティション操作といい、パーティション操作が終了したら基準要素の位置が最終的に並べ替えられた位置です。 ペアの「基準」の左と右の2つのサブセットは、すべてのサブセットが1つの要素だけになるまで、第1および第2のステップを繰り返します。
その場のパーティションのバージョン:主な違いは先にパーティションの処理を行うことです。
泡の並べ替え
アルゴリズムの説明:
1.隣接する要素を比較します。一番目が二番目より大きいなら、二人を交換します。
2.各ペアの隣接要素に対して同じ作業を行い、最初のペアから最後のペアまでを行います。この点では、最後の要素は最大の数になるはずです。
3.すべての要素に対して上記のステップを繰り返します。最後を除いて。
4.継続的に毎回少なくなる要素に対して上のステップを繰り返して、数字のペアがないまで比較が必要です。5.
関心のある友達はオンラインHTML/CSS/JavaScriptコードを使ってツールを実行できます。http://tools.jb51.net/code/HtmlJsRunは上記のコードの運行効果をテストします。
PS:ここでは並べ替えに関するデモンストレーションを紹介します。
オンラインアニメーションのデモ挿入/選択/発泡/帰結/ヒル/高速ソートアルゴリズムプロセスツール:
http://tools.jb51.net/aideddesign/paixu_システム
JavaScriptに関する多くの内容に興味がある読者は、本駅のテーマを見てもいいです。「JavaScript数学演算の使い方のまとめ」、「JavaScriptデータ構造とアルゴリズム技術のまとめ」、「JavaScript配列操作技術のまとめ」、「JavaScriptソートアルゴリズムのまとめ」、「JavaScriptはアルゴリズムと技術の総括を遍歴します。」、「JavaScript検索アルゴリズムのテクニックのまとめ」および「JavaScriptエラーとデバッグテクニックのまとめ」
本論文で述べたように、JavaScriptプログラムの設計に役に立ちます。
並べ替えのアルゴリズムは面接と筆記試験の中で必ず試験するので、本文はアニメーションの方式を通じて実証して、実例を通じて説明して、最後にJavaScript版の並べ替えのアルゴリズムを提供します。
並べ替えの挿入
アルゴリズムの説明:
1.最初の要素から、この要素は並べ替えられたと考えられます。
2.次の要素を取り出して、並べ替えられた元素系列の中で後ろから前へスキャンします。
3.要素が新しい要素より大きい場合は、要素を次の位置に移動します。
4.並べ替えられた要素が新しい要素より小さいかまたは等しい位置にあるまで、ステップ3を繰り返します。
5.新しい要素をその位置に挿入した後
6.手順2~5を繰り返す
既存の配列arr=[5,6,3,1,8,7,2,4]
[5] 6 3 1 8 7 2 4 //
[5,6] 3 1 8 7 2 4 //6 5 , 5
[3,5,6] 1 8 7 2 4 //3 6 5 , ,
[1,3,5,6] 8 7 2 4 //1 3,5,6 ,
[1,3,5,6,8] 7 2 4
[1,3,5,6,7,8] 2 4
[1,2,3,5,6,7,8] 4
[1,2,3,4,5,6,7,8]
プログラムの考え方:二層循環、外循環制御がソートされていない要素、内循環制御がソートされている要素、未ソート要素をバーとして設定し、並べ替えられた要素と比較して、小さい場合は交換位置、大きい場合は位置が動かない。
function insertSort(arr){
var tmp;
for(var i=1;i<arr.length;i++){
tmp = arr[i];
for(var j=i;j>=0;j--){
if(arr[j-1]>tmp){
arr[j]=arr[j-1];
}else{
arr[j]=tmp;
break;
}
}
}
return arr
}
時間複雑度O(n^2)並べ替えを選択
アルゴリズムの説明:直接並べ替え行列から最小(または最大)の数字を選択して、新しい配列に入れます。
[1] 5 6 3 8 7 2 4
[1,2] 5 6 3 8 7 4
[1,2,3] 5 6 8 7 2 4
[1,2,3,4] 5 6 8 7
[1,2,3,4,5] 6 8 7
[1,2,3,4,5,6] 8 7
[1,2,3,4,5,6,7] 8
[1,2,3,4,5,6,7,8]
プログラムの考え方:まず最初の要素が最小であると仮定して、循環によって最小要素を探して、そして最初の要素と交換して、次に第二の要素を仮定して、上記の操作を繰り返してもいいです。
function selectSort(array) {
var length = array.length,
i,
j,
minIndex,
minValue,
temp;
for (i = 0; i < length - 1; i++) {
minIndex = i;
minValue = array[minIndex];
for (j = i + 1; j < length; j++) {//
if (array[j] < minValue) {
minIndex = j;
minValue = array[minIndex];
}
}
//
temp = array[i];
array[i] = minValue;
array[minIndex] = temp;
}
return array
}
時間複雑度O(n^2)並べ替え
アルゴリズムの説明:
1.n個の記録をn個の長さlの秩序子表と見なす。
2.二つの帰納を行い、記録キーワードを秩序化させ、n/2個の長さが2の秩序あるサブテーブルを得る。
3.すべての記録がnの長さの秩序表になるまで、第2のステップを繰り返す。
5 6 3 1 8 7 2 4
[5,6] [3,1] [8,7] [2,4]
[5,6] [1,3] [7,8] [2,4]
[5,6,1,3] [7,8,2,4]
[1,3,5,6] [2,4,7,8]
[1,2,3,4,5,6,7,8]
プログラミングの考え方:配列を常に等分し、統合します。
function merge(left, right) {
var tmp = [];
while (left.length && right.length) {
if (left[0] < right[0])
tmp.push(left.shift());
else
tmp.push(right.shift());
}
return tmp.concat(left, right);
}
function mergeSort(a) {
if (a.length === 1)
return a;
var mid = Math.floor(a.length / 2)
, left = a.slice(0, mid)
, right = a.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
時間複雑度O(nlogn)クイックソート
アルゴリズムの説明:
5 6 3 1 8 7 2 4
pivot
|
5 6 3 1 9 7 2 4
|
storeIndex
5 6 3 1 9 7 2 4// 5 6 ,
|
storeIndex
3 6 5 1 9 7 2 4// 5 3 ,
|
storeIndex
3 6 1 5 9 7 2 4// 5 1 ,
|
storeIndex
...
3 6 1 4 9 7 2 5// 5 4 ,
|
storeIndex
3 6 1 4 5 7 2 9//
|
storeIndex pivot
上のようにパーティションの過程を説明しました。そして各サブエリアに対して同じやり方を行います。
function quickSort(arr){
if(arr.length<=1) return arr;
var partitionIndex=Math.floor(arr.length/2);
var tmp=arr[partitionIndex];
var left=[];
var right=[];
for(var i=0;i<arr.length;i++){
if(arr[i]<tmp){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return quickSort(left).concat([tmp],quickSort(right))
}
上記のバージョンはスタックオーバーフローの原因となりますので、以下のバージョンを使用してください。その場のパーティションのバージョン:主な違いは先にパーティションの処理を行うことです。
function quickSort(arr){
function swap(arr,right,left){
var tmp = arr[right];
arr[right]=arr[left];
arr[left]=tmp;
}
function partition(arr,left,right){// ,
var pivotValue=arr[right]//
var storeIndex=left;
for(var i=left;i<right;i++){
if(arr[i]<=pivotValue){
swap(arr,storeIndex,i);
storeIndex++;
}
}
swap(arr,right,storeIndex);
return storeIndex//
}
function sort(arr,left,right){
if(left>right) return;
var storeIndex=partition(arr,left,right);
sort(arr,left,storeIndex-1);
sort(arr,storeIndex+1,right);
}
sort(arr,0,arr.length-1);
return arr;
}
時間複雑度O(nlogn)泡の並べ替え
アルゴリズムの説明:
1.隣接する要素を比較します。一番目が二番目より大きいなら、二人を交換します。
2.各ペアの隣接要素に対して同じ作業を行い、最初のペアから最後のペアまでを行います。この点では、最後の要素は最大の数になるはずです。
3.すべての要素に対して上記のステップを繰り返します。最後を除いて。
4.継続的に毎回少なくなる要素に対して上のステップを繰り返して、数字のペアがないまで比較が必要です。5.
5 6 3 1 8 7 2 4
[5 6] 3 1 8 7 2 4 // 5 6
5 [6 3] 1 8 7 2 4
5 3 [6 1] 8 7 2 4
5 3 1 [6 8] 7 2 4
5 3 1 6 [8 7] 2 4
5 3 1 6 7 [8 2] 4
5 3 1 6 7 2 [8 4]
5 3 1 6 7 2 4 8 // ,
プログラムの考え方:外循環制御は比較的な要素が必要です。例えば、最初の並べ替えの後、最後の要素は比較が必要ではないです。内循環は2つの要素の比較を担当して、元素を正しい位置に置いてください。
function bubbleSort(arr){
var len=arr.length;
for(var i=len-1;i>0;i--){
for(var j=0;j<i;j++){
if(arr[j]>arr[j+1]){
var tmp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp
}
}
}
return arr;
}
時間複雑度O(n^2)関心のある友達はオンラインHTML/CSS/JavaScriptコードを使ってツールを実行できます。http://tools.jb51.net/code/HtmlJsRunは上記のコードの運行効果をテストします。
PS:ここでは並べ替えに関するデモンストレーションを紹介します。
オンラインアニメーションのデモ挿入/選択/発泡/帰結/ヒル/高速ソートアルゴリズムプロセスツール:
http://tools.jb51.net/aideddesign/paixu_システム
JavaScriptに関する多くの内容に興味がある読者は、本駅のテーマを見てもいいです。「JavaScript数学演算の使い方のまとめ」、「JavaScriptデータ構造とアルゴリズム技術のまとめ」、「JavaScript配列操作技術のまとめ」、「JavaScriptソートアルゴリズムのまとめ」、「JavaScriptはアルゴリズムと技術の総括を遍歴します。」、「JavaScript検索アルゴリズムのテクニックのまとめ」および「JavaScriptエラーとデバッグテクニックのまとめ」
本論文で述べたように、JavaScriptプログラムの設計に役に立ちます。