冒泡排序
冒泡排序即数组从头到尾，依次比较相邻两数的大小，不符合顺序则交换位置，一直循环直到排序完成。如果是升序排序，那么每一轮的一系列比较和交换之后，最大那个数一定会被排到最后（不信可以动手验证一下），可以理解为冒泡到最后，这样每一轮的最大那个数都冒到最后，所以每一轮需要比较的总数都在减少，直到剩一个数为止，序列就有序了，降序也是同样的道理；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
function bubbleSort(_arr) {
var arr = _arr.concat();
var len = arr.length;
for (var i = len - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
|
选择排序
选择排序即从数组第一个数到倒数第二个数，分别与后面的数中的选出的最值（升序就是最小值）进行比较，满足条件（升序就是大于最小值）就交换位置，然后完成排序。这里可以理解为先选择出最小值，然后与前面的数进行比较和交换，就不用像冒泡那样挨个比较和交换了；另外，这里为了交换方便，记录的最值其实是该值在数组中的索引，而不是实际值；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function selectSort(_arr) {
var arr = _arr.concat();
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
var minIdx = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx !== i) {
var tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
return arr;
}
|
插入排序
插入排序即从第二个到最后一个数，分别与排在前面的有序序列（第一轮该序列只有一个数，肯定是有序的，之后每一轮结束这个有序序列都会增加）中的每个数进行比较，然后插入合适的位置使其有序，直到最后一个数插入时完成排序；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| function insertSort(_arr) {
var arr = _arr.concat();
var len = arr.length;
for (let i = 1; i < len; i++) {
let tmp = arr[i];
for (let j = i; j > 0; j--) {
if (tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
} else {
arr[j] = tmp;
break;
}
}
}
return arr;
}
|
快速排序
快速排序在数组中任选一个数（下面选第一个数）作中间值，然后将余下的数分别与其比较，比中间值小则放到左边，否则放右边，然后再进行递归，将放在左边和右边的数组分别作为新数组进行同样的排序操作，直到数组不能再分，最后将所有排序结果合并；这里快速可以理解为整个操作过程相比于其他方法简单快捷，找好任一个中间值后便将剩下的数挨个放入其左或右，而不用管左右数组是否有序，直到递归完成就整体有序了，至于排序是否快速就要看情况了；
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
function quickSort(arr) {
let len = arr.length;
if (len < 2) {
return arr;
} else {
let mid = arr[0],
left = [],
right = [];
for (let i = 1; i < len; i++) {
if (arr[i] < mid) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).
concat(mid).
concat(quickSort(right));
}
}
function quickSort(arr) {
let len = arr.length;
if (len < 2) {
return arr;
} else {
let midIdx = 0;
for (let i = 1; i < len; i++) {
if (arr[i] < arr[midIdx]) {
arr.unshift(arr.splice(i, 1)[0]);
midIdx++;
}
}
return quickSort(arr.slice(0, midIdx)).
concat(arr[midIdx]).
concat(quickSort(arr.slice(midIdx + 1)));
}
}
|
归并排序
归并排序递归地将数组分割为两个部分（左数组与右数组），直到不能再分，然后再定义一个合并函数，负责递归地将两部分合并为一个有序数组作为返回值；合并函数其实会是合并两个有序的数组，合并方法便是分别将两数组第一个数取出（删除）放入返回数组中，至于两个数先放哪一个，可以通过比较大小来确定；所以这里的归并可以理解为递归地合并为一个有序序列；
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
31
32
33
34
35
36
37
38
| function mergeSort(arr) {
if (arr.length < 2) {
return arr;
} else {
let mid = Math.ceil(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
}
function merge(left, right) {
let result = [];
let len = left.length + right.length;
for (let i = 0; i < len; i++) {
if (!left[0]) {
result.push(right.shift());
} else if (!right[0]) {
result.push(left.shift());
} else {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
}
return result;
}
|
