他们在面试中询问的问题：算法回顾，第 1 部分

大家下午好！项目中使用各种类型的算法的频率比您想象的要高。例如，我们需要根据某些参数（列）对一些数据进行排序，以便我们可以轻松地浏览它。因此，在工作面试期间，他们可能会被问到一种或另一种基本算法，并且可能会被要求使用代码来实现它，这一事实并不奇怪。 既然您访问了这个网站，我就大胆猜测您是用 Java 编写的。因此，今天我邀请您熟悉一些基本算法及其在 Java 中的具体实现示例。我所说的某些人的意思是：

1. 数组排序算法概述：
   • 冒泡排序，
   • 选择排序，
   • 插入排序，
   • 壳排序，
   • 快速排序，
   • 合并排序。
2. 贪心算法。
3. 寻路算法：
   • 深入地爬行
   • 宽阔的步行道。
4. 传输算法是Dijkstra算法。

好了，废话不多说，让我们言归正传吧。

1.排序算法概述

冒泡排序

这种排序算法主要因其简单性而闻名，但它也是执行速度最低的算法之一。例如，考虑按升序对数字进行冒泡排序。让我们想象一个随机放置的数字链，将从链的开头开始执行以下步骤：

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

在遍历整个链并执行这些步骤之后，我们会发现最大的数字位于我们一系列数字的末尾。接下来，按照上述步骤，沿着链执行完全相同的传递。但这次我们不会包含列表的最后一个元素，因为它是最大的，并且已经排在最后，正如它应该的那样。同样，我们将获得相关数字序列末尾的最后一个元素。因此，两个最大的数字已经就位了。再次开始沿着链条的通道，排除已经就位的元素，直到所有元素都处于所需的顺序。我们看一下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++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           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 - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

这种类型的排序优于上述排序，因为尽管运行时间相同 - 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} B 普通数组：{ 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 = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

目前，Shell 排序的有效性尚未得到真正证实，因为不同情况下结果有所不同。从实验中获得的估计范围从O(N ^3/2 )到O(N ^7/6 )。

快速排序

这是最流行的算法之一，因此值得特别关注。该算法的本质是从元素列表中选择一个主元元素——本质上是需要对剩余值进行排序的任何元素。小于它的值在左边，大于它的值在右边。接下来，右侧和左侧部分也由支持元素选择，并且发生相同的事情：相对于这些元素对值进行排序，然后从结果部分中选择支持元素 - 依此类推，直到我们得到排序后的结果排。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 выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так How нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно element middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с elementми большими чем 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);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       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<Item> {
   private String name;
   private int weight;
   private int cost;

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

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

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

这里没有什么特别的：三个字段——名称、重量、成本——用于指定物品的特征。另外，正如您所看到的，这里实现了Comparable接口，以便我们可以按价格对项目进行排序。接下来我们看看我们的背包的类——Bag：

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

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

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

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

• maxWeight是我们背包的容量，在创建对象时设置；
• items——背包里的物品；
• currentWeight , currentCost - 背包中所有物品的当前重量和成本，在addItem方法中添加新物品时我们会增加该重量和成本。

实际上，让我们去课堂，所有动作都发生在那里：

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

首先，我们创建一个元素列表并对其进行排序。创建一个容量为 30 个单位的袋子对象。接下来，我们将元素和 bag 对象发送给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<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / 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("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

我们将输出输出到控制台： 好一点了，不是吗？贪心算法在每一步都会做出局部最优选择，并期望最终解决方案也是最优的。这并不总是合理的，但对于许多问题，贪心算法确实提供了最佳方案。这个算法的时间复杂度是O(N)，相当不错了，对吧？好了，到这里，本文的第一部分就结束了。如果您对本文的后续部分感兴趣，该文章将讨论与它们相关的图和算法，您可以在这里找到它。