求职面试问答：Java 算法，第 1 部分

开发项目比您想象的更频繁地使用各种算法。例如，假设我们需要按某些参数（列）对一些数据进行排序，这样我们就可以毫不费力地浏览数据。因此，求职面试官向您询问特定的基本算法并可能给出使用代码实现它的任务一点也不奇怪。 既然你在这个网站上，我就大胆地假设你是用 Java 编写的。这就是为什么今天我建议您熟悉一些基本算法以及如何在 Java 中实现它们的具体示例。“一些”，我的意思是：

1. 数组排序算法概述：
   • 冒泡排序，
   • 选择排序，
   • 插入排序，
   • 贝壳排序，
   • 快速排序，
   • 归并排序，
2. 贪心算法
3. 寻路算法
   • 深度优先搜索
   • 广度优先搜索
4. Dijkstra 的最短路径优先算法

好了，废话少说，言归正传。

一、排序算法概述

冒泡排序

这种排序算法主要以其简单而著称，但它也是最慢的算法之一。例如，让我们考虑按升序对数字进行冒泡排序。让我们想象一个随机的数字序列。我们将从序列的开头开始对这些数字执行以下步骤：

• 比较两个数字；
• 如果左边的数字较大，则交换它们；
• 向右移动一个位置。

在对整个序列执行这些步骤后，我们会发现最大的数字在我们的数字系列的末尾。然后我们再次遍历序​​列，执行与上面完全相同的步骤。但是这次我们不会包括列表的最后一个元素，因为它是最大的数字，并且在对数字进行排序时已经恰好位于它应该出现的位置。再一次，我们最终会将下一个最大的数字移到序列的末尾。当然，这意味着两个最大的数字都站在了正确的位置。同样，我们遍历序列，排除已经在其位置的元素，直到所有元素都按要求的顺序排列。我们来看看冒泡排序在Java代码中是如何实现的：

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

如您所见，这里没有什么复杂的。一切看起来都很棒，如果不是因为一个缺点，那就太棒了——冒泡排序非常非常慢。它的时间复杂度是 O(N²)，因为我们有嵌套循环。对元素执行 N 次外循环。内循环也执行了N次。结果，我们得到 N*N 或 N² 次迭代。

选择排序

该算法类似于冒泡排序，但速度更快一些。同样，作为示例，让我们以我们想要按升序排列的数字序列为例。该算法的本质是顺序遍历所有数字并选择最小的元素，我们将其与最左边的元素（第 0 个元素）交换。这里我们有一个类似冒泡排序的情况，但是在这种情况下我们排序的元素将是最小的。因此，下一次遍历元素将从索引为 1 的元素开始。我们将重复这些遍历，直到所有元素都已排序。Java中的实现：

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // Put the sorted number in the proper cell
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

该算法优于冒泡排序，因为这里所需的移位次数从 O(N²) 减少到 O(N)。我们并没有在整个列表中驱动一个元素，但是比较的次数仍然是 O(N²)。

插入排序

我们考虑要按升序排列的另一个数字序列。该算法包括放置一个标记，标记左侧的所有元素已经在它们之间进行了部分排序。在算法的每个步骤中，将选择一个元素并将其放置在部分排序序列中的所需位置。因此，排序的部分将增长，直到所有元素都被检查过。您是否想知道如何获得已排序元素的子集以及我们如何确定放置标记的位置？但是由第一个元素组成的数组已经排序了，不是吗？我们来看看Java中的实现：

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i is the dividing marker
           int temp = array[i]; // Make a temporary copy of the marked element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // Until a smaller element is found
               array[j] = array[j - 1]; // We shift the element to the right
               --j;
           }
           array[j] = temp;   // Insert the marked element in its proper place
       }
   }
}

这种排序优于上述排序，因为尽管它具有相同的 O(N²) 运行时间，但该算法的速度是冒泡排序的两倍，略快于选择排序。

壳排序

这种排序本质上是一种改进的插入排序。我在说什么？让我们把要紧的事情放在第一位。我们首先要选择一个区间。有很多方法可以做出这种选择。我们不会对此进行过多的详细介绍。让我们将数组分成两半并得到一些数字——这将是我们的区间。所以，如果我们的数组中有 9 个元素，那么我们的间隔将为 9/2 = 4.5。我们丢弃小数部分并得到 4，因为数组索引只能是整数。我们将利用这段时间来组成我们的小组。如果一个元素的索引为 0，则其组中下一个元素的索引为 0+4，即 4。第三个元素的索引为 4+4，第四个为 8+4，依此类推。在第二组中，第一个元素将是 1,5,9...在第三组和第四组中，情况将相同。因此，从数字数组 {6,3,8,8,6,9,4,11,1} 我们得到四组： I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} 它们保留了它们在通用数组中的位置，但我们标记为同一组的成员：{6,3,8,8,6,9,4,11,1} 接下来，插入对这些组应用排序，然后它们看起来像这样： I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} 在一般数组中，组占用的单元格将保持不变，但它们的内部顺序将根据上面组的顺序发生变化：{1,3,4,8,6,9,8,11,6} 数组变成了更有序，不是吗？下一个间隔将除以 2： 4/2 = 2 我们有两组： I — {1,4,6,8,6} II — {3,8,9,11} 在一般数组中，我们有: {1,3,4,8,6,9,8,11,6} 我们对两组都运行插入排序算法，得到这个数组：{1,3,4,8,6,9,6, 11、8} 现在我们的数组差不多排序好了。我们需要执行算法的最后一次迭代：我们将间隔除以 2：2/2 = 1。我们得到一个由整个数组组成的组：{1,3,4,8,6,9,6,11 ,8} 在其上运行插入排序算法，我们得到：{1,3,4,6,6,8,8,9,11} 让我们看看如何在 Java 代码中实现这种排序：

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // Shrink the interval
       }
   }
}

目前，Shellsort 的性能不容易表征，因为结果在不同情况下会有所不同。实验估计范围从 O(N ^3/2 ) 到 O(N ^7/6 )。

快速排序

这是最流行的算法之一，因此值得特别关注。该算法的要点是在元素列表中选择一个枢轴元素。我们相对于枢轴元素对所有其他元素进行排序。小于枢轴元素的值位于左侧。大于它的值在右边。接下来，还在左右部分中选择了 pivot 元素，同样的事情发生了：值相对于这些元素进行排序。然后在新形成的部分中选择枢轴元素，依此类推，直到我们得到一个排序序列。该算法的以下 Java 实现使用递归：

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0) // Condition for exiting recursion if the array length is 0
           return;

       if (min> = max) // Terminate the recursion, since there is nothing to divide
           return;


       int middle = min + (max - min) / 2; // Select the middle
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) { // Swap places
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // Make a recursive call on the elements that are less than middle
           recursionFastSort(array, min, j);

       if (max > i) // Make a recursive call on the elements larger than middle
           recursionFastSort(array, i, max);
   }
}

毫无疑问，快速排序算法是最受欢迎的，因为在大多数情况下它运行得比其他算法快。它的时间复杂度是 O(N*logN)。

合并排序

这种类型也很受欢迎。它是依赖于“分而治之”原则的众多算法之一。此类算法首先将问题划分为可管理的部分（快速排序是此类算法的另一个示例）。那么这个算法的要点是什么？

划分：

该数组被分成大小大致相同的两部分。这两部分中的每一个都再分成两部分，依此类推，直到剩下最小的不可分割部分。当每个数组只有一个元素时，我们有最小的不可分割的部分，即一个已经排序的数组。

征服：

这是我们开始给算法命名的过程的地方：合并。为此，我们将两个结果排序数组合并为一个。在这种情况下，两个数组的第一个元素中最小的一个被写入结果数组。重复此操作，直到将这两个数组中的所有元素都复制过来。也就是说，如果我们有两个最小数组 {6} 和 {4}，我们比较它们的值并生成这个合并结果：{4,6}。如果我们对数组 {4,6} 和 {2,8} 进行了排序，我们首先比较值 4 和 2，然后将 2 写入结果数组。之后比较4和8，我们写4。最后比较6和8。因此，我们将写 6，然后才写 8。结果，我们得到以下合并数组：{2,4,6,8}。这在 Java 代码中看起来如何？要运行这个算法，我们使用递归会很方便：

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
       int[] bufferArr = new int[array1.length];// Buffer array
       return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
           return sortArr;
       }

       // Make a recursive call to get two sorted arrays:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Merge the sorted arrays:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

与快速排序一样，我们将递归方法移动到中间方法中，这样用户只需提供要排序的数组，而不必担心提供任何额外的默认参数。该算法与快速排序有相似之处，不出所料，其执行速度是相同的：O(N*logN)。

2. 贪心算法

贪心算法是一种在每个阶段做出局部最优决策的方法，假设最终解决方案也将是最优的。“最佳”解决方案将是在任何特定步骤/阶段提供最明显和直接好处的解决方案。为了探索这个算法，让我们来看一个相当常见的问题——背包问题。假装你是一个小偷。您在晚上带着背包（背包）闯入了一家商店。在你面前有几件你可以偷的东西。但与此同时，您的背包容量有限。它可以承载不超过 30 个单位的重量。您还想带走能装进背包的最有价值的一套商品。您如何确定将什么放入包中？所以，

1. 选择尚未被拿走的最昂贵的物品。
2. 如果它能装进背包，就把它放进去。如果装不下，就把它留下。
3. 我们已经偷走了一切吗？如果不是，我们返回到步骤 1。如果是，那么我们将快速离开商店，因为我们已经完成了我们来这里要做的事情。

让我们看看这个，但在 Java 中。这是 Item 类的外观：

public class Item implements Comparable {
   private String name;
   private int weight;
   private int value;

   public Item(String name, int weight, int value) {
       this.name = name;
       this.weight = weight;
       this.value = value;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getValue() {
       return value;
   }

   @Override
   public int compareTo(Item o) {
       return this.value > o.value ? -1 : 1;
   }
}

这里没有什么特别之处：三个字段（名称、重量、值）定义了项目的特征。此外，如您所见，实现了 Comparable 接口以允许我们按价格对项目进行排序。接下来，我们将查看 Bag 类，它代表我们的背包：

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentValue;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentValue = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentValue() {
       return currentValue;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentValue += item.getValue();
   }
}

• maxWeight是我们背包的容量，这是我们创建对象时设置的；
• items 代表我们背包里的物品；
• currentWeight , currentValue — 这些字段存储背包中所有物品的当前重量和价值，当我们在 addItem 方法中添加新物品时，我们会增加它们。

无论如何，现在让我们转到发生所有操作的类：

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("Guitar", 7, 800));
       items.add(new Item("Iron", 6, 500));
       items.add(new Item("Tea pot", 3, 300));
       items.add(new Item("Lamp", 4, 500));
       items.add(new Item("Television", 15, 2000));
       items.add(new Item("Vase", 2, 450));
       items.add(new Item("Mixer", 2, 400));
       items.add(new Item("Blender", 3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
               ". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
} 

首先，我们创建一个项目列表并对其进行排序。我们创建了一个容量为 30 单位的袋子对象。接下来，我们将物品和包对象传递给 fillBackpack 方法，该方法根据我们的贪心算法填充背包：

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

这很简单：我们开始查看按成本排序的项目列表，如果容量允许，将它们放入包中。如果没有足够的空间，那么该项目将被跳过，我们将继续遍历其余项目，直到我们到达列表的末尾。运行 main 后，控制台输出如下： 这是一个贪心算法的例子：在每一步中，选择一个局部最优解，最后得到一个全局最优解。在我们的例子中，最好的选择是最昂贵的物品。但这是最好的解决方案吗？您不认为可以稍微改进我们的解决方案，以便用总价值更高的物品来装满我们的背包吗？让我们来看看如何做到这一点。

public static void effectiveFillBackpack(Bag bag, List items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getValue() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

在这里，我们首先计算每个项目的价值重量比。这告诉我们给定项目的每个单位的价值。然后我们使用这些比率对我们的物品进行分类并将它们添加到我们的包中。让我们运行以下命令：

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
       ". The total cost of items in the knapsack is " + secondBag.getCurrentValue());

我们得到这个控制台输出： 好一点，不是吗？贪心算法每一步都做局部最优选择，希望最后的解也是最优的。这个假设并不总是有效，但对于许多任务，贪心算法确实会产生最佳的最终解决方案。该算法的时间复杂度为 O(N)。很不错吧？