DAY 9
5

## 用Javascript征服演算法 (5-bubble sort&實作)

Bubble Sort~~~像泡泡一樣會冒出排序好的集合喔~~~(最好這麼容易XD)

`````` for(var i = 0; i < list.length; i++) {
//將元素及LIST丟進去處理處理阿
}
``````

``````for(var i = 0; i < end - 1; i++) {
if(compare(list[i + 1], list[i]) < 0) {
swap(list, i + 1, i);

}

}

function swap(list, i, j) {
var ele = list[i];
list[i] = list[j];
list[j] = ele;
}
``````

``````var swapornot = 0;
for(var i = 0; i < end - 1; i++) {
if(compare(list[i + 1], list[i]) < 0) {
swap(list, i + 1, i);
swapornot = 1;
}

}
return swapornot;
``````

``````var times = 0;

function ascending(a, b) {return a - b;}

function swap(list, i, j) {
var ele = list[i];
list[i] = list[j];
list[j] = ele;
}

function bubbleTo(list, to, compare) {
var swapornot = 0;
for(var i = 0; i < to - 1; i++) {
if(compare(list[i + 1], list[i]) < 0) {
swap(list, i + 1, i);
swapornot = 1;
}

}

times++;
return swapornot;

}

function bubbleSort(list, compare) {

for(var i = 0; i < list.length; i++) {
var swap =  bubbleTo(list, list.length - i, compare);
if(!swap)
break;
}
}

var list = [10, 9, 1, 2, 5, 3, 8, 7];

bubbleSort(list, ascending);
console.log(list);
console.log(times);
``````

### 2 則留言

0

iT邦新手 4 級 ‧ 2013-10-01 21:22:20

0
azole
iT邦新手 5 級 ‧ 2013-10-01 21:34:52

bubble sort的複雜度：
Best case: O(n)
Worst case: O(n^2)
Avg. case: O(n^2)