当前位置：首页 > news >正文

计算机算法基础：理论与实战

news 来源：原创 2024/9/20 12:21:19

计算机算法基础：理论与实战

大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！

一、引言

计算机算法是解决复杂问题的核心技术，广泛应用于各种编程任务中。本文将介绍算法的基本理论，并通过具体的Java代码实例演示算法的实际应用，帮助大家从理论到实践掌握计算机算法。

二、算法的基本概念

算法是一组明确指令的集合，用于解决特定问题。一个好的算法通常具有以下特性：

正确性：算法能够正确地解决问题。
效率：算法的时间复杂度和空间复杂度尽可能低。
可读性：算法逻辑清晰，易于理解和维护。

三、排序算法

排序是算法中的基础问题之一。常见的排序算法包括冒泡排序、选择排序和快速排序。

冒泡排序

冒泡排序是一种简单的排序算法，通过重复遍历要排序的列表，比较相邻的元素并交换顺序。

package cn.juwatech.sort;public class BubbleSort {public static void bubbleSort(int[] array) {int n = array.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - 1 - i; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;swapped = true;}}if (!swapped) break;}}public static void main(String[] args) {int[] array = {64, 34, 25, 12, 22, 11, 90};bubbleSort(array);for (int i : array) {System.out.print(i + " ");}}
}

选择排序

选择排序是一种简单直观的排序算法，每次从待排序的元素中选择最小的一个进行排序。

package cn.juwatech.sort;public class SelectionSort {public static void selectionSort(int[] array) {int n = array.length;for (int i = 0; i < n - 1; i++) {int minIdx = i;for (int j = i + 1; j < n; j++) {if (array[j] < array[minIdx]) {minIdx = j;}}int temp = array[minIdx];array[minIdx] = array[i];array[i] = temp;}}public static void main(String[] args) {int[] array = {64, 25, 12, 22, 11};selectionSort(array);for (int i : array) {System.out.print(i + " ");}}
}

快速排序

快速排序是一种高效的排序算法，采用分治法，将数组分成两个子数组，再递归地对其进行排序。

package cn.juwatech.sort;public class QuickSort {public static void quickSort(int[] array, int low, int high) {if (low < high) {int pi = partition(array, low, high);quickSort(array, low, pi - 1);quickSort(array, pi + 1, high);}}private static int partition(int[] array, int low, int high) {int pivot = array[high];int i = (low - 1);for (int j = low; j < high; j++) {if (array[j] <= pivot) {i++;int temp = array[i];array[i] = array[j];array[j] = temp;}}int temp = array[i + 1];array[i + 1] = array[high];array[high] = temp;return i + 1;}public static void main(String[] args) {int[] array = {10, 7, 8, 9, 1, 5};int n = array.length;quickSort(array, 0, n - 1);for (int i : array) {System.out.print(i + " ");}}
}

四、搜索算法

搜索算法用于查找数据结构中的特定元素。常见的搜索算法包括线性搜索和二分搜索。

线性搜索

线性搜索是一种简单的搜索算法，逐个检查每个元素，直到找到目标元素。

package cn.juwatech.search;public class LinearSearch {public static int linearSearch(int[] array, int target) {for (int i = 0; i < array.length; i++) {if (array[i] == target) {return i;}}return -1;}public static void main(String[] args) {int[] array = {2, 3, 4, 10, 40};int target = 10;int result = linearSearch(array, target);if (result != -1) {System.out.println("Element found at index " + result);} else {System.out.println("Element not found in array");}}
}

二分搜索

二分搜索是一种高效的搜索算法，要求数据结构是有序的，通过不断折半查找目标元素。

package cn.juwatech.search;public class BinarySearch {public static int binarySearch(int[] array, int target) {int left = 0, right = array.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (array[mid] == target) {return mid;}if (array[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}public static void main(String[] args) {int[] array = {2, 3, 4, 10, 40};int target = 10;int result = binarySearch(array, target);if (result != -1) {System.out.println("Element found at index " + result);} else {System.out.println("Element not found in array");}}
}

五、图算法

图算法用于处理图结构的数据，常见的图算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索图的算法，沿着路径深入到尽可能深的节点。

package cn.juwatech.graph;import java.util.Iterator;
import java.util.LinkedList;public class DepthFirstSearch {private int V;private LinkedList<Integer> adj[];DepthFirstSearch(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i) {adj[i] = new LinkedList();}}void addEdge(int v, int w) {adj[v].add(w);}void DFSUtil(int v, boolean visited[]) {visited[v] = true;System.out.print(v + " ");Iterator<Integer> i = adj[v].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n]) {DFSUtil(n, visited);}}}void DFS(int v) {boolean visited[] = new boolean[V];DFSUtil(v, visited);}public static void main(String[] args) {DepthFirstSearch g = new DepthFirstSearch(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("Depth First Traversal starting from vertex 2:");g.DFS(2);}
}

广度优先搜索（BFS）

广度优先搜索是一种用于遍历或搜索图的算法，从起始节点开始，逐层向外扩展。

package cn.juwatech.graph;import java.util.Iterator;
import java.util.LinkedList;public class BreadthFirstSearch {private int V;private LinkedList<Integer> adj[];BreadthFirstSearch(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i) {adj[i] = new LinkedList();}}void addEdge(int v, int w) {adj[v].add(w);}void BFS(int s) {boolean visited[] = new boolean[V];LinkedList<Integer> queue = new LinkedList<Integer>();visited[s] = true;queue.add(s);while (queue.size() != 0) {s = queue.poll();System.out.print(s + " ");Iterator<Integer> i = adj[s].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n]) {visited[n] = true;queue.add(n);}}}}public static void main(String[] args) {BreadthFirstSearch g = new BreadthFirstSearch(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("Breadth First Traversal starting from vertex 2:");g.BFS(2);}
}