联系作者
# 3.1 冒泡排序
# 个人理解：
比较 2 个元素，如果顺序错误就把他们交换过来，这个名字的由来就是较小的元素由于交换慢慢“浮”到数列的顶端，它的特点是每一次排序完；右边的总是最大的数值。
# 大佬理解：
冒泡 排序 是比较形象的 一种排序算法， 就像小气泡在水底不断往上冒泡，直到变大。那他的算法过程就是这样的，依次比较俩个相邻的节点，然后将较大的放置在后，较小的放置在前，直到排序完成
# 算法步骤：
比较相邻的元素，如果第一个比第二个大，就交换它们的位置。
对每对相邻元素作同样的工作，这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。直到没有任何一对数字需要比较。
# 菜鸟教程给出生动的展示图：点击我
# 案例： 给数组[2,4,3,5,1,5]进行排序
let arr = [2, 4, 3, 5, 1, 5]
// 正向遍历
function bubbleSort1(src) {
let arr = [...src] // 做浅拷贝，避免影响原数组
let len = arr.length
let current
for (let i = 0; i < len - 1; i++) {
//为什么arr.length-1-i？因为每次遍历完后最大值肯定在最右边，数组的后面的那段其实已经是排序好，无需在排序
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
current = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = current
}
}
}
return arr
}
/*
反向遍历实现
- 冒泡排序第一次遍历后会将最大值放到最右边，这个值是全局的最大值
- 标准的冒泡排序的每次遍历都会比较全部元素，虽然右侧的值以及是最大值了
- 改进之后，每次遍历后的最大值，次大值，等等都会固定在右侧，避免的重复比较
*/
function bubbleSort2(src) {
let arr = [...src] //做浅拷贝，避免影响原数组
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
console.log(bubbleSort1(arr)) // [ 1, 2, 3, 4, 5, 5 ]
console.log(bubbleSort2(arr)) // [ 1, 2, 3, 4, 5, 5 ]
//2个方法都会循环10次
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
# 3.2 插入排序
# 个人理解：
先把第2元素存起来，然后跟第1个的元素进行比较，如果小于第1个元素，那么第1个元素往后挪一个位置；第二个元素放在第一个元素的位置上，如果大于前面的数值，就不用动。
在把第 3 个元素存起来，跟第2个的元素进行比较，如果符合规则（小于前面的元素），第2个元素往后挪一位。 存起来的元素在跟第1个元素比较，如果符合规则，第1个元素就往后挪一位，这时候前面没有元素可比，就把第3个元素放在第1个元素的位置上。需要注意的是如果不符合规则了，就是存的元素比比较元素大的时候，就不用往前比较了，可以插入当前的位置；在比较的过程中，被比较的元素在比较中符合规则就需要往后挪一位，这是给存起来的元素腾位置。
以此慢慢递进完成排序。
（正序：插入就是每次新取一个数，然后倒序地往前找，找到比它小的就插入后面）
# 大佬理解：
其实插入排序就和打扑克的时候抓牌一样，新摸一张，然后再已排好的队列里面去插入它。
# 算法步骤：
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
# 菜鸟教程给出生动的展示图：点击我
# 案例： 给数组[2,4,3,5,1,5]进行排序
function insertionSort(src) {
let arr = [...src]
for (let i = 1; i < arr.length; i++) {
let current = arr[i]
let preIndex = i - 1
while (preIndex >= 0 && current < arr[preIndex]) {
// 如果current小于前面的值，那么current肯定需要往前插入，具体插入前面的哪个位置，需要跟前面的数进行对比
// 在对比的过程中，如果current小于前面的值；那么对比的数肯定往后挪一位
arr[preIndex + 1] = arr[preIndex]
preIndex--
}
arr[preIndex + 1] = current
}
return arr
}
console.log(insertionSort(arr)) // [ 1, 2, 3, 4, 5, 5 ]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 3.3 选择排序
个人理解：寻找最小值，第一次枚举会找到当前数组的最小的一个值，放在首位；就是首位跟最小值交换位置。
第二次枚举会找到数组第二小值，然后第二位置的值跟第二小值交换位置，以此内推。
由此可见每次枚举完，左边是排序好的，右边是待排序的。
# 菜鸟教程给出生动的展示图：点击我
function selectionSort(arr) {
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;
}
return arr;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 3.4 快速排序
个人理解：快速排序主要采用分治法，定义基准值；左边所有都比基准值小，右边所有的都比基准值大；然后左右两边在定义基准值再次重复上次动作。
# 菜鸟教程给出生动的展示图：点击我
function quickSort(arr, left = 0, right = arr.length - 1) {
// 定义递归边界，若数组只有一个元素，则没有排序必要
if(arr.length > 1) {
// lineIndex表示下一次划分左右子数组的索引位
const lineIndex = partition(arr, left, right)
// 如果左边子数组的长度不小于1，则递归快排这个子数组
if(left < lineIndex-1) {
// 左子数组以 lineIndex-1 为右边界
quickSort(arr, left, lineIndex-1)
}
// 如果右边子数组的长度不小于1，则递归快排这个子数组
if(lineIndex<right) {
// 右子数组以 lineIndex 为左边界
quickSort(arr, lineIndex, right)
}
}
return arr
}
// 以基准值为轴心，划分左右子数组的过程
function partition(arr, left, right) {
// 基准值默认取中间位置的元素
let pivotValue = arr[Math.floor(left + (right-left)/2)]
// 初始化左右指针
let i = left
let j = right
// 当左右指针不越界时，循环执行以下逻辑
while(i<=j) {
// 左指针所指元素若小于基准值，则右移左指针
while(arr[i] < pivotValue) {
i++
}
// 右指针所指元素大于基准值，则左移右指针
while(arr[j] > pivotValue) {
j--
}
// 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
if(i<=j) {
swap(arr, i, j)
i++
j--
}
}
// 返回左指针索引作为下一次划分左右子数组的依据
return i
}
// 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
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
54
总结：现在可以用 sort 排序，可以看 v8 的源码去了解它点击我