# 基本排序算法
基本排序算法分为:冒泡排序,选择排序,插入排序。
- 三种排序算法都是嵌套循环,故最坏的时间复杂度为 O(n²)。
- 选择排序是不稳定排序,数组中如果有相同的元素,交换后的位置可能不一致。
算法稳定性
算法的稳定性定义:排序前后两个相等的数相对位置不变,则算法稳定。
例如:[7 2 5 9 3 4 7 1] 使用选择排序算法进行排序时候,第一个 7 和 1 调换,第一个 7 就跑到了第二个 7 的后面了,原来的次序改变了,这样就不稳定了。
# 冒泡排序
它是最慢的排序算法之一,数据值会像气泡一样从数组的一端漂浮到另一端。
function bubbleSort(array) {
for (let outer = 0; outer < array.length; outer++) {
for (let inner = 0; inner < array.length - outer; inner++) {
if (array[inner] > array[inner + 1]) {
swap(array, inner, inner + 1);
}
console.log("冒泡排序循环次数");
}
}
return array;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 选择排序
从数组的开头开始,将第一个元素和其他元素比,较最小的元素会被放到数组的第一个位置,再从第二个位置继续。
// 选择排序
function selectSort(array) {
for (let outer = 0; outer < array.length - 1; outer++) {
let min = array[outer];
for (let inner = outer + 1; inner < array.length; inner++) {
if (array[inner] < min) {
swap(array, inner, outer);
}
console.log("选择排序循环次数");
}
}
return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 插入排序
类似于人们按数组或字母顺序对数据进行排序,后面的要为前面腾位置(叠卷子)。
// 插入排序
function insertSort(array) {
for (let outer = 1; outer < array.length; outer++) {
for (
let inner = outer;
inner > 0 && array[inner] < array[inner - 1];
inner--
) {
swap(array, inner, inner - 1);
console.log("插入排序循环次数");
}
}
return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
插入排序是稳定的排序,处理小规模数据或者基本有序数据时,十分高效。
# 最终代码
// 冒泡排序
function bubbleSort(array) {
for (let outer = 0; outer < array.length; outer++) {
for (let inner = 0; inner < array.length - outer; inner++) {
if (array[inner] > array[inner + 1]) {
swap(array, inner, inner + 1);
}
console.log("冒泡排序循环次数");
}
}
return array;
}
// 选择排序
function selectSort(array) {
for (let outer = 0; outer < array.length - 1; outer++) {
let min = array[outer];
for (let inner = outer + 1; inner < array.length; inner++) {
if (array[inner] < min) {
swap(array, inner, outer);
}
console.log("选择排序循环次数");
}
}
return array;
}
// 插入排序
function insertSort(array) {
for (let outer = 1; outer < array.length; outer++) {
for (
let inner = outer;
inner > 0 && array[inner] < array[inner - 1];
inner--
) {
swap(array, inner, inner - 1);
console.log("插入排序循环次数");
}
}
return array;
}
function swap(array, index1, index2) {
var temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
const array = [2, 3, 1, 9, 6, 4, 7, 8, 5];
console.warn("冒泡排序:", bubbleSort(array));
console.warn("选择排序:", selectSort(array));
console.warn("插入排序:", insertSort(array));
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
51
52
53
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
51
52
53