泡並べ替えアルゴリズム(JavaScript実装)
1184 ワード
アルゴリズムフロー
隣接する要素を比較すると、最初のペアが2番目より大きい場合は、交換し、最初のペアから最後のペアまで同じ作業を行い、毎回以上のステップを繰り返します.
複雑さ
時間の複雑さはO(n^2)です.
コードの実装
コード:
順序配列が[1,3,5,6,7,8,9,2]の場合:第1の順序付けの結果は:1 3,5,6,8のシーケンスはすでに完了していますが、上記のコードに基づいて、第9の順序付けまで継続します.これは明らかに不合理です.コードにflagGマークを入れて前の順序で交換したことがありますか?もし交換しなかったら、現在の配列と秩序を説明します.コードは以下の通りです
隣接する要素を比較すると、最初のペアが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]