代码均为自己手写，如有错误或更优解法，劳烦小伙伴们指教哈~
1、斐波那契数列
// 解法一
function a (n, a1 = 1, a2 = 1) {
if (n <= 1) return a1
return a(n - 1, a2, a1 + a2)
}
let res = a(5)
console.log(res)
// 解法二
let a1 = 1, a2 = 1
function b (n) {
if (n <= 1) return a
for (let i = 0; i < (n - 2); i++) {
let t = a2
a2 = a1 + a2
a1 = t
}
return a2
}
let res = b(5)
console.log(res)
2、冒泡排序
let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]
let l = arr.length
for (let i = 0; i < arr.length; i++) {
for (let j = l - 1; j >= i; j--) {
if (arr[j] > arr[j - 1]) {
let t = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = t
}
}
}
console.log(arr)
3、选择排序
let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]
let l = arr.length
for (let i = 0; i < l; i++) {
let min = arr[i]
let index = i
for (let j = i; j < l; j++) {
if (arr[j] < min) {
min = arr[j]
index = j
}
}
if (index !== i) {
arr[index] = arr[i]
arr[i] = min
}
}
console.log(arr)
4、插入排序
let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]
let l = arr.length
for (let i = 0; i < l; i++) {
let index = i
while (index >= 1 && arr[index] < arr[index - 1]) {
let t = arr[index]
arr[index] = arr[index - 1]
arr[index - 1] = t
index --
}
}
console.log(arr)
5、希尔排序
let arr = [2, 53, 32, 21, 432, 54, 76, 45, 654]
let l = arr.length
let gap = Math.floor(l / 2)
for (gap; gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < l; i++) {
let t = arr[i]
let index = -1
for (let j = i - gap; j > 0 && arr[j] > t; j -= gap) {
arr[j + gap] = arr[j]
index = j
}
if (index !== -1) {
arr[index] = t
}
}
}
console.log(arr)
6、归并排序
let arr = [89, 53, 32, 21, 432, 54, 76, 45, 654]
function mergeSort (arr) {
if (arr.length <= 1) {
return arr
}
let left = [], right = []
for (let i = 0; i < arr.length / 2; i++) {
left.push(arr.shift())
}
right = arr
return merge(mergeSort(left), mergeSort(right))
}
function merge (left, right) {
console.log(left, right)
let list = []
while (left.length > 0 && right.length > 0) {
if (left[0] > right[0]) {
list.push(right.shift())
} else {
list.push(left.shift())
}
}
while (left.length > 0) {
list.push(left.shift())
}
while (right.length > 0) {
list.push(right.shift())
}
return list
}
let res = mergeSort(arr)
console.log(res)
7、快速排序
let arr = [89, 53, 32, 21, 432, 54, 76, 45, 654]
function quickSort (arr, left, right) {
if (left >= right) {
return
}
let i = left, j = right
// 记录当前基准值在左边还是右边
let flag = 'left'
while (i < j) {
if (flag === 'left') {
while (arr[i] < arr[j]) {
j --
}
if (i < j) {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
flag = 'right'
i ++
}
} else if (flag === 'right') {
while (arr[i] < arr[j]) {
i ++
}
if (i < j) {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
flag = 'left'
j --
}
}
}
quickSort(arr, left, i - 1)
quickSort(arr, i + 1, right)
}
quickSort(arr, 0, arr.length - 1)
console.log(arr)
8、堆排序
这个算法没想出来，搬运一下大神的代码
var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
9、根据前序和中序遍历构建二叉树，并生成后序遍历数组
/* 二叉树 demo
* 0
* 1 2
* 3 4 5 6
* 7 8 9 10
*/
// 前序遍历数组 根 左 右
let pre = [0, 1, 3, 7, 8, 4, 9, 2, 5, 6, 10]
// 中序遍历数组 左 根 右
let mid = [7, 3, 8, 1, 4, 9, 0, 5, 2, 6, 10]
// 后序遍历数组 [7, 8, 3, 9, 4, 1, 5, 10, 6, 2, 0]
let back = []
// 二叉树数据结构
let tree = {
val: 0,
left: {},
right: {}
}
// 构造二叉树
function buildTree (pre, mid) {
if (mid.length === 0 || pre.length === 0) {
return null
}
let root = pre[0]
let mid_left = mid.slice(0, mid.indexOf(root))
let mid_right = mid.slice(mid.indexOf(root) + 1, mid.length)
let pre_left = pre.slice(1, mid_left.length + 1)
let pre_right = pre.slice(mid_left.length + 1, pre.length)
return {
val: root,
left: buildTree(pre_left, mid_left),
right: buildTree(pre_right, mid_right)
}
}
// 生成后序遍历
function renderBack (tree) {
if (tree.left !== null) {
renderBack(tree.left)
}
if (tree.right !== null) {
renderBack(tree.right)
}
if (tree.left === null && tree.right === null) {
back.push(tree.val)
return
}
back.push(tree.val)
}
// 执行函数
tree = buildTree(pre, mid)
renderBack(tree)
// 输出结果
console.log(tree, back)
持续更新中…
