開發項目比您想像的更頻繁地使用各種算法。例如，假設我們需要按某些參數（列）對一些數據進行排序，這樣我們就可以毫不費力地瀏覽數據。因此，求職面試官向您詢問特定的基本算法並可能給出使用代碼實現它的任務一點也不奇怪。 ![求職面試問答：Java 中的算法，第 1 - 1 部分]()
既然你在這個網站上，我就大膽地假設你是用 Java 編寫的。這就是為什麼今天我建議您熟悉一些基本算法以及如何在 Java 中實現它們的具體示例。“一些”，我的意思是：
既然你在這個網站上，我就大膽地假設你是用 Java 編寫的。這就是為什麼今天我建議您熟悉一些基本算法以及如何在 Java 中實現它們的具體示例。“一些”，我的意思是：
- 數組排序算法概述：
- 冒泡排序，
- 選擇排序，
- 插入排序，
- 貝殼排序，
- 快速排序，
- 歸併排序，
- 貪心算法
- 尋路算法
- 深度優先搜索
- 廣度優先搜索
- Dijkstra 的最短路徑優先算法
一、排序算法概述
冒泡排序
這種排序算法主要以其簡單而著稱，但它也是最慢的算法之一。例如，讓我們考慮按升序對數字進行冒泡排序。讓我們想像一個隨機的數字序列。我們將從序列的開頭開始對這些數字執行以下步驟：- 比較兩個數字；
- 如果左邊的數字較大，則交換它們；
- 向右移動一個位置。
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;
}
}
}
}
}
選擇排序
該算法類似於冒泡排序，但速度更快一些。同樣，作為示例，讓我們以我們想要按升序排列的數字序列為例。該算法的本質是順序遍歷所有數字並選擇最小的元素，我們將其與最左邊的元素（第 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;
}
}
}
插入排序
我們考慮要按升序排列的另一個數字序列。該算法包括放置一個標記，標記左側的所有元素已經在它們之間進行了部分排序。在算法的每個步驟中，將選擇一個元素並將其放置在部分排序序列中的所需位置。因此，排序的部分將增長，直到所有元素都被檢查過。您是否想知道如何獲得已排序元素的子集以及我們如何確定放置標記的位置？但是由第一個元素組成的數組已經排序了，不是嗎？我們來看看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
}
}
}
殼排序
這種排序本質上是一種改進的插入排序。我在說什麼？讓我們把要緊的事情放在第一位。我們首先要選擇一個區間。有很多方法可以做出這種選擇。我們不會對此進行過多的詳細介紹。讓我們將數組分成兩半並得到一些數字——這將是我們的區間。所以，如果我們的數組中有 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
}
}
}
快速排序
這是最流行的算法之一，因此值得特別關注。該算法的要點是在元素列表中選擇一個樞軸元素。我們相對於樞軸元素對所有其他元素進行排序。小於樞軸元素的值位於左側。大於它的值在右邊。接下來，還在左右部分中選擇了 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);
}
}
合併排序
這種類型也很受歡迎。它是依賴於“分而治之”原則的眾多算法之一。此類算法首先將問題劃分為可管理的部分（快速排序是此類算法的另一個示例）。那麼這個算法的要點是什麼？劃分：
該數組被分成大小大致相同的兩部分。這兩部分中的每一個都再分成兩部分，依此類推，直到剩下最小的不可分割部分。當每個數組只有一個元素時，我們有最小的不可分割的部分，即一個已經排序的數組。征服：
這是我們開始給算法命名的過程的地方：合併。為此，我們將兩個結果排序數組合併為一個。在這種情況下，兩個數組的第一個元素中最小的一個被寫入結果數組。重複此操作，直到將這兩個數組中的所有元素都複製過來。也就是說，如果我們有兩個最小數組 {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;
}
}
2. 貪心算法
貪心算法是一種在每個階段做出局部最優決策的方法，假設最終解決方案也將是最優的。“最佳”解決方案將是在任何特定步驟/階段提供最明顯和直接好處的解決方案。為了探索這個算法，讓我們來看一個相當常見的問題——背包問題。假裝你是一個小偷。您在晚上帶著背包（背包）闖入了一家商店。在你面前有幾件你可以偷的東西。但與此同時，您的背包容量有限。它可以承載不超過 30 個單位的重量。您還想帶走能裝進背包的最有價值的一套商品。您如何確定將什麼放入包中？所以，- 選擇尚未被拿走的最昂貴的物品。
- 如果它能裝進背包，就把它放進去。如果裝不下，就把它留下。
- 我們已經偷走了一切嗎？如果不是，我們返回到步驟 1。如果是，那麼我們將快速離開商店，因為我們已經完成了我們來這裡要做的事情。
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;
}
}
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());
}
}
public static void fillBackpack(Bag bag, List<Item> items) {
for (Item item : items) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
bag.addItem(item);
}
}
}
背包重量為29，背包內物品總價值為3700
這是一個貪心算法的例子：在每一步中，選擇一個局部最優解，最後得到一個全局最優解。在我們的例子中，最好的選擇是最昂貴的物品。但這是最好的解決方案嗎？您不認為可以稍微改進我們的解決方案，以便用總價值更高的物品來裝滿我們的背包嗎？讓我們來看看如何做到這一點。
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());
背包的重量是29，背包裡物品的總成本是4150
好一點，不是嗎？貪心算法每一步都做局部最優選擇，希望最後的解也是最優的。這個假設並不總是有效，但對於許多任務，貪心算法確實會產生最佳的最終解決方案。該算法的時間複雜度為 O(N)。很不錯吧？
GO TO FULL VERSION