JavaScript並べ替え——発泡法の並べ替え

2965 ワード

どのような泡の並べ替えですか?
泡の並べ替え(昇順の場合)は一連の無秩序な数で、隣の数を比較して、もし前の数が後ろの数より大きいならば、交換位置、第1ラウンドは一番大きいのを得て、一番右側に泡が出ます.二番目の大きさの数が右から二番目の位置に泡を作ります.これをもって類推して、最後の順序付けられたシーケンスが得られます.
最も一般的なコードは、このコードが最も考えられやすいです.
/**
 * @desc      (    )
 * @param {Array} arr        
 */
var bubbleSort= function(arr){
  //     
  if(arr.length <= 1) return arr
  //     ,         -1      
  for(let i=arr.length-1, tmp; i>0 ;i--){
    //     
    for(let j=0; j arr[j+1]){
        arr[j] = arr[j+1]
        arr[j+1] = tmp
      }
    }
  }
  return arr
}
時間の複雑さと空間の複雑さ
平均時間複雑度:O(n^2)の場合が望ましい:O(n)の最悪の場合:O(n^2)空間複雑度:O(1)安定性:安定性
どのように計算された時間の複雑さ:time=(n-1)+(n-2)+(n-3)+.+2+1=n*(n-1)/2ですので、時間の複雑さはO(n^2)です.
泡の並べ替え時間の複雑さはまだ高いです.大量のデータに対しては使わないほうがいいです.
最適化して、ここは最も愚かから最適化の情況まで貼り付けます.
/**
 * @description            
 * @param {Array} arr       
 * @return       
 */

let arr = [4, 3, 2, 1];
let arr1 = [1,2,3,4,5];

//    
function bubbleSort1(arr) {
  let max = arr.length - 1;
  for (let j = 0; j < max; j++) {
    console.log(" " + (j + 1) + "   :")
    for (let i = 0; i < max; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
      console.log(arr)
    }
  }
  // return arr
}


//   1:    ,                 。
function bubbleSort2 (arr) {
  //     
  if (arr.length <= 1) return arr
  //     
  for (let i = arr.length - 1, tmp; i > 0; i--) {
    console.log(" " + (arr.length-i) + "   :")
    //     
    for (let j = 0; j < i; j++) {
      tmp = arr[j]
      //             ,    
      if (arr[j] > arr[j + 1]) {
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
      }
      console.log(arr)
    }
  }
  // return arr
}

//   2:       ,          ,       
function bubbleSort3(arr) {
  let max = arr.length - 1;
  let temp = [];
  for (let j = 0; j < max; j++) { //  j   
    console.log(" " + (j + 1) + "   :")
    let done = true;        //   1:       ,          ,       
    for (let i = 0; i < max - j; i++) { //          
      if (arr[i] > arr[i + 1]) {  //    
        temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        done = false;
      }
      console.log(arr)
    }
    if (done) break; //     
  }
  // return arr
}

//   3:       
function bubbleSort4(arr) {
  let sortBorder = arr.length - 1;
  let temp = [];
  let lastChangeIndex = 0;
  for (let j = 0; j < arr.length; j++) {
    console.log(" " + (j + 1) + "   :")
    let done = true;
    for (let i = 0; i < sortBorder; i++) {
      if (arr[i] > arr[i + 1]) {
        temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        done = false;
        lastChangeIndex = i;
      }
      console.log(arr)
    }
    sortBorder = lastChangeIndex;
    if (done) break;
  }
  // return arr
}