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