在很多大廠的面試中，算法是最基本的要求，像基礎的算法，冒泡，選擇，插入等，基本上都會問到。
很多同學往往忽略了其重要程度，只注重編程語言，小編并不建議這樣子，今天我們來梳理一下算法，匯總一下面試的一些基礎算法。
冒泡排序
原理：每次冒泡排序操作都會將相鄰的兩個元素進行比較，看是否滿足大小關系要求，如果不滿足，就交換這兩個相鄰元素的次序，一次冒泡至少讓一個元素移動到它應該排列的位置，重復N次，就完成了冒泡排序。
代碼實現：
/**
* 冒泡算法
* @author：溪云閣
* @date：2020年5月3日
* 冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求。
* 如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置，重復n 次，
* 就完成了 n 個數據的排序工作。
*/
public static void bubbleSort(Integer[] arr) {
// 如果只有一個元素就不用排序了
if (arr.length <= 1) {
return;
} else {
// 打印排序后的數組
System.out.println("排序前的數組：" + Arrays.toString(arr));
for (int i = 0; i < arr.length; ++i) {
// 提前退出冒泡循環的標志位,即一次比較中沒有交換任何元素，這個數組就已經是有序的了
boolean flag = false;
// 此處你可能會疑問的j<n-i-1，因為冒泡是把每輪循環中較大的數飄到后面，
for (int j = 0; j < arr.length - i - 1; ++j) {
// 數組下標又是從0開始的，i下標后面已經排序的個數就得多減1，總結就是i增多少，j的循環位置減多少
if (arr[j] > arr[j + 1]) {
// 即這兩個相鄰的數是逆序的，交換位置
final int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag)
// 沒有數據交換，數組已經有序，退出排序
break;
}
// 打印排序后的數組
System.out.println("排序后的數組：" + Arrays.toString(arr));
}
}
選擇排序
原理：先遍歷數組，然后找到一個最大或者最小的元素（這個看需要），把這個元素放到第一個位置，接著在剩余的數組中繼續找，找到比第一個大或者小的元素，放到第二個位置，依次這樣子做，從而完成排序。
代碼實現：
/**
* 選擇排序
* @author 溪云閣
* @param arr void
* 先遍歷數組，然后找到一個最大或者最小的元素（這個看需要）
* 把這個元素放到第一個位置，接著在剩余的數組中繼續找
* 找到比第一個大或者小的元素，放到第二個位置
* 依次這樣子做，從而完成排序。
*/
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 用來記錄最小值的索引位置，默認值為i
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
// 遍歷 i+1~length 的值，找到其中最小值的位置
minIndex = j;
}
}
// 交換當前索引 i 和最小值索引 minIndex 兩處的值
if (i != minIndex) {
final int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
插入排序
原理：這個比較抽象，但是我來劃分來輔助理解
一組無序序列{A1,A2,........An}
先取出A1，然后從A2與A1比較，比較完之后序列狀況是{A1,A2}{A3..........An}，這時候其中{A1,A2}就變成有序
然后取出A3 ，放到{A1,A2}有序序列合適位置，從而形成{A1,A2,A3}{A4........An}
重復這個過程，直到取出An放入{A1,A2........An-1}有序序列中
代碼實現：
/**
* 插入排序
* @author 溪云閣
* @param ins
* @return int[]
* 一組無序序列{A1,A2,........An}
* 先取出A1，然后從A2與A1比較，比較完之后序列狀況是{A1,A2}{A3..........An}，這時候其中{A1,A2}就變成有序
* 然后取出A3 ，放到{A1,A2}有序序列合適位置，從而形成{A1,A2,A3}{A4........An}
* 重復這個過程，直到取出An放入{A1,A2........An-1}有序序列中
*/
public static int[] insertSort(int[] ins) {
for (int i = 1; i < ins.length; i++) {
// 保存每次需要插入的那個數
final int temp = ins[i];
int j;
for (j = i; j > 0 && ins[j - 1] > temp; j--) {
// 吧大于需要插入的數往后移動。最后不大于temp的數就空出來j
ins[j] = ins[j - 1];
}
// 將需要插入的數放入這個位置
ins[j] = temp;
}
return ins;
}
希爾排序
原理：希爾排序是插入排序的改進版，它將數組按照約定的數量分成N列，對每一列執行插入排序，接著縮小步長，不斷重復這過程，最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法。
代碼實現：
/**
* 希爾排序
* @author 溪云閣
* @param arrays void
* 希爾排序是插入排序的改進版，
* 它將數組按照約定的數量分成N列，對每一列執行插入排序，接著縮小步長
* 不斷重復這過程，最后整個表就只有一列了
*/
public static void shellSort(int[] arrays) {
if (arrays == null || arrays.length <= 1) {
return;
} else {
// 增量
int incrementNum = arrays.length / 2;
while (incrementNum >= 1) {
for (int i = 0; i < arrays.length; i++) {
// 進行插入排序
for (int j = i; j < arrays.length - incrementNum; j = j + incrementNum) {
if (arrays[j] > arrays[j + incrementNum]) {
final int temple = arrays[j];
arrays[j] = arrays[j + incrementNum];
arrays[j + incrementNum] = temple;
}
}
}
// 設置新的增量
incrementNum = incrementNum / 2;
}
}
}
歸并排序
原理：歸并其實就是分而治之的思想，對于每一個數組，每個遞歸過程涉及三個步驟
1、分解:：把待排序的 n 個元素的序列分解成兩個子序列, 每個子序列包括 n/2 個元素.
2、治理:：對每個子序列分別調用歸并排序MergeSort, 進行遞歸操作
3、合并：合并兩個排好序的子序列,生成排序結果.
代碼實現：
/**
* 兩路歸并算法，兩個排好序的子序列合并為一個子序列
* @author 溪云閣
* @param a
* @param left
* @param mid
* @param right void
*/
public static void merge(int[] a, int left, int mid, int right) {
// 輔助數組
final int[] tmp = new int[a.length];
// p1、p2是檢測指針，k是存放指針
int p1 = left, p2 = mid + 1, k = left;
while (p1 <= mid && p2 <= right) {
if (a[p1] <= a[p2])
tmp[k++] = a[p1++];
else
tmp[k++] = a[p2++];
}
while (p1 <= mid) {
// 如果第一個序列未檢測完，直接將后面所有元素加到合并的序列中
tmp[k++] = a[p1++];
}
while (p2 <= right) {
// 同上
tmp[k++] = a[p2++];
}
// 復制回原素組
for (int i = left; i <= right; i++) {
a[i] = tmp[i];
}
}
/**
* 歸并排序
* @author 溪云閣
* @param a
* @param start
* @param end void
*/
public static void mergeSort(int[] a, int start, int end) {
// 當子序列中只有一個元素時結束遞歸
if (start < end) {
// 劃分子序列
final int mid = (start + end) / 2;
// 對左側子序列進行遞歸排序
mergeSort(a, start, mid);
// 對右側子序列進行遞歸排序
mergeSort(a, mid + 1, end);
// 合并
merge(a, start, mid, end);
}
}
快速排序
原理：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
代碼實現：
/**
* 快速排序
* @author 溪云閣
* @param arr 待排序列
* @param leftIndex 待排序列起始位置
* @param rightIndex 待排序列結束位置
*/
public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex) {
return;
} else {
int left = leftIndex;
int right = rightIndex;
// 待排序的第一個元素作為基準值
final int key = arr[left];
// 從左右兩邊交替掃描，直到left = right
while (left < right) {
while (right > left && arr[right] >= key) {
// 從右往左掃描，找到第一個比基準值小的元素
right--;
}
// 找到這種元素將arr[right]放入arr[left]中
arr[left] = arr[right];
while (left < right && arr[left] <= key) {
// 從左往右掃描，找到第一個比基準值大的元素
left++;
}
// 找到這種元素將arr[left]放入arr[right]中
arr[right] = arr[left];
}
// 基準值歸位
arr[left] = key;
// 對基準值左邊的元素進行遞歸排序
quickSort(arr, leftIndex, left - 1);
// 對基準值右邊的元素進行遞歸排序。
quickSort(arr, right + 1, rightIndex);
}
}
--END--
作者：@溪云閣
如需要源碼，轉發，關注后私信我。
部分圖片來源網絡，如侵權請聯系刪除，謝謝！
