选择排序
从待排序的数据元素中选出最小（或最大）的一个元素，存放在与序列的第一个元素交换位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完
时间复杂度
最好：O(n2)
最坏：O(n2)
平均：O(n2)
空间复杂度 —— O(1)
稳定性：不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function selectSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
let temp = arr[i], minIndex = i;
for (j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
|
其排序过程为
1
2
3
4
5
6
7
8
| selectSort([4, 9, 1, 7, 3, 5]);
0: 1 9 4 7 3 5
1: 1 3 4 7 9 5
2: 1 3 4 7 9 5
3: 1 3 4 5 9 7
4: 1 3 4 5 7 9
5: 1 3 4 5 7 9
|
特点：
运行时间与输入无关
数据移动次数是最少的，共 n 此交换
插入排序
将每一个元素插入到已经排好序的序列中
时间复杂度
最好：O(n)
最坏：O(n2)
平均：O(n2)
空间复杂度 —— O(1)
稳定性：稳定
1
2
3
4
5
6
7
8
9
| function insertSort(arr) {
let len = arr.length;
for (let i = 1; i < len; i++) {
for (j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
}
}
return arr;
}
|
其排序过程为
1
2
3
4
5
6
7
| insertSort([4, 9, 1, 7, 3, 5])
1: 4 9 1 7 3 5
2: 1 4 9 7 3 5
3: 1 4 7 9 3 5
4: 1 3 4 7 9 5
5: 1 3 4 5 7 9
|
另一种写法，在内循环中将较大的元素向右移动而不交换
1
2
3
4
5
6
7
8
9
10
11
| function insertSort(arr) {
let len = arr.length;
for (let i = 1; i < len; i++) {
let temp = arr[i];
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
return arr;
}
|
特点：插入排序所需的时间取决于输入元素的初始顺序
冒泡排序
遍历若干次要排序的序列，每次遍历时，从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，每一次遍历之后，最大的元素就在序列的末尾。重复此操作，直到整个序列都有序为止
时间复杂度
最好：O(n)
最坏：O(n2)
平均：O(n2)
空间复杂度 —— O(1)
稳定性：稳定
1
2
3
4
5
6
7
8
9
10
11
12
| function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
console.log(`${i}: ${arr}`)
}
return arr;
}
|
其排序过程为
1
2
3
4
5
6
7
8
| bubbleSort([4, 9, 1, 7, 3, 5])
0: 4 1 7 3 5 9
1: 1 4 3 5 7 9
2: 1 3 4 5 7 9
3: 1 3 4 5 7 9
4: 1 3 4 5 7 9
5: 1 3 4 5 7 9
|
一种优化的方法：
添加一个标记，如果一趟遍历中发生了交换，则标记为true，否则为false。如果某一趟没有发生交换，说明排序已经完成，可以直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
let needSwap = false;
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
needSwap = true;
}
}
if (!needSwap) return arr;
}
return arr;
}
|
1
2
3
4
5
6
| bubbleSort([4, 9, 1, 7, 3, 5])
0: 4 1 7 3 5 9 (true)
1: 1 4 3 5 7 9 (true)
2: 1 3 4 5 7 9 (true)
3: 1 3 4 5 7 9 (false)
|
希尔排序
希尔排序是把元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个序列恰被分成一组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function shellSort(arr) {
let len = arr.length, gap = 1;
while (gap < len / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (let i = gap; i < len; i++) {
for (let j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
[arr[j], arr[j - gap]] = [arr[j - gap], arr[j]];
}
console.log(`${gap}: ${arr}`)
}
gap = Math.floor(gap / 3);
}
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
| shellSort([4, 9, 1, 7, 3, 5, 52, 10, 98, 8, 24, 30, 2, 79, 43])
gap = 13 4 9 1 7 3 5 52 10 98 8 24 30 2 79 43
4 9 1 7 3 5 52 10 98 8 24 30 2 79 43
gap = 4 3 9 1 7 4 5 52 10 98 8 24 30 2 79 43
3 5 1 7 4 9 52 10 98 8 24 30 2 79 43
3 5 1 7 4 9 52 10 98 8 24 30 2 79 43
3 5 1 7 4 9 52 10 98 8 24 30 2 79 43
3 5 1 7 4 9 52 10 98 8 24 30 2 79 43
3 5 1 7 4 8 52 10 98 9 24 30 2 79 43
3 5 1 7 4 8 24 10 98 9 52 30 2 79 43
3 5 1 7 4 8 24 10 98 9 52 30 2 79 43
2 5 1 7 3 8 24 10 4 9 52 30 98 79 43
2 5 1 7 3 8 24 10 4 9 52 30 98 79 43
2 5 1 7 3 8 24 10 4 9 43 30 98 79 52
gap = 1 2 5 1 7 3 8 24 10 4 9 43 30 98 79 52
1 2 5 7 3 8 24 10 4 9 43 30 98 79 52
1 2 5 7 3 8 24 10 4 9 43 30 98 79 52
1 2 3 5 7 8 24 10 4 9 43 30 98 79 52
1 2 3 5 7 8 24 10 4 9 43 30 98 79 52
1 2 3 5 7 8 24 10 4 9 43 30 98 79 52
1 2 3 5 7 8 10 24 4 9 43 30 98 79 52
1 2 3 4 5 7 8 10 24 9 43 30 98 79 52
1 2 3 4 5 7 8 9 10 24 43 30 98 79 52
1 2 3 4 5 7 8 9 10 24 43 30 98 79 52
1 2 3 4 5 7 8 9 10 24 30 43 98 79 52
1 2 3 4 5 7 8 9 10 24 30 43 98 79 52
1 2 3 4 5 7 8 9 10 24 30 43 79 98 52
1 2 3 4 5 7 8 9 10 24 30 43 52 79 98
|
归并排序