JavaScript並べ替え——発泡法の並べ替え
2965 ワード
どのような泡の並べ替えですか?
泡の並べ替え(昇順の場合)は一連の無秩序な数で、隣の数を比較して、もし前の数が後ろの数より大きいならば、交換位置、第1ラウンドは一番大きいのを得て、一番右側に泡が出ます.二番目の大きさの数が右から二番目の位置に泡を作ります.これをもって類推して、最後の順序付けられたシーケンスが得られます.
最も一般的なコードは、このコードが最も考えられやすいです.
平均時間複雑度: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)です.
泡の並べ替え時間の複雑さはまだ高いです.大量のデータに対しては使わないほうがいいです.
最適化して、ここは最も愚かから最適化の情況まで貼り付けます.
泡の並べ替え(昇順の場合)は一連の無秩序な数で、隣の数を比較して、もし前の数が後ろの数より大きいならば、交換位置、第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
}