復(fù)雜度 相關(guān)概念
時(shí)間復(fù)雜度與時(shí)間效率：O(1) < O(log2N) < O(n) < O(N * log2N) < O(N2) < O(N3) < 2N < 3N < N! 一般來(lái)說(shuō)，前四個(gè)效率比較高，中間兩個(gè)差強(qiáng)人意，后三個(gè)比較差（只要N比較大，這個(gè)算法就動(dòng)不了了）。 常數(shù)階int sum = 0,n = 100; //執(zhí)行一次 sum = (1+n)*n/2; //執(zhí)行一次 System.out.println (sum); //執(zhí)行一次上面算法的運(yùn)行的次數(shù)的函數(shù)為 f(n)=3，根據(jù)推導(dǎo)大 O 階的規(guī)則 1，我們需要將常數(shù) 3 改為 1，則這個(gè)算法的時(shí)間復(fù)雜度為 O(1)。如果 sum=(1+n)*n/2 這條語(yǔ)句再執(zhí)行 10 遍，因?yàn)檫@與問題大小 n 的值并沒有關(guān)系，所以這個(gè)算法的時(shí)間復(fù)雜度仍舊是 O(1)，我們可以稱之為常數(shù)階。 線性階線性階主要要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況，如下所示： 上面算法循環(huán)體中的代碼執(zhí)行了n次，因此時(shí)間復(fù)雜度為O(n)。 對(duì)數(shù)階接著看如下代碼： int number = 1;while (number < n) { number = number * 2; //時(shí)間復(fù)雜度為O(1)的算法 ...}可以看出上面的代碼，隨著 number 每次乘以 2 后，都會(huì)越來(lái)越接近 n，當(dāng) number 不小于 n 時(shí)就會(huì)退出循環(huán)。假設(shè)循環(huán)的次數(shù)為 X，則由 2^x=n 得出 x=log?n，因此得出這個(gè)算法的時(shí)間復(fù)雜度為 O(logn)。 平方階下面的代碼是循環(huán)嵌套： 內(nèi)層循環(huán)的時(shí)間復(fù)雜度在講到線性階時(shí)就已經(jīng)得知是O(n)，現(xiàn)在經(jīng)過外層循環(huán)n次，那么這段算法的時(shí)間復(fù)雜度則為O(n2)。 算法思想 分治(Divide and Conquer)分治算法思想很大程度上是基于遞歸的，也比較適合用遞歸來(lái)實(shí)現(xiàn)。顧名思義，分而治之。一般分為以下三個(gè)過程：
比較經(jīng)典的應(yīng)用就是歸并排序 (Merge Sort) 以及快速排序 (Quick Sort) 等。我們來(lái)從歸并排序理解分治思想，歸并排序就是將待排序數(shù)組不斷二分為規(guī)模更小的子問題處理，再將處理好的子問題合并起來(lái)。 貪心(Greedy)貪心算法是動(dòng)態(tài)規(guī)劃算法的一個(gè)子集，可以更高效解決一部分更特殊的問題。實(shí)際上，用貪心算法解決問題的思路，并不總能給出最優(yōu)解。因?yàn)樗诿恳徊降臎Q策中，選擇目前最優(yōu)策略，不考慮全局是不是最優(yōu)。 貪心算法+雙指針求解
回溯(Backtracking)使用回溯法進(jìn)行求解，回溯是一種通過窮舉所有可能情況來(lái)找到所有解的算法。如果一個(gè)候選解最后被發(fā)現(xiàn)并不是可行解，回溯算法會(huì)舍棄它，并在前面的一些步驟做出一些修改，并重新嘗試找到可行解。究其本質(zhì)，其實(shí)就是枚舉。
動(dòng)態(tài)規(guī)劃(Dynamic Programming)雖然動(dòng)態(tài)規(guī)劃的最終版本 (降維再去維) 大都不是遞歸，但解題的過程還是離開不遞歸的。新手可能會(huì)覺得動(dòng)態(tài)規(guī)劃思想接受起來(lái)比較難，確實(shí)，動(dòng)態(tài)規(guī)劃求解問題的過程不太符合人類常規(guī)的思維方式，我們需要切換成機(jī)器思維。使用動(dòng)態(tài)規(guī)劃思想解題，首先要明確動(dòng)態(tài)規(guī)劃的三要素。動(dòng)態(tài)規(guī)劃三要素：
查找算法順序查找就是一個(gè)一個(gè)依次查找。 二分查找二分查找又叫折半查找，從有序列表的初始候選區(qū)li[0:n]開始，通過對(duì)待查找的值與候選區(qū)中間值的比較，可以使候選區(qū)減少一半。如果待查值小于候選區(qū)中間值，則只需比較中間值左邊的元素，減半查找范圍。依次類推依次減半。
 JAVA代碼如下： /** * 執(zhí)行遞歸二分查找，返回第一次出現(xiàn)該值的位置 * * @param array 已排序的數(shù)組 * @param start 開始位置，如：0 * @param end 結(jié)束位置，如：array.length-1 * @param findValue 需要找的值 * @return 值在數(shù)組中的位置，從0開始。找不到返回-1 */public static int searchRecursive(int[] array, int start, int end, int findValue) { // 如果數(shù)組為空，直接返回-1，即查找失敗 if (array == null) { return -1; } if (start <= end) { // 中間位置 int middle = (start + end) / 1; // 中值 int middleValue = array[middle]; if (findValue == middleValue) { // 等于中值直接返回 return middle; } else if (findValue < middleValue) { // 小于中值時(shí)在中值前面找 return searchRecursive(array, start, middle - 1, findValue); } else { // 大于中值在中值后面找 return searchRecursive(array, middle + 1, end, findValue); } } else { // 返回-1，即查找失敗 return -1; }}/** * 循環(huán)二分查找，返回第一次出現(xiàn)該值的位置 * * @param array 已排序的數(shù)組 * @param findValue 需要找的值 * @return 值在數(shù)組中的位置，從0開始。找不到返回-1 */public static int searchLoop(int[] array, int findValue) { // 如果數(shù)組為空，直接返回-1，即查找失敗 if (array == null) { return -1; } // 起始位置 int start = 0; // 結(jié)束位置 int end = array.length - 1; while (start <= end) { // 中間位置 int middle = (start + end) / 2; // 中值 int middleValue = array[middle]; if (findValue == middleValue) { // 等于中值直接返回 return middle; } else if (findValue < middleValue) { // 小于中值時(shí)在中值前面找 end = middle - 1; } else { // 大于中值在中值后面找 start = middle + 1; } } // 返回-1，即查找失敗 return -1;}插值查找插值查找算法類似于二分查找，不同的是插值查找每次從自適應(yīng)mid處開始查找。將折半查找中的求mid索引的公式，low表示左邊索引left，high表示右邊索引right，key就是前面我們講的findVal。  注意事項(xiàng)
斐波那契查找黃金分割點(diǎn)是指把一條線段分割為兩部分，使其中一部分與全長(zhǎng)之比等于另一部分與這部分之比。取其前三位數(shù)字的近似值是0.618。由于按此比例設(shè)計(jì)的造型十分美麗，因此稱為黃金分割，也稱為中外比。這是一個(gè)神奇的數(shù)字，會(huì)帶來(lái)意向不大的效果。斐波那契數(shù)列{1, 1,2, 3, 5, 8, 13,21, 34, 55 }發(fā)現(xiàn)斐波那契數(shù)列的兩個(gè)相鄰數(shù)的比例，無(wú)限接近黃金分割值0.618。 斐波那契查找原理與前兩種相似，僅僅改變了中間結(jié)點(diǎn)(mid)的位置，mid不再是中間或插值得到，而是位于黃金分割點(diǎn)附近，即mid=low+F(k-1)-1(F代表斐波那契數(shù)列)，如下圖所示：  JAVA代碼如下： /** * 因?yàn)楹竺嫖覀僲id=low+F(k-1)-1，需要使用到斐波那契數(shù)列，因此我們需要先獲取到一個(gè)斐波那契數(shù)列 * 非遞歸方法得到一個(gè)斐波那契數(shù)列 * * @return */private static int[] getFibonacci() { int[] fibonacci = new int[20]; fibonacci[0] = 1; fibonacci[1] = 1; for (int i = 2; i < fibonacci.length; i++) { fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]; } return fibonacci;}/** * 編寫斐波那契查找算法 * 使用非遞歸的方式編寫算法 * * @param arr 數(shù)組 * @param findValue 我們需要查找的關(guān)鍵碼(值) * @return 返回對(duì)應(yīng)的下標(biāo)，如果沒有-1 */public static int fibonacciSearch(int[] arr, int findValue) { int low = 0; int high = arr.length - 1; int k = 0;// 表示斐波那契分割數(shù)值的下標(biāo) int mid = 0;// 存放mid值 int[] fibonacci = getFibonacci();// 獲取到斐波那契數(shù)列 // 獲取到斐波那契分割數(shù)值的下標(biāo) while (high > fibonacci[k] - 1) { k++; } // 因?yàn)?fibonacci[k] 值可能大于 arr 的 長(zhǎng)度，因此我們需要使用Arrays類，構(gòu)造一個(gè)新的數(shù)組 int[] temp = Arrays.copyOf(arr, fibonacci[k]); // 實(shí)際上需求使用arr數(shù)組最后的數(shù)填充 temp for (int i = high + 1; i < temp.length; i++) { temp[i] = arr[high]; } // 使用while來(lái)循環(huán)處理，找到我們的數(shù) findValue while (low <= high) { mid = low + fibonacci[k] - 1; if (findValue < temp[mid]) { high = mid - 1; k--; } else if (findValue > temp[mid]) { low = mid + 1; k++; } else { return Math.min(mid, high); } } return -1;}搜素算法深度優(yōu)先搜索(DFS)深度優(yōu)先搜索（Depth-First Search / DFS）是一種優(yōu)先遍歷子節(jié)點(diǎn)而不是回溯的算法。  DFS解決的是連通性的問題。即給定兩個(gè)點(diǎn)，一個(gè)是起始點(diǎn)，一個(gè)是終點(diǎn)，判斷是不是有一條路徑能從起點(diǎn)連接到終點(diǎn)。起點(diǎn)和終點(diǎn)，也可以指的是某種起始狀態(tài)和最終的狀態(tài)。問題的要求并不在乎路徑是長(zhǎng)還是短，只在乎有還是沒有。 代碼案例 廣度優(yōu)先搜索(BFS)廣度優(yōu)先搜索（Breadth-First Search / BFS）是優(yōu)先遍歷鄰居節(jié)點(diǎn)而不是子節(jié)點(diǎn)的圖遍歷算法。  BFS一般用來(lái)解決最短路徑的問題。和深度優(yōu)先搜索不同，廣度優(yōu)先的搜索是從起始點(diǎn)出發(fā)，一層一層地進(jìn)行，每層當(dāng)中的點(diǎn)距離起始點(diǎn)的步數(shù)都是相同的，當(dāng)找到了目的地之后就可以立即結(jié)束。廣度優(yōu)先的搜索可以同時(shí)從起始點(diǎn)和終點(diǎn)開始進(jìn)行，稱之為雙端 BFS。這種算法往往可以大大地提高搜索的效率。 代碼案例 /** * Breadth-First Search(BFS) * <p> * 從根節(jié)點(diǎn)出發(fā)，在橫向遍歷二叉樹層段節(jié)點(diǎn)的基礎(chǔ)上縱向遍歷二叉樹的層次。 * <p> * 數(shù)據(jù)結(jié)構(gòu)：隊(duì)列 * 父節(jié)點(diǎn)入隊(duì)，父節(jié)點(diǎn)出隊(duì)列，先左子節(jié)點(diǎn)入隊(duì)，后右子節(jié)點(diǎn)入隊(duì)。遞歸遍歷全部節(jié)點(diǎn)即可 * */public class BreadthFirstSearch { /** * 樹節(jié)點(diǎn) * * @param <V> */ @Data @NoArgsConstructor @AllArgsConstructor public static class TreeNode<V> { private V value; private List<TreeNode<V>> childList; } /** * 模型： * .......A * ...../ \ * ....B C * .../ \ / \ * ..D E F G * ./ \ / \ * H I J K */ public static void main(String[] args) { TreeNode<String> treeNodeA = new TreeNode<>('A', new ArrayList<>()); TreeNode<String> treeNodeB = new TreeNode<>('B', new ArrayList<>()); TreeNode<String> treeNodeC = new TreeNode<>('C', new ArrayList<>()); TreeNode<String> treeNodeD = new TreeNode<>('D', new ArrayList<>()); TreeNode<String> treeNodeE = new TreeNode<>('E', new ArrayList<>()); TreeNode<String> treeNodeF = new TreeNode<>('F', new ArrayList<>()); TreeNode<String> treeNodeG = new TreeNode<>('G', new ArrayList<>()); TreeNode<String> treeNodeH = new TreeNode<>('H', new ArrayList<>()); TreeNode<String> treeNodeI = new TreeNode<>('I', new ArrayList<>()); TreeNode<String> treeNodeJ = new TreeNode<>('J', new ArrayList<>()); TreeNode<String> treeNodeK = new TreeNode<>('K', new ArrayList<>()); // A->B,C treeNodeA.getChildList().add(treeNodeB); treeNodeA.getChildList().add(treeNodeC); // B->D,E treeNodeB.getChildList().add(treeNodeD); treeNodeB.getChildList().add(treeNodeE); // C->F,G treeNodeC.getChildList().add(treeNodeF); treeNodeC.getChildList().add(treeNodeG); // D->H,I treeNodeD.getChildList().add(treeNodeH); treeNodeD.getChildList().add(treeNodeI); // G->J,K treeNodeG.getChildList().add(treeNodeJ); treeNodeG.getChildList().add(treeNodeK); System.out.println('遞歸方式'); bfsRecursive(Arrays.asList(treeNodeA), 0); System.out.println(); System.out.println('非遞歸方式'); bfsNotRecursive(treeNodeA); } /** * 遞歸遍歷 * * @param children * @param depth * @param <V> */ public static <V> void bfsRecursive(List<TreeNode<V>> children, int depth) { List<TreeNode<V>> thisChildren, allChildren = new ArrayList<>(); for (TreeNode<V> child : children) { // 打印節(jié)點(diǎn)值以及深度 System.out.print('-->[' + child.getValue().toString() + ',' + depth + ']'); thisChildren = child.getChildList(); if (thisChildren != null && thisChildren.size() > 0) { allChildren.addAll(thisChildren); } } if (allChildren.size() > 0) { bfsRecursive(allChildren, depth + 1); } } /** * 非遞歸遍歷 * * @param tree * @param <V> */ public static <V> void bfsNotRecursive(TreeNode<V> tree) { if (tree != null) { // 跟上面一樣，使用 Map 也只是為了保存樹的深度，沒這個(gè)需要可以不用 Map Queue<Map<TreeNode<V>, Integer>> queue = new ArrayDeque<>(); Map<TreeNode<V>, Integer> root = new HashMap<>(); root.put(tree, 0); queue.offer(root); while (!queue.isEmpty()) { Map<TreeNode<V>, Integer> itemMap = queue.poll(); TreeNode<V> node = itemMap.keySet().iterator().next(); int depth = itemMap.get(node); //打印節(jié)點(diǎn)值以及深度 System.out.print('-->[' + node.getValue().toString() + ',' + depth + ']'); if (node.getChildList() != null && !node.getChildList().isEmpty()) { for (TreeNode<V> child : node.getChildList()) { Map<TreeNode<V>, Integer> map = new HashMap<>(); map.put(child, depth + 1); queue.offer(map); } } } } }}迪杰斯特拉算法(Dijkstra)迪杰斯特拉(Dijkstra)算法 是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。它的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止。 基本思想 通過Dijkstra計(jì)算圖G中的最短路徑時(shí)，需要指定起點(diǎn)s(即從頂點(diǎn)s開始計(jì)算)。 此外，引進(jìn)兩個(gè)集合S和U。S的作用是記錄已求出最短路徑的頂點(diǎn)(以及相應(yīng)的最短路徑長(zhǎng)度)，而U則是記錄還未求出最短路徑的頂點(diǎn)(以及該頂點(diǎn)到起點(diǎn)s的距離)。 初始時(shí)，S中只有起點(diǎn)s；U中是除s之外的頂點(diǎn)，并且U中頂點(diǎn)的路徑是'起點(diǎn)s到該頂點(diǎn)的路徑'。然后，從U中找出路徑最短的頂點(diǎn)，并將其加入到S中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑。 然后，再?gòu)腢中找出路徑最短的頂點(diǎn)，并將其加入到S中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑。 ... 重復(fù)該操作，直到遍歷完所有頂點(diǎn)。 操作步驟
迪杰斯特拉算法圖解  以上圖G4為例，來(lái)對(duì)迪杰斯特拉進(jìn)行算法演示(以第4個(gè)頂點(diǎn)D為起點(diǎn))：  代碼案例 排序算法十種常見排序算法可以分為兩大類：
 冒泡排序（Bubble Sort）循環(huán)遍歷多次每次從前往后把大元素往后調(diào)，每次確定一個(gè)最大(最小)元素，多次后達(dá)到排序序列。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。  算法步驟
代碼實(shí)現(xiàn) /** * 冒泡排序 * 描述：每輪連續(xù)比較相鄰的兩個(gè)數(shù)，前數(shù)大于后數(shù)，則進(jìn)行替換。每輪完成后，本輪最大值已被移至最后 * * @param arr 待排序數(shù)組 */public static int[] bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // 每次比較2個(gè)相鄰的數(shù),前一個(gè)小于后一個(gè) if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr;}以下是冒泡排序算法復(fù)雜度:
冒泡排序是最容易實(shí)現(xiàn)的排序, 最壞的情況是每次都需要交換, 共需遍歷并交換將近n2/2次, 時(shí)間復(fù)雜度為O(n2). 最佳的情況是內(nèi)循環(huán)遍歷一次后發(fā)現(xiàn)排序是對(duì)的, 因此退出循環(huán), 時(shí)間復(fù)雜度為O(n)。平均來(lái)講, 時(shí)間復(fù)雜度為O(n2). 由于冒泡排序中只有緩存的temp變量需要內(nèi)存空間, 因此空間復(fù)雜度為常量O(1)。 Tips: 由于冒泡排序只在相鄰元素大小不符合要求時(shí)才調(diào)換他們的位置, 它并不改變相同元素之間的相對(duì)順序, 因此它是穩(wěn)定的排序算法。 選擇排序（Selection Sort）選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。 算法描述 n個(gè)記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：
代碼實(shí)現(xiàn) 以下是選擇排序復(fù)雜度:
選擇排序的簡(jiǎn)單和直觀名副其實(shí)，這也造就了它”出了名的慢性子”，無(wú)論是哪種情況，哪怕原數(shù)組已排序完成，它也將花費(fèi)將近n2/2次遍歷來(lái)確認(rèn)一遍。即便是這樣，它的排序結(jié)果也還是不穩(wěn)定的。 唯一值得高興的是，它并不耗費(fèi)額外的內(nèi)存空間。 插入排序（Insertion Sort）插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序由于操作不盡相同，可分為 直接插入排序、折半插入排序(又稱二分插入排序)、鏈表插入排序、希爾排序 。 算法描述 一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
代碼實(shí)現(xiàn) /** * 直接插入排序 * 1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序 * 2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描 * 3. 如果該元素（已排序）大于新元素，將該元素移到下一位置 * 4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置 * 5. 將新元素插入到該位置后 * 6. 重復(fù)步驟2~5 * * @param arr 待排序數(shù)組 */ public static int[] insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { // 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描 int temp = arr[i]; for (int j = i; j >= 0; j--) { if (j > 0 && arr[j - 1] > temp) { // 如果該元素（已排序）大于取出的元素temp，將該元素移到下一位置 arr[j] = arr[j - 1]; } else { // 將新元素插入到該位置后 arr[j] = temp; break; } } } return arr; } /** * 折半插入排序 * 往前找合適的插入位置時(shí)采用二分查找的方式，即折半插入 * 交換次數(shù)較多的實(shí)現(xiàn) * * @param arr 待排序數(shù)組 */ public static int[] insertionBinarySort(int[] arr) { for (int i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { int tmp = arr[i]; // 記錄搜索范圍的左邊界,右邊界 int low = 0, high = i - 1; while (low <= high) { // 記錄中間位置Index int mid = (low + high) / 2; // 比較中間位置數(shù)據(jù)和i處數(shù)據(jù)大小，以縮小搜索范圍 if (arr[mid] < tmp) { // 左邊指針則一只中間位置+1 low = mid + 1; } else { // 右邊指針則一只中間位置-1 high = mid - 1; } } // 將low~i處數(shù)據(jù)整體向后移動(dòng)1位 for (int j = i; j > low; j--) { arr[j] = arr[j - 1]; } arr[low] = tmp; } } return arr; }插入排序復(fù)雜度：
Tips：由于直接插入排序每次只移動(dòng)一個(gè)元素的位， 并不會(huì)改變值相同的元素之間的排序， 因此它是一種穩(wěn)定排序。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 希爾排序（Shell Sort）1959年Shell發(fā)明，第一個(gè)突破O(n2)的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。 算法描述 先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：
代碼實(shí)現(xiàn) 以下是希爾排序復(fù)雜度:
Tips：希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。動(dòng)態(tài)定義間隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。 歸并排序（Merging Sort）簡(jiǎn)介 基本思想：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。 場(chǎng)景使用 應(yīng)用場(chǎng)景：內(nèi)存少的時(shí)候使用，可以進(jìn)行并行計(jì)算的時(shí)候使用。 步驟：
算法描述 a.遞歸法（假設(shè)序列共有n個(gè)元素） ①. 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成 floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素； ②. 將上述序列再次歸并，形成 floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素； ③. 重復(fù)步驟②，直到所有元素排序完畢。 b.迭代法 ①. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列 ②. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置 ③. 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置 ④. 重復(fù)步驟③直到某一指針到達(dá)序列尾 ⑤. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾 代碼實(shí)現(xiàn) /** * 歸并排序（遞歸） * ①. 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成 floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素； * ②. 將上述序列再次歸并，形成 floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素； * ③. 重復(fù)步驟②，直到所有元素排序完畢。 * * @param arr 待排序數(shù)組 */ public static int[] mergeSort(int[] arr) { return mergeSort(arr, 0, arr.length - 1); } private static int[] mergeSort(int[] arr, int low, int high) { int center = (high + low) / 2; if (low < high) { // 遞歸，直到low==high，也就是數(shù)組已不能再分了， mergeSort(arr, low, center); mergeSort(arr, center + 1, high); // 當(dāng)數(shù)組不能再分，開始?xì)w并排序 mergeSort(arr, low, center, high); } return arr; } private static void mergeSort(int[] a, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; // 把較小的數(shù)先移到新數(shù)組中 while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } // 把左邊剩余的數(shù)移入數(shù)組 while (i <= mid) { temp[k++] = a[i++]; } // 把右邊邊剩余的數(shù)移入數(shù)組 while (j <= high) { temp[k++] = a[j++]; } // 把新數(shù)組中的數(shù)覆蓋nums數(shù)組 for (int x = 0; x < temp.length; x++) { a[x + low] = temp[x]; } }以下是歸并排序算法復(fù)雜度:
從效率上看，歸并排序可算是排序算法中的”佼佼者”. 假設(shè)數(shù)組長(zhǎng)度為n，那么拆分?jǐn)?shù)組共需logn，, 又每步都是一個(gè)普通的合并子數(shù)組的過程， 時(shí)間復(fù)雜度為O(n)， 故其綜合時(shí)間復(fù)雜度為O(nlogn)。另一方面， 歸并排序多次遞歸過程中拆分的子數(shù)組需要保存在內(nèi)存空間， 其空間復(fù)雜度為O(n)。 Tips：和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是O(nlogn）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。 快速排序（Quick Sort）快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)，借用了分治的思想，由C. A. R. Hoare在1962年提出?；舅枷胧峭ㄟ^一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。 算法描述 快速排序使用分治法來(lái)把一個(gè)串（list）分為兩個(gè)子串（sub-lists）。具體算法描述如下：
代碼實(shí)現(xiàn) 以下是快速排序算法復(fù)雜度:
快速排序排序效率非常高。 雖然它運(yùn)行最糟糕時(shí)將達(dá)到O(n2)的時(shí)間復(fù)雜度, 但通常平均來(lái)看, 它的時(shí)間復(fù)雜為O(nlogn), 比同樣為O(nlogn)時(shí)間復(fù)雜度的歸并排序還要快. 快速排序似乎更偏愛亂序的數(shù)列, 越是亂序的數(shù)列, 它相比其他排序而言, 相對(duì)效率更高。 Tips: 同選擇排序相似, 快速排序每次交換的元素都有可能不是相鄰的, 因此它有可能打破原來(lái)值為相同的元素之間的順序. 因此, 快速排序并不穩(wěn)定。 基數(shù)排序（Radix Sort）基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。 算法描述
代碼實(shí)現(xiàn) /** * 基數(shù)排序（LSD 從低位開始） * 基數(shù)排序適用于： * (1)數(shù)據(jù)范圍較小，建議在小于1000 * (2)每個(gè)數(shù)值都要大于等于0 * <p> * ①. 取得數(shù)組中的最大數(shù)，并取得位數(shù)； * ②. arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組； * ③. 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）； * * @param arr 待排序數(shù)組 */public static int[] radixSort(int[] arr) { // 取得數(shù)組中的最大數(shù)，并取得位數(shù) int max = 0; for (int item : arr) { if (max < item) { max = item; } } int maxDigit = 1; while (max / 10 > 0) { maxDigit++; max = max / 10; } // 申請(qǐng)一個(gè)桶空間 int[][] buckets = new int[10][arr.length]; int base = 10; // 從低位到高位，對(duì)每一位遍歷，將所有元素分配到桶中 for (int i = 0; i < maxDigit; i++) { // 存儲(chǔ)各個(gè)桶中存儲(chǔ)元素的數(shù)量 int[] bktLen = new int[10]; // 分配：將所有元素分配到桶中 for (int value : arr) { int whichBucket = (value % base) / (base / 10); buckets[whichBucket][bktLen[whichBucket]] = value; bktLen[whichBucket]++; } // 收集：將不同桶里數(shù)據(jù)挨個(gè)撈出來(lái),為下一輪高位排序做準(zhǔn)備,由于靠近桶底的元素排名靠前,因此從桶底先撈 int k = 0; for (int b = 0; b < buckets.length; b++) { for (int p = 0; p < bktLen[b]; p++) { arr[k++] = buckets[b][p]; } } base *= 10; } return arr;}以下是基數(shù)排序算法復(fù)雜度，其中k為最大數(shù)的位數(shù)：
其中，d 為位數(shù)，r 為基數(shù)，n 為原數(shù)組個(gè)數(shù)。在基數(shù)排序中，因?yàn)闆]有比較操作，所以在復(fù)雜上，最好的情況與最壞的情況在時(shí)間上是一致的，均為 O(d*(n + r))。基數(shù)排序更適合用于對(duì)時(shí)間, 字符串等這些整體權(quán)值未知的數(shù)據(jù)進(jìn)行排序。 Tips: 基數(shù)排序不改變相同元素之間的相對(duì)順序，因此它是穩(wěn)定的排序算法。 堆排序（Heap Sort）對(duì)于堆排序，首先是建立在堆的基礎(chǔ)上，堆是一棵完全二叉樹，還要先認(rèn)識(shí)下大根堆和小根堆，完全二叉樹中所有節(jié)點(diǎn)均大于(或小于)它的孩子節(jié)點(diǎn)，所以這里就分為兩種情況：
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆排序的過程就是將待排序的序列構(gòu)造成一個(gè)堆，選出堆中最大的移走，再把剩余的元素調(diào)整成堆，找出最大的再移走，重復(fù)直至有序。 算法描述
動(dòng)圖演示 代碼實(shí)現(xiàn)
Tips: 由于堆排序中初始化堆的過程比較次數(shù)較多, 因此它不太適用于小序列. 同時(shí)由于多次任意下標(biāo)相互交換位置, 相同元素之間原本相對(duì)的順序被破壞了, 因此, 它是不穩(wěn)定的排序. 計(jì)數(shù)排序（Counting Sort）計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。 作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。 算法描述
動(dòng)圖演示 代碼實(shí)現(xiàn) /** * 計(jì)數(shù)排序算法 * * @param arr 待排序數(shù)組 */ public static int[] countingSort(int[] arr) { // 得到數(shù)列的最大值與最小值，并算出差值d int max = arr[0]; int min = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } if (arr[i] < min) { min = arr[i]; } } int d = max - min; // 創(chuàng)建統(tǒng)計(jì)數(shù)組并計(jì)算統(tǒng)計(jì)對(duì)應(yīng)元素個(gè)數(shù) int[] countArray = new int[d + 1]; for (int value : arr) { countArray[value - min]++; } // 統(tǒng)計(jì)數(shù)組變形，后面的元素等于前面的元素之和 int sum = 0; for (int i = 0; i < countArray.length; i++) { sum += countArray[i]; countArray[i] = sum; } // 倒序遍歷原始數(shù)組，從統(tǒng)計(jì)數(shù)組找到正確位置，輸出到結(jié)果數(shù)組 int[] sortedArray = new int[arr.length]; for (int i = arr.length - 1; i >= 0; i--) { sortedArray[countArray[arr[i] - min] - 1] = arr[i]; countArray[arr[i] - min]--; } return sortedArray; }算法分析 計(jì)數(shù)排序是一個(gè)穩(wěn)定的排序算法。當(dāng)輸入的元素是 n 個(gè) 0到 k 之間的整數(shù)時(shí)，時(shí)間復(fù)雜度是O(n+k)，空間復(fù)雜度也是O(n+k)，其排序速度快于任何比較排序算法。當(dāng)k不是很大并且序列比較集中時(shí)，計(jì)數(shù)排序是一個(gè)很有效的排序算法。 桶排序（Bucket Sort）桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排）。 算法描述
代碼實(shí)現(xiàn) 算法分析 桶排序最好情況下使用線性時(shí)間O(n)，桶排序的時(shí)間復(fù)雜度，取決與對(duì)各個(gè)桶之間數(shù)據(jù)進(jìn)行排序的時(shí)間復(fù)雜度，因?yàn)槠渌糠值臅r(shí)間復(fù)雜度都為O(n)。很顯然，桶劃分的越小，各個(gè)桶之間的數(shù)據(jù)越少，排序所用的時(shí)間也會(huì)越少。但相應(yīng)的空間消耗就會(huì)增大。 |
|
|
