1.序
從今天開始我分模塊推出面試指南，首先作為程式設計師最重要的是數據結構，數據結構是我們的本科課程，同時也是我們的必備課程。排序是我們的必考內容，今天以排序算法引出我們的數據結構。
2.總3.詳敘3.1插入排序3.1.1直接插入
博客連結（詳解）
https://blog.csdn.net/weixin_41563161/article/details/100858281
敘述：
將待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，就得到一個新的序列。（抓撲克牌思想）
特點：元素越接近有序，直接插入排序算法的時間效率越高，算法的本質是減治算法；因此當數組接近有序或大概率有序的情況下，或是數組的數量比較小的時候採用插入排序。
時間複雜度
最好情況：（有序且為正序）O(n)
最壞情況：（逆序）O(n^2）
平均情況：O(n2)
空間複雜度：O(1)
具有穩定性
private static void InsertSort(int[] arr) { int tmp = 0; int i ,j; for(i = 1; i < arr.length; i++) {
tmp = arr[i]; for(j = i-1;j >=0 && arr[j] > tmp;j--) { arr[j+1] = arr[j]; } arr[j+1] = tmp; }}一般來說，插入排序都採用in-place在數組上實現。具體算法描述如下：
⒈ 從第一個元素開始，該元素可以認為已經被排序
⒉ 取出下一個元素，在已經排序的元素序列中從後向前掃描
⒊ 如果該元素（已排序）大於新元素，將該元素移到下一位置
⒋ 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重複步驟2~5
如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。
實例
基本思想：
把n個待排序的元素看成一個有序表和一個無序表，開始時有序表中只有一個元素，無序表中有n-1個元素；排序過程即每次從無序表中取出第一個元素，將它插入到有序表中，使之成為新的有序表，重複n-1次完成整個排序過程。
實例：
0.初始狀態 3，1，5，7，2，4，9，6（共8個數）
有序表：3；無序表：1，5，7，2，4，9，6
1.第一次循環，從無序表中取出第一個數 1，把它插入到有序表中，使新的數列依舊有序
有序表：1，3；無序表：5，7，2，4，9，6
2.第二次循環，從無序表中取出第一個數 5，把它插入到有序表中，使新的數列依舊有序
有序表：1，3，5；無序表：7，2，4，9，6
3.第三次循環，從無序表中取出第一個數 7，把它插入到有序表中，使新的數列依舊有序
有序表：1，3，5，7；無序表：2，4，9，6
4.第四次循環，從無序表中取出第一個數 2，把它插入到有序表中，使新的數列依舊有序
有序表：1，2，3，5，7；無序表：4，9，6
5.第五次循環，從無序表中取出第一個數 4，把它插入到有序表中，使新的數列依舊有序
有序表：1，2，3，4，5，7；無序表：9，6
6.第六次循環，從無序表中取出第一個數 9，把它插入到有序表中，使新的數列依舊有序
有序表：1，2，3，4，5，7，9；無序表：6
7.第七次循環，從無序表中取出第一個數 6，把它插入到有序表中，使新的數列依舊有序
有序表：1，2，3，4，5，6，7，9；無序表：（空）
3.1.2希爾排序博客連結（詳解）
https://blog.csdn.net/weixin_41563161/article/details/101637859
敘述：
先將數據進行分組，通過插入排序的方式讓數據基本有序，然乎再進行插入排序，能夠讓插入排序最壞情況的概率降低；
分組的方法：固定步長取值分為一組的方法。分組越多（步長越小）大的數往後走的越快，分組越少排完後越接近有序
希爾排序是對直接插入排序的優化
時間複雜度：最好情況（正序）：O（n）
平均情況：O(n1.3–n2)
最壞情況（逆序）：O(n2)
空間複雜度：O(1)
不具有穩定性的排序
private static void ShellSort(int[] arr) { int h = 1; while(h < arr.length / 3) { h = h * 3 + 1; } while(h > 0) { int tmp = 0; for(int i = h; i < arr.length; i++) { tmp = arr[i]; int j = i; while(j > h - 1 && arr[j - h] >= tmp) {
arr[j] = arr[j - h]; j -= h; } arr[j] = tmp; } h = (h - 1) / 3; }}3.2交換排序3.2.1冒泡排序博客連結（詳解）
https://blog.csdn.net/weixin_41563161/article/details/100858281
根據序列中兩個記錄的值的比較結構來交換兩個記錄在序列中的位置，將值較小的向前移動
特點：算法的本質是減治排序
時間複雜度：最好情況（正序）：O（n）
最壞情況（逆序）：O(n2)
平均情況：O(n2)
空間複雜度：O(1)
穩定性：穩定private static void BubbleSort(int[] source) { int tmp = 0; for(int i =0;i<source.length;i++){ for (int j =0;j<source.length-1-i;j++){ if(source[j]>source[j+1]){ tmp = source[j+1]; source[j+1] = source[j]; source[j] = tmp; } } }}3.2.2快速排序
博客連結（詳解）
https://blog.csdn.net/weixin_41563161/article/details/101921177
一共包含三大步：
1.確定待排序元素序列中的某元素作為基準值（選區間最右邊的元素/選中間元素 與最右邊的元素交換）
2.以基準值為界，大於基準值的放在基準值的右邊，小於基準值的放在基準值左邊(hover 挖坑 前後下標)
3.然後對左右序列重複該過程，直到小區間中只有一個元素或沒有元素為止（size==0||size ==1）
特點：採用分治算法
時間複雜度：最好情況：O(n*long(n)) （區間分割，組成形式可以考慮為二叉樹形式，最好情況就成了單支樹，分治算法變成了減治算法）
平均情況：O(n*long(n))
最差情況：O（n2）
空間複雜度：O(log(n))—O（n）
穩定性：不穩定
private static void QuickSort(int[] arr, int low, int high) { if(low < high){ int index = GetIndex(arr, low, high); QuickSort(arr, 0, index - 1); QuickSort(arr, index + 1, high); } } private static int GetIndex(int[] arr, int low, int high) { int i = low, j = high; int x = arr[low]; while (i < j) { while(i < j && arr[j] >= x){ j--; } if(i < j) { arr[i] = arr[j]; i++; } while(i < j && arr[i] < x) { i++; } if(i < j) { arr[j] = arr[i]; j--; } } arr[i] = x; return i; }快速排序我們可以近似的想成一個完全二叉樹
一個數組的容量是N,第一層遞歸遍歷的次數是N,因為數組裡每個數字都需要和key比較,那麼接下來遍歷分出來的兩個區間，總的遍歷次數還會是近似是N,以此類推,直到分為最後一個,也就是說樹的高度是lgn,也就是遞歸次數,所以時間複雜度是N*lgN.
3.3交換排序3.3.1選擇排序
博客連結（詳解）
https://blog.csdn.net/weixin_41563161/article/details/100858281
每一次從待排序的元素中選出最小的一個元素，若它不是這組元無序素中的最後一個元素，則將它與存放這組有序元素的起始位置交換，直到全部待排序元素全部排完。
或是從無序元素中選出一個最大的，若其不是無序區間的最後一個元素，則將其與存放有序區間的最後一個元素交換，直到無序元素全部排完
特點：效率不高，算法的本質是減治算法
時間複雜度：最好情況：O(n2)
平均情況：O(n2)
最壞情況：O(n2)
空間複雜度：O（1）
穩定性：不穩定* @Author liuhaidong * @Description 選擇排序 * @Date 17:10 2019/10/2 0002 */ private static void SelectionSort(int[] arr) { int k =0; int tmp = 0; for(int i = 0;i<arr.length-1;i++){ k = i; for(int j =i+1;j<arr.length;j++){ if(arr[j] <arr[k]){ k = j; } } tmp = arr[i]; arr[i] = arr[k]; arr[k] = tmp; } }3.3.1堆排序
博客連結（詳解）
https://blog.csdn.net/weixin_41563161/article/details/101937543
利用堆的特點設計的一種排序算法，排升序要建大堆，排降序要建小堆，建堆是從第一個非葉子節點開始建，利用向下調整的思想逐步建立出整個堆。
每次將未排序序列的第一個與最後一個元素進行交換，然後利用向下調整，將最大的元素調整到最後一個。
特點：算法的本質是減治算法
時間複雜度：最好情況：O（n*longn）
平均情況：O（n*longn）
最壞情況：O（n*longn）
空間複雜度：O(1)
穩定性：不穩定private static void HeadSort(int[] arr) { int startIndex = (arr.length-1)/2; for(int i =startIndex;i>=0;i--){ ToMaxHeap(arr,arr.length,i); } for(int i = arr.length-1;i>0;i--){ int t = arr[0]; arr[0] = arr[i]; arr[i] = t; ToMaxHeap(arr,i,0); } } private static void ToMaxHeap(int[] arr, int size, int index) { int leftNodeIndex = index * 2 + 1; int rightNodeIndex = index * 2 + 2; int maxIndx = index; if (leftNodeIndex < size && arr[leftNodeIndex] > arr[maxIndx]) { maxIndx = leftNodeIndex; } if (rightNodeIndex < size && arr[rightNodeIndex] > arr[maxIndx]) { maxIndx = rightNodeIndex; } if (maxIndx != index) { int t = arr[maxIndx]; arr[maxIndx] = arr[index]; arr[index] = t; ToMaxHeap(arr, size, index); }}3.4歸並排序博客連結（詳解）
https://blog.csdn.net/weixin_41563161/article/details/101942087
把數組平均分成兩部分，分別對左右兩部分做均分，直到區間的size<=1，然後利用一個額外的數組空間，逐步將兩個數組按序排列，再將排好的數據拷貝回原始數組，這樣使子序列的段間有序，將子序列歸併為完整的序列
特點：分治算法，是外部排序最好的算法
時間複雜度：最好情況：O（n*log(n)）
空間複雜度：O（n）
穩定性：穩定
需要做外部排序的情況：
1.內存放不下了，切成小塊，將每一小塊排序，然後合併n個有序數組
private static void MergrSort(int[] arr) { Split(arr,0,arr.length-1); } private static void Split(int[] arr, int startIndex, int endIndex) { int centerIndex = (startIndex + endIndex)/2; if(startIndex < endIndex){ Split(arr, startIndex, centerIndex); Split(arr, centerIndex+1, endIndex); Mergr(arr,startIndex,centerIndex,endIndex); } } private static void Mergr(int[] arr, int startIndex, int centerIndex, int enIndex) { int[] tempArr = new int[enIndex-startIndex+1]; int i = startIndex; int j = centerIndex+1; int index = 0; while (i <= centerIndex && j<=enIndex){ if(arr[i] <= arr[j]){ tempArr[index] = arr[i]; i++; }else { tempArr[index] = arr[j]; j++; } index++; } while(i <= centerIndex){ tempArr[index] = arr[i]; i++; index++; } while(j <= enIndex){ tempArr[index] = arr[j]; j++; index++; } for(int k = 0;k<tempArr.length;k++){ arr[k+startIndex] = tempArr[k]; } }4.總結其中快速排序、堆排序 、歸併排序必須要能默寫出來的。因為篇幅問題所以不能展開，之後會對每一個算法進行展開講解。一定要了解每個排序算法的原理，做到胸有成竹，這樣才可以夢想成真。
本公眾號分享自己從程式設計師小白到經歷春招秋招斬獲10幾個offer的面試筆試經驗，其中包括【Java】、【作業系統】、【計算機網絡】、【設計模式】、【數據結構與算法】、【大廠面經】、【資料庫】期待你加入！！！
優質文章推薦：
1.計算機網絡----三次握手四次揮手
2.夢想成真項目自我介紹
3.IntelliJ IDEA 2020.3.2激活破解（附安裝包及補丁、激活碼）
4.震驚！來看《這份程式設計師面試手冊》！！！
5.一字一句教你面試「個人簡介」
6.接近30場面試分享
7.你們要的免費書來了
8.思維導圖Xmind2020 3.1中文正式版激活指南