ホームページ > 記事 > ウェブフロントエンド > JS バブルソートの選択ソートと挿入ソートの例の分析

JS バブルソートの選択ソートと挿入ソートの例の分析

小云云オリジナル: 2017-12-14 09:25:122192ブラウズ

この記事では、JS ソートアルゴリズムのバブルソート、選択ソート、挿入ソートを主に紹介し、バブルソート、選択ソート、挿入ソートの概念、原理、実装方法をサンプルの形式で分析します。皆さんのお役に立てれば幸いです。

バブルソート:

配列内のデータについて、連続する 2 つの隣接する数値のサイズを比較します。

前のデータが後のデータより大きい場合は、2 つの数値を交換します。

時間計算量O(n^2)

function bubble(array){
 var temp;
 for(var i=0; i<arr.length; i++){
  for(var j=0; j<arr.length; j++){
   if(arr[j]>arr[j+1]){
    temp = arr[j+1];
    arr[j+1] =arr[j];
    arr[j]=temp;
   }
  }console.log(arr);
 }
}//冒泡排序

選択ソート:

まず元の配列から最小のデータを選択し、それを位置1のデータと交換します。

残りのn-1個のデータから次に小さいデータを選択し、2番目のデータと交換します。

最後の 2 つのデータが交換されるまで繰り返します。

時間計算量O(n^2)

function selectionSort(array){
 var min,temp;
 for(var i=0; i<array.length-1; i++){
  min=i;
  for(var j=i+1; j<array.length; j++){
   if(array[j]<array[min]){
    min=j;
   }
  }
  swap(array,min,i);
 }
 console.log(array);
}//选择排序
function swap(array,i,j){
 var temp =array[i];
 array[i]=array[j];
 array[j]=temp;
}//两个数字交换

挿入ソート:

まず、最初の 2 つのデータを小さいデータから大きいデータまで比較します。

次に、3番目のデータと最初に配置した2つのデータを比較し、3番目のデータを適切な位置に挿入します。等々。

(挿入ソートには2つのループがあります。外側のループは配列を1つずつ移動し、内側のループは外側のループで選択された要素をその前の数値と比較します。)

時間計算量O(n^2)

function insertSort(arr){
 var temp, j;
 for(var i=1; i<arr.length; i++){
  temp =arr[i];
  j=i;
  while(j>0 && arr[j-1]>temp){
   arr[j]=arr[j-1];
   j--;
  }
  arr[j]=temp;
 }
}

JS バブル ソートの選択ソートと挿入ソートの例の分析

関連記事

JS バブルソートの選択ソートと挿入ソートの例の分析