# 基本排序算法
# 1.冒泡排序
- 基本思想：对相邻元素进行比较，顺序相反则交换，这样，每一趟会把最大或者最小的元素'浮'到顶端，最终达到完全有序。
- 外层循环遍历每一个数组元素，内层循环用于比较元素，一次循环的时间复杂度是O(n),嵌套的双层循环就是O(n2)
function bubbleSort(arr) {
//不是数组或者长度为1，直接返回
if(!Array.isArray(arr) || arr.length <= 1) return;
for (let i = 0; i < arr.length; i++) {
//设定一个标记，假如为true，表示此次循环并没有交换位置，排序已经完成了，那么直接跳出外循环，排序结束。
let flag = true
for (let j = 0; j < arr.length - 1; j++){
if(arr[j]>arr[j+1]){
flag = false;
//解构赋值，交换位置
[arr[j],arr[j+1]]=[arr[j+1],arr[j]]
}
}
if(flag===true){
break
}
}
}
let arr = [3, 4, 5, 1, 2, 9, 7, 8, 6]
bubbleSort(arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 2.选择排序（O(n2),不稳定排序）
- 基本思想：每一趟从待排序的数据元素中选择最小（或者最大）的一个元素作为首元素，直到所有元素都排完为止。
- 假如每次交换，会消耗很多的时间，所以应该把最小（或者最大）值的索引存起来，当内层的一轮循环结束之后，再执行交换操作。
function selectSort(arr){
if(!Array.isArray(array) || arr.length<=1) return;
for(let i = 0; i < arr.length - 1; i++){
let minIndex = i
for(let j = i + 1;j < arr.length; j++){
//从小到大排序，存最小的值
if(arr[i] > arr[j]){
minIndex = j
}
}
//内层循环结束后，交换一次位置即可
[arr[i],arr[j]]=[arr[j],arr[i]]
}
}
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
# 3.插入排序
- 基本思想：将第一待排序序列第一个元素看做一个有序序列，第二个元素到最后一个元素当成是未排序序列
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入到有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
function insertSort(arr) {
let length = arr.length;
if(!Array.isArray(arr) || length <=1) return;
//循环从1开始，0位置为默认的已排序的序列
for(let i = 1;i < arr.length; i++){
//保存当前需要排序的元素
let temp = arr[i];
let j = i;
//在已经排序的序列中比较，如果比需要排序的元素大，就依次往后移动位置
while(j - 1>=0 && arr[j-1] > temp){
arr[j] = array[j-1];
j--
}
//将找到的位置插入元素
arr[j] = temp
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 4.希尔排序
- 也叫做递减增量排序算法，是插入排序的改进版本，但是是非稳定排序
- 把数组按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。
- 基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。