程序员常用算法详细讲解
原创
在编程中，算法是解决问题的一系列步骤或指令的集合。对于程序员来说，掌握一些常用的算法是非常必要的。下面，我将用JavaScript（JS）语言来详细讲解几个常用的算法。
1. 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，通过重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { // 相邻元素两两对比
let temp = arr[j + 1]; // 元素交换
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
let arr = [34, 8, 64, 51, 32, 21];
console.log(bubbleSort(arr)); // 输出: [8, 21, 32, 34, 51, 64]2. 二分查找（Binary Search）
二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
function binarySearch(arr, target) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === target) {
return mid;
}
if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(arr, 6)); // 输出: 53. 快速排序（Quick Sort）
快速排序使用分而治之的策略来把一个数列分成两个子序列，再使子序列有序。
function quickSort(arr) {
if (arr.length <= 1) return arr;
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
let arr = [3,6,8,10,1,2,1];
console.log(quickSort(arr)); // 输出: [1, 1, 2, 3, 6, 8, 10]4. 归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
function mergeSort(arr) {
if (arr.length < 2) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const 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;
}
let arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // 输出: [3, 9, 10, 27, 38, 43, 82]5. 深度优先搜索（Depth-First Search, DFS）
深度优先搜索用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
function dfs(graph, start) {
let visited = new Set();
let stack = [start];
while (stack.length) {
let vertex = stack.pop();
if (!visited.has(vertex)) {
visited.add(vertex);
console.log(vertex); // 访问节点
if (graph[vertex]) {
for (let neighbor of graph[vertex]) {
stack.push(neighbor);
}
}
}
}
}
let graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
};
dfs(graph, 'A'); // 输出: A B D E F C6. 广度优先搜索（Breadth-First Search, BFS）
广度优先搜索是另一种用于遍历或搜索树或图的算法。这个算法从根节点（在图中是任意一个节点）开始，并探索最靠近根节点的邻居节点，然后是一层一层的向下遍历，这就是广度优先搜索。
function bfs(graph, start) {
let visited = new Set();
let queue = [start];
while (queue.length) {
let vertex = queue.shift();
if (!visited.has(vertex)) {
visited.add(vertex);
console.log(vertex); // 访问节点
if (graph[vertex]) {
for (let neighbor of graph[vertex]) {
queue.push(neighbor);
}
}
}
}
}
// 使用上面的 graph 变量
bfs(graph, 'A'); // 输出: A B C D E F这些算法是编程中非常基础和重要的概念，对于程序员来说，理解并熟练掌握它们，能够大大提高编程能力和解决复杂问题的能力。通过实践这些算法，你可以更好地了解计算机科学和数据结构的基础知识，以及它们如何应用于实际编程问题中。
您好，我是肥晨。
欢迎关注我获取前端学习资源，日常分享技术变革，生存法则；行业内幕，洞察先机。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。