algorithms

昨天被问到选择排序,插入排序,冒泡排序的时候,一时间有点懵逼。因为我只记得一种冒泡排序了(其实是选择排序。。。汗颜呐),之后,又说了一句:其实,排序可以用JS自带的 sort 函数 sort(function(a,b){return a-b}) 。。。。泪奔

1.冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
var len = arr.length;
//循环的次数表示参与排序的元素的个数
for(var j = 0; j < len - 1; j++) {
//-1是为了保证参与比较的元素的下标不会超过 length-1
for(var i = 0; i < len - 1 - j; i++) {
if(arr[i] > arr[i + 1]) {
//如何交换数据
var temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}

2.选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {//寻找最小的数
minIndex = j; //将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}

3.插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 默认第一位是排好序的
for (var i = 1; i < array.length; i++) {
// 从第二位开始取一位
var key = array[i];
// 排好序的最后一位
var j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
///////////////////
//插入排序二分法法//
///////////////////
for (var i = 1; i < array.length; i++) {
var key = array[i], left = 0, right = i - 1;
while (left <= right) {
var middle = parseInt((left + right) / 2);
if (key < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
for (var j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = key;
}

是不是还是一脸懵逼,好吧,这个要是不理解肯定是想着头疼看着眼疼。推荐一个网址,可以动态看效果应该好一点。(其实我自己也有点懵逼。。。)未成年人勿点

另另另另另外再说一点,其实我还有一个网址慎重