1. 冒泡排序
实现
解法一（推荐去看解法二）：
从第一个元素开始向后进行比较，在一轮比较的过程中，通过持续交换元素位置，将更大的元素推向后方。sortedIndex 表示已经排序好的元素，不参与内部的第二次循环。
1
2
3
4
5
6
7
8
9
10
11
| function babelSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
const sortedIndex = arr.length - 1 - i
for (let j = 0; j < sortedIndex; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 起始输入：
[5, 2, 3, 1]
length = 4
排序过程：
i = 0; sortedIndex = 3;
j = 0; 5 > 2 === true => [*5*, *2*, 3, 1] -> [*2*, *5*, 3, 1]
j = 1; 5 > 3 === true => [2, *5*, *3*, 1] -> [2, *3*, *5*, 1]
j = 2; 5 > 1 === true => [2, 3, *5*, *1*] -> [2, 3, *1*, *5*]
i = 1; sortedIndex = 2;
j = 0; 2 > 3 === false => [*2*, *3*, 1, 5] -> [*2*, *3*, 1, 5]
j = 1; 3 > 1 === true => [2, *3*, *1*, 5] -> [2, *1*, *3*, 5]
i = 2; sortIndex = 1;
j = 0; 2 > 1 === true; [*2*, *1*, 3, 5] -> [*1*, *2*, 3, 5]
|
解法二：
拿 arr[i] 与后面的数进行对比，如果比后面的数大，就将后面的数放到前面，也就是将最小的数放到前面。
1
2
3
4
5
6
7
8
9
10
| function firstBabelSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
return arr;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 起始输入：
[5, 2, 3, 1]
排序过程：
i = 0
j = 1; 5 > 2 === true; [(5),(2),3,1] -> [(2),(5),3,1]
j = 2; 2 > 3 === false; [(2),5,(3),1] -> [(2),5,(3),1]
j = 3; 2 > 1 === true; [(2),5,3,(1)] -> [(1),5,3,(2)]
i = 1
j = 2; 5 > 3 === true; [1,(5),(3),2] -> [1,(3),(5),2]
j = 3; 3 > 2 === true; [1,(3),5,(2)] -> [1,(2),5,(3)]
i = 2
j = 3; 5 > 3 === true; [1,2,(5),(3)] -> [1,2,(3),(5)]
|
复杂度
稳定性
稳定性：在一个排序序列中，如果有两个相同的记录，若经过排序后，这些记录的相对顺序仍保持不变，即在原序列中如果 A1 === A2 且 A1 位于 A2 之前，在排序后 A1 仍位于 A2 之前，那么这个算法被称为是稳定的。
稳定，当遇到相同元素时冒泡算法不会交换两个元素的位置。
最坏情况
待排序的序列是逆序的情况下，冒泡排序需要比较和交换的次数最多。
2. 插入排序
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似与扑克牌排序：
实现
1
2
3
4
5
6
7
8
9
10
11
12
| function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
const current = arr[i];
let preIndex = i - 1;
while (preIndex >= 0 && current < arr[preIndex]) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 起始输入：
[5, 2, 1, 6, 7]
排序过程：
i = 1, preIndex = 0, current = 2, arr[preIndex] = 5
sorting arr: [5, 5, 1, 6, 7]
sorted arr: [2, 5, 1, 6, 7]
i = 2, preIndex = 1, current = 1, arr[preIndex] = 5
sorting arr: [2, 5, 5, 6, 7]
sorting arr: [2, 2, 5, 6, 7]
sorted arr: [1, 2, 5, 6, 7]
i = 3, preIndex = 2, current = 6, arr[preIndex] = 5
sorted arr: [1, 2, 5, 6, 7]
i = 4, preIndex = 3, current = 7, arr[preIndex] = 6
sorted arr: [1, 2, 5, 6, 7]
|
复杂度
稳定性
稳定，当插入排序遍历数组时，如果当前元素与已排序部分的某个元素相等，它会被插入到该元素的后面，而不是前面，因此相同元素的相对顺序保持不变。
最坏情况
插入排序的最坏情况发生在输入数组是逆序排列时。也就是说，当输入数组中的元素按照递减的顺序排列时，插入排序的性能会达到最差。
在这种情况下，每个新元素都必须与已排序部分的每个元素进行比较，并且需要执行最大数量的移动操作才能将其插入到正确的位置。这导致插入排序的时间复杂度达到 O(n^2)，其中 n 是数组的大小。
因此，插入排序在面对逆序排列的数组时效率较低，这也是其在处理大规模数据时不够高效的原因之一。
3. 选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function selectionSort(arr) {
let minIndex;
for (let i = 0; i < arr.length - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 起始输入：
[5, 2, 7, 6, 1]
排序过程：
i = 0, sortedArr = [], waitArr = [5, 2, 7, 6, 1]
minIndex = 4, arr[minIndex] = 1 => [5, 2, 7, 6, 1] -> [1, 2, 7, 6, 5]
i = 1, sortedArr = [1], waitArr = [2, 7, 6, 5]
minIndex = 1, arr[minIndex] = 2 => [1, 2, 7, 6, 5] -> [1, 2, 7, 6, 5]
i = 2, sortedArr = [1, 2], waitArr = [7, 6, 5]
minIndex = 4, arr[minIndex] = 5 => [1, 2, 7, 6, 5] -> [1, 2, 5, 6, 7]
i = 3, sortedArr = [1, 2, 5], waitArr = [6, 7]
minIndex = 3, arr[minIndex] = 6 => [1, 2, 5, 6, 7] -> [1, 2, 5, 6, 7]
|
复杂度
稳定性
不稳定，在选择排序中，由于每次选择最小（或最大）元素并将其交换到正确的位置（如 [5, 2, 5, 1, 3] 排序时第一个元素 5 可能与元素 1 交换位置），可能会破坏相同元素之间的相对顺序。因此，选择排序不是稳定的排序算法。
最坏情况
选择排序无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
4. 快速排序
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const left = [];
const right = [];
const mid = arr[arr.length - 1];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < mid) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), mid, ...quickSort(right)];
}
|
复杂度
稳定性
不稳定，在快速排序中，对元素的比较和交换是在不同位置上进行的，这可能导致相同元素的相对顺序发生改变。
最坏情况
快速排序算法的最坏情况发生在每次划分都选取的枢轴元素都是当前子数组中的最小（或最大）元素的情况下。这样的情况导致每次划分都只能将数组分成一个子数组和一个空数组，从而使得递归的深度达到最大值。
