泡並べ替えアルゴリズム(JavaScript実装)

1184 ワード

アルゴリズムフロー
隣接する要素を比較すると、最初のペアが2番目より大きい場合は、交換し、最初のペアから最後のペアまで同じ作業を行い、毎回以上のステップを繰り返します.arr.length-1を遍歴した後、すべての要素を遍歴しました.
複雑さ
時間の複雑さはO(n^2)です.
コードの実装
コード:
function bubbleSort(arr){
  for(var i = 0; i < arr.length-1; i++){
    for(var j = 0;j < arr.length-i;j++){
      if(arr[j] > arr[j+1]){
        var t = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = t;
      }
    }
  }
  
  return arr;
}

var arr = [1,4,2,5,3];
bubbleSort(arr); // [1 , 2 , 3 , 4 , 5]
アルゴリズム最適化
順序配列が[1,3,5,6,7,8,9,2]の場合:第1の順序付けの結果は:1 3,5,6,8のシーケンスはすでに完了していますが、上記のコードに基づいて、第9の順序付けまで継続します.これは明らかに不合理です.コードにflagGマークを入れて前の順序で交換したことがありますか?もし交換しなかったら、現在の配列と秩序を説明します.コードは以下の通りです
function bubbleSort(arr){
  var flag = true;
  while(true){
    flag = false;
    for(var i = 0; i < arr.length-1; i++){
      for(var j = 0;j < arr.length-i;j++){
        if(arr[j] > arr[j+1]){
          var t = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = t;
          flag = true;
        }
      }
    } 
  }
  
  return arr;
}

var arr = [1, 3, 4, 5, 6, 7, 8, 9, 2];
bubbleSort(arr);  //[1, 2, 3, 4, 5, 6, 7, 8, 9]