目录
一、排序算法
1、冒泡排序(Bubble Sort):
2、快速排序(Quick Sort):
二、查找算法
1、二分查找(Binary Search):
三、 图算法
1、深度优先搜索(Depth-First Search,DFS):
2、广度优先搜索(Breadth-First Search,BFS):
一、排序算法
1、冒泡排序(Bubble Sort):
冒泡排序(Bubble Sort)是一种简单的排序算法,它多次遍历要排序的元素列表,每次比较相邻的两个元素,并交换它们,如果它们的顺序不正确。这个过程重复进行,直到整个列表排好序为止。
public class BubbleSort {public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};System.out.println("排序前的数组:");printArray(arr);bubbleSort(arr);System.out.println("\n排序后的数组:");printArray(arr);}public static void bubbleSort(int[] arr) {int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j+1] 的位置int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 如果在一轮中没有发生交换,说明列表已经排序完成,可以提前退出if (!swapped) {break;}}}public static void printArray(int[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {System.out.print(arr[i] + " ");}System.out.println();}
}
在这个示例中,bubbleSort
函数对给定的整数数组进行冒泡排序,printArray
函数用于打印数组的内容。冒泡排序的核心是嵌套的循环,外循环控制每次遍历的范围,内循环用于比较相邻元素并进行交换。
冒泡排序的时间复杂度是 O(n^2),在大规模数据集上性能较差,但对于小规模数据集或基本有序的数据集,它可能是一个简单且容易实现的排序方法。
2、快速排序(Quick Sort):
快速排序(Quick Sort)是一种高效的排序算法,它采用分治策略来将一个数组分为两个子数组,然后递归地对子数组进行排序。
public class QuickSort {public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};System.out.println("排序前的数组:");printArray(arr);quickSort(arr, 0, arr.length - 1);System.out.println("\n排序后的数组:");printArray(arr);}public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}}public static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交换 arr[i] 和 arr[j] 的位置int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 交换 arr[i+1] 和 arr[high] 的位置,将pivot放在正确的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}public static void printArray(int[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {System.out.print(arr[i] + " ");}System.out.println();}
}
这个示例中,quickSort
函数对给定的整数数组进行快速排序,partition
函数用于选择一个元素作为主元(通常选择最后一个元素),并将小于主元的元素移到主元的左侧,大于主元的元素移到主元的右侧。
快速排序的时间复杂度通常为 O(n log n),在平均情况下表现良好,但在最坏情况下可能为 O(n^2),这取决于主元的选择。然而,通过选择随机的主元或使用三数中值法等优化策略,可以降低最坏情况的概率。
二、查找算法
1、二分查找(Binary Search):
二分查找(Binary Search)是一种高效的搜索算法,用于在有序数组中查找特定的元素。以下是Java中的二分查找算法示例:
public class BinarySearch {public static void main(String[] args) {int[] arr = {11, 12, 22, 25, 34, 64, 90};int target = 25;int result = binarySearch(arr, target);if (result == -1) {System.out.println("未找到目标元素 " + target);} else {System.out.println("目标元素 " + target + " 位于索引 " + result);}}public static int binarySearch(int[] arr, int target) {int left = 0, right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标元素,返回索引} else if (arr[mid] < target) {left = mid + 1; // 在右半部分继续查找} else {right = mid - 1; // 在左半部分继续查找}}return -1; // 未找到目标元素}
}
在这个示例中,binarySearch
函数接受一个有序数组和一个目标元素作为输入,并返回目标元素的索引,如果未找到目标元素,则返回 -1。算法的核心思想是在每次迭代中,将目标元素与数组的中间元素进行比较,然后根据比较结果缩小搜索范围。
二分查找的时间复杂度是 O(log n),其中 n 是数组的长度。这使它成为在大型有序数据集上查找元素的一种非常高效的方法。但要注意,二分查找要求数组必须是有序的。
三、 图算法
1、深度优先搜索(Depth-First Search,DFS):
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索图形和树数据结构的算法。DFS的基本思想是从起始节点开始,沿着一条路径尽可能深入,直到无法前进为止,然后回溯并继续搜索其他路径
import java.util.*;class Graph {private int V; // 图的顶点数private LinkedList<Integer> adj[]; // 邻接列表Graph(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);}// 从顶点s开始进行DFS遍历void DFS(int s) {boolean visited[] = new boolean[V];DFSUtil(s, visited);}// 辅助函数用于递归遍历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);}}
}public class DFSExample {public static void main(String[] args) {Graph g = new Graph(7);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(2, 5);g.addEdge(2, 6);System.out.println("DFS遍历结果:");g.DFS(0);}
}
在这个示例中,我们创建了一个有7个节点的图,然后使用深度优先搜索(DFS)从节点0开始遍历图。Graph
类包含了图的表示,DFS
方法用于启动遍历,DFSUtil
方法是递归的辅助函数,它用于深入遍历图中的节点。
DFS在树结构和图形遍历中非常有用,并且可以用于解决许多问题,例如查找路径、拓扑排序、连通性检查等。DFS的时间复杂度是O(V + E),其中V是顶点数,E是边数。
2、广度优先搜索(Breadth-First Search,BFS):
广度优先搜索(Breadth-First Search,BFS)是一种用于遍历或搜索图形和树数据结构的算法。BFS从起始节点开始,首先访问该节点,然后逐层访问与该节点直接相邻的节点,然后再依次访问这些相邻节点的相邻节点,以此类推。
import java.util.*;class Graph {private int V; // 图的顶点数private LinkedList<Integer> adj[]; // 邻接列表Graph(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);}// 从顶点s开始进行BFS遍历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 class BFSExample {public static void main(String[] args) {Graph g = new Graph(7);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(2, 5);g.addEdge(2, 6);System.out.println("BFS遍历结果:");g.BFS(0);}
}
在这个示例中,我们创建了一个有7个节点的图,然后使用广度优先搜索(BFS)从节点0开始遍历图。Graph
类包含了图的表示,BFS
方法用于启动遍历,它使用队列来管理要访问的节点。在BFS中,节点按照层级的顺序被访问,这使得它非常适合查找最短路径等问题。
BFS在图形遍历、路径查找和连通性检查等问题中非常有用。它的时间复杂度是O(V + E),其中V是顶点数,E是边数。BFS通常使用队列来实现,确保先访问的节点先被处理,从而实现层级遍历的效果。