深入理解三大经典算法：快速排序、动态规划背包问题和Dijkstra算法_什么排序用到了动态规划算法

很多业务场景需要算法，成熟的算法可以提高效率，减少不必要出现的问题，规避风险！今天给大家总结了3个在实现业务场景中使用到的算法，分享给你。

1. 快速排序算法

实现原理： 快速排序是一种高效的排序算法，采用了分治法的思想。它选择一个基准元素，将数组分成两部分：左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后，递归地对这两个子数组进行排序。

示例代码：

public class QuickSort {
    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);
        }
    }
 
    private 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++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
 
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    public static void main(String[] args) {
        int[] arr = {12, 3, 9, 7, 2, 16, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

逻辑步骤：

1. 选择数组中的一个元素作为基准元素（通常选择最后一个元素）。
2. 使用分区函数将数组重新排列，使得比基准元素小的元素位于基准元素的左侧，大的位于右侧。
3. 递归地对基准元素左右两侧的子数组进行排序。

业务场景： 快速排序适用于大规模数据的排序场景，例如数据库系统的数据排序和搜索引擎的结果排序。由于其平均时间复杂度为 O(n log n)，在处理大数据时表现出色。例如，海量用户数据的排序可以使用快速排序算法来提高效率。

2. 动态规划 - 背包问题

实现原理： 背包问题是一个经典的动态规划问题，其目标是在限定的背包容量下，装入最有价值的物品。动态规划解决背包问题的核心思想是通过构建一个二维数组来记录不同背包容量和物品数量下的最大价值，然后利用状态转移方程更新数组中的值，最终得到背包能装下的最大价值。

示例代码：

public class KnapsackProblem {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
 
        return dp[n][capacity];
    }
 
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        int maxValue = knapsack(weights, values, capacity);
        System.out.println("背包能装下的最大价值为：" + maxValue);
    }
}

逻辑步骤：

1. 初始化一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时的最大价值。
2. 遍历物品和背包容量的组合，根据当前物品是否放入背包，更新 dp[i][j] 的值。
3. 最终返回 dp[n][capacity]，即所有物品都考虑完毕，背包容量为 capacity 时的最大价值。

业务场景： 动态规划背包问题在资源分配、投资决策、作业调度等领域有广泛应用。例如，在零售业的库存管理中，商家需要在有限的仓库空间内选择存放哪些商品以及存放多少数量，以最大化销售额和利润。动态规划背包问题可以帮助商家做出最优的库存管理决策。

3. 最短路径算法 - Dijkstra算法

实现原理： Dijkstra 算法用于求解单源最短路径问题，即从一个源点到图中所有其他顶点的最短路径。它通过不断选择距离源点最近的顶点来逐步确定最短路径，并使用优先队列来加速查找过程。

示例代码：

import java.util.*;
 
public class DijkstraAlgorithm {
    public static int[] dijkstra(int[][] graph, int source) {
        int vertices = graph.length;
        int[] distance = new int[vertices];
        boolean[] visited = new boolean[vertices];
 
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;
 
        for (int i = 0; i < vertices - 1; i++) {
            int minDistance = Integer.MAX_VALUE;
            int minIndex = -1;
 
            for (int v = 0; v < vertices; v++) {
                if (!visited[v] && distance[v] < minDistance) {
                    minDistance = distance[v];
                    minIndex = v;
                }
            }
 
            visited[minIndex] = true;
 
            for (int j = 0; j < vertices; j++) {
                if (!visited[j] && graph[minIndex][j] != 0 && distance[minIndex] != Integer.MAX_VALUE
                        && distance[minIndex] + graph[minIndex][j] < distance[j]) {
                    distance[j] = distance[minIndex] + graph[minIndex][j];
                }
            }
        }
 
        return distance;
    }
 
    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            {0, 8, 0, 7, 0, 4, 0, 0, 2},
            {0, 0, 7, 0, 9, 14, 0, 0, 0},
            {0, 0, 0, 9, 0, 10, 0, 0, 0},
            {0, 0, 4, 14, 10, 0, 2, 0, 0},
            {0, 0, 0, 0, 0, 2, 0, 1, 6},
            {8, 11, 0, 0, 0, 0, 1, 0, 7},
            {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
 
        int source = 0;
        int[] shortestDistances = dijkstra(graph, source);
 
        System.out.println("从源点到其他顶点的最短路径长度为：");
        for (int i = 0; i < shortestDistances.length; i++) {
            System.out.println("从顶点 " + source + " 到顶点 " + i + " 的距离为 " + shortestDistances[i]);
        }
    }
}

逻辑步骤：

1. 初始化距离数组 distance 和访问标记数组 visited，并将距离数组的源点距离设为0。
2. 循环遍历所有顶点，每次选择未访问的顶点中距离源点最近的顶点，将其标记为已访问。
3. 更新从源点到其他顶点的最短距离，如果经过当前顶点到其他顶点的距离比已有距离小，则更新距离数组。
4. 重复上述步骤，直到所有顶点都被访问过，最终得到从源点到其他顶点的最短路径长度数组。

业务场景： Dijkstra 算法在网络路由、地图导航、电信网络等领域有广泛应用。例如，在地图导航系统中，通过 Dijkstra 算法可以找到两个地点之间的最短路径，帮助用户快速规划出行路线。用户在导航软件中输入起点和终点后，系统可以利用 Dijkstra 算法计算出最短路径，并指导用户进行导航。这种应用不仅可以节省用户的时间，还可以提高行驶效率。