他們在面試中詢問的問題：演算法回顧，第 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)，相當不錯了，對吧？好了，到這裡，本文的第一部分就結束了。如果您對本文的後續部分感興趣，該文章將討論與它們相關的圖和演算法，您可以在這裡找到它。