bubbleSort
氣泡排序
by Chris_Walter
JavaScript
class ArrayList{
constructor(){
this.array = [];
}
insert(item){
this.array.push(item);
}
toString(){
return this.array.join();
}
// 第一個比第二個大就交換位置
swap(A, B){
[this.array[A], this.array[B]] = [this.array[B], this.array[A]];
}
sort(){
this.array.sort((a,b) => {
return a - b; //由小到大排序
});
}
bubbleSort(){
let length = this.array.length;
for(let i=0; i<length - 1; i++ ){
for(let j=0; j<length-i-1; j++){
if(this.array[j] > this.array[j+1]){
this.swap(j, j + 1);
}
}
}
}
}
/*
// 由大到小
const nonSortedArray = (arraySize) => {
const array = new ArrayList();
for(let i=arraySize; i>0; i--){
array.insert(i);
}
console.log(`未使用冒泡排序前: ${array}`);
array.bubbleSort();
console.log(`冒泡排序後: ${array}`);
return array;
}
// 由小到大
const SortedArray = (arraySize) => {
const array = new ArrayList();
for(let i=0; i<arraySize; i++){
array.insert(i);
}
console.log(`未使用合併排序前: ${array}`);
array.bubbleSort();
console.log(`合併排序後: ${array}`);
}
*/
// 亂數
const nonSortedArray = (arraySize) => {
const array = new ArrayList();
for(let i=0; i<arraySize; i++){
array.insert(Math.random()*100);
}
console.time();
//array.bubbleSort();
array.sort();//使用JavaScript內建的排序方法
console.timeEnd();
}
nonSortedArray(100000);
//假設資料量100000筆，此演算法複雜度是O(n²) 表示要100000²次的比較運算
//假設電腦1秒能跑40億次的指令，經過計算大概要花23s，JavaScript內建的排序方法則是花0.04 秒