求職面試問答：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)。很不錯吧？