算法的研究可参考: 算法通关之路
深度优先遍历(DFS)
栈实现 (非递归),右子树优先,先进后出
const root = {
name: 'A',
children: [
{
name: 'X',
children: [
{
name: 'X1',
children: []
},
{
name: 'X2',
children: []
},
{
name: 'X3',
children: []
}
]
},
{
name: 'Y',
children: [
{
name: 'Y1',
children: []
},
{
name: 'Y2',
children: [
{
name: 'M1',
children: []
},
{
name: 'M2',
children: []
}
]
},
{
name: 'Y3',
children: []
}
]
},
{
name: 'Z',
children: [
{
name: 'Z1',
children: []
},
{
name: 'Z2',
children: []
},
{
name: 'Z3',
children: []
}
]
}
]
}
const stack = [root]
while(stack.length) {
current = stack.pop()
console.log(`访问: ${current.name}`)
if (current.children) {
current.children.forEach(e => stack.push(e))
}
}
访问: A
访问: Z
访问: Z3
访问: Z2
访问: Z1
访问: Y
访问: Y3
访问: Y2
访问: M2
访问: M1
访问: Y1
访问: X
访问: X3
访问: X2
访问: X1
递归实现,左子树优先
function dfs(current) {
if (current) {
console.log(`访问: ${current.name}`)
if (current.children) {
current.children.forEach(e => dfs(e))
}
}
}
dfs(root)
访问: A
访问: X
访问: X1
访问: X2
访问: X3
访问: Y
访问: Y1
访问: Y2
访问: M1
访问: M2
访问: Y3
访问: Z
访问: Z1
访问: Z2
访问: Z3
广度优先遍历(BFS)
队列实现 (非递归),先进先出
const queue = [root]
while(queue.length) {
current = queue.pop()
console.log(`访问: ${current.name}`)
if (current.children) {
current.children.forEach(e => queue.unshift(e))
}
}
访问: A
访问: X
访问: Y
访问: Z
访问: X1
访问: X2
访问: X3
访问: Y1
访问: Y2
访问: Y3
访问: Z1
访问: Z2
访问: Z3
访问: M1
访问: M2
快速排序
const data = [2, 1, 5, 6, 3, 9]
// quick sort
function quick_sort(data, begin, end) {
if (begin < end) {
let key = data[begin];
let left = begin;
let right = end;
while (left < right) {
while (left < right && data[right] > key) {
right--;
}
if (left < right) {
data[left] = data[right]
left++;
}
while(left < right && data[left] < key) {
left++;
}
if (left < right) {
data[right] = data[left];
right--;
}
}
data[left] = key;
quick_sort(data, begin, left - 1);
quick_sort(data, left + 1, end);
}
}
quick_sort(data, 0, data.length - 1);
console.log(data)