经典排序算法（JS）
Rio 2023-02-23
数据结构与算法
说明
js实现经典排序算法
本专栏已迁移 详见https://github.com/sami-jiaze/myCoding
# 经典排序算法
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括
# 冒泡排序
相邻的数据进行两两比较，小数放在前面，大数放在后面，如果前面的数据比后面的数据大，就交换这两个数的位置。也可以实现大数放在前面，小数放在后面，如果前面的数据比后面的小，就交换两个的位置。要实现上述规则需要用到两层for循环。
let arr = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
function bubble(arr) {
for (let j = 0; j < arr.length-1; j++) {
for (let i = 0; i < arr.length - 1 - j; i++) {
let temp = arr[i];
if (arr[i] > arr[i + 1]) {
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
return arr;
}
console.log(bubble(arr));
// -j 是每一层循环后就会至少确定一个数的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 选择排序
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序是不稳定的;因为会不停的交换顺序
let arr = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
function select(arr) {
for (let i = 0; i < arr.length-1; i++) {
// 最小数小标
let min = i;
for (let j = i; j < arr.length-1; j++) {
if (arr[j+1] < arr[min]) {
min = j+1;
}
}
let t = arr[i];
arr[i] = arr[min];
arr[min] = t;
}
return arr;
}
console.log(select(arr));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 插入排序
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
let arr = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
function insert(arr) {
let len = arr.length;
for(let i = 1; i<arr.length; i++){
for(let j = 0; j < i; j++){
if (arr[i]<arr[j]) {
swap(arr,i,j)
}
}
}
return arr
}
function swap(arr,i,j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
console.log(insert(arr));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序
1
