佳宸学习和分享笔记的地方

0%

基础排序算法JS实现

基础排序算法JS实现

冒泡排序

前一个元素大于后一个元素就交换位置,最大的值会冒泡到最后,重复循环,每趟过后,比较的次数都要减1

先定义一个交换位置函数

1
2
3
4
5
6
7
8
9
10
11
/**
*
* @param {Array} arr 传入数组
* @param {Number} a 要交换的数组下标index
* @param {Number} b index
*/
function swap(arr, a, b) {
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
}

解码过程

1
2
3
4
5
6
7
8
9
10
11
function bubble(arr) {
let length = arr.length
for (let i = 0; i < length-1; i++) {
for (let j = 0; j < length-1-i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr, j, j+1)
}
}
}
return arr
}

插入排序

与有序的数组进行比较,比它大则直接放入,比它小则移动数组元素的位置,找到个合适的位置插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function insert(arr) {
let length = arr.length
// 从第二个开始,把第一个设为初有序
for (let i = 1; i < length; i++) {
// 取出当前遍历数组的数
let tNum = arr.splice(i, 1)[0]
// 从有序数组末尾开始比较
for (let j = i - 1; j >= 0; j--) {
// 比最小的小,直接插入队头
if(tNum < arr[0]) {
arr.unshift(tNum)
break
}
// 找到个合适的位置插入
if (tNum > arr[j]) {
arr.splice(j+1, 0, tNum)
break
}
}
}
return arr
}

选择排序

找到数组中最大的元素,与数组未排序最后一位元素交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function select(arr) {
// 只有一个数时就不要排序了 -1趟
for (let i = 0; i < arr.length - 1; i++) {
let max = 0
for (let j = 0; j < arr.length - i; j++) {
if (arr[max] < arr[j]) {
max = j
}
}
// 把最大的放到最后面
swap(arr, max, arr.length-1-i)
}
return arr
}

快速排序

选择一个中间节点,小的放左边,大的放右边,不断递归

1
2
3
4
5
6
7
8
9
10
11
function quick(arr) {
if (arr.length <= 1) return arr
// 取数组中间下标值
let middle = arr.splice(arr.length - 1 >> 1, 1)[0]
let left = [],
right = []
for(let i = 0; i < arr.length; i++) {
arr[i] < middle ? left.push(arr[i]) : right.push(arr[i])
}
return quick(left).concat(middle,quick(right))
}

归并排序

分而治之加递归,先把数组递归二分,然后比较合并

merge-sort-example.png

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
function mergeSort(arr) {
const length = arr.length
// 如果数组长度小于二直接返回
if (length < 2) return arr
// 取到中间值 同等于 Math.floor(arr.length/2)
let middle = arr.length >> 1,
// 切出左右两边 (start,end断掉下标前一位)
left = arr.slice(0, middle),
right = arr.slice(middle)
// 递归拆分,然后比较,合并比较,这里理解难点,可以动手画一画程序流程
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = []
while (left.length && right.length) {
// 两边数组头项 比较大小
if(left[0] < right[0]) {
// 如果左边小,就把左边数组头项取出,推入新结果
result.push(left.shift())
} else {
result.push(right.shift())
}
}
// 如果左边有右边没有情况下直接推入
while (left.length) result.push(left.shift())
while (right.length) result.push(right.shift())
return result
}

堆排序

堆排序视频讲解C语言实现

用数组可以表示一个完全二叉树,左子节点2i+1,右子节点2i+2

堆其实是一种特殊的树。只要满足这两点,它就是一个堆。

  • 堆是一个完全二叉树。 完全二叉树:除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列。
  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。 也可以说:堆中每个节点的值都大于等于(或者小于等于)其左右子节点的值。这两种表述是等价的。
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
30
31
32
33
34
35
36
37
38
function heapSort (arr) {
// 从最后一个含有子节点的父节点开始
for (let i = arr.length - 1 >> 1; i >= 0; i--) {
heapify(arr, i, arr.length)
}
// 堆完成后,每次把对顶最大的数放到末尾
for (let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i)
// 交换之后,再规范堆的位置
heapify(arr, 0, i)
}
return arr
}

/**
* arr 数组(堆)
* i 数组(堆)下标
* length 数组(堆)长度
*/
// 完全二叉树,堆函数顺序化
function heapify (arr, i, length) {
let parent = arr[i]
for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
parent = arr[i]
// 找到两子节点中较大的一个,再与父节点比较
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++
}
if (parent < arr[j]) {
// 如果父节点大于子节点:交换;否则跳出
swap(arr, i, j)
// 交换后,parent 的值下标变为交换的子节点
i = j
} else {
break
}
}
}

在家这么久效率有些低,这篇排序还做了这么久,之前数据结构课程也都复习过,疫情快快过去把,想去图书馆里了。