溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“如何使用快速排序”，在日常操作中，相信很多人在如何使用快速排序問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何使用快速排序”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
快速排序
快速排序是什么 快速排序是圖靈獎得主C. A. R. Hoare（1934--）于1960時提出來的。
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。整個排序過程只需要三步：
在數據集之中，選擇一個元素作為"基準"（pivot）。
所有小于"基準"的元素，都移到"基準"的左邊；所有大于"基準"的元素，都移到"基準"的右邊。
對"基準"左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。
引自wikipedia 快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n)算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。
步驟
找到該數組的基準點(中間數)，并創建兩個空數組left和right；
遍歷數組，拿出數組中的每個數和基準點進行比較，如果比基準點小就放到left數組中，如果比基準點大就放到right數組中；
對數組left和right進行遞歸調用。
方法一
function quickSort(arr) { if (arr.length<=1) {return arr;} var left = [], right = [], baseDot =Math.round(arr.length/2), base =arr.splice(baseDot, 1)[0]; for (var i =0; i <arr.length; i++) { if (arr[i] < base) { left.push(arr[i]) }else { right.push(arr[i]) } } return quickSort(left).concat([base], quickSort(right)); }實現一個quickSort的封裝，并且定義left和right，找到數組的基準點baseDot和對應的基數base，然后遍歷數組的每一項和base進行對比，最后遞歸調用，給出一個跳出條件if (arr.length <= 1) {return arr;}
方法二
function quickSort(array, left, right) { var length =array.length; left =typeof left ==='number'? left :0, right =typeof right ==='number'? right : length-1; if (left < right) { var index = left -1; for (var i = left; i <= right; i++) { if (array[i] <= array[right]) { index++; var temp = array[index]; array[index] = array[i]; array[i] = temp; } } quickSort(array, left, index -1); quickSort(array, index +1, right); } return array; }快速排序的基本思想就是分治法
引自wikipedia 在計算機科學中，分治法是建基于多項分支遞歸的一種很重要的算法范式。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。
快速排序的改進方法：三路快排
定義
三路快速排序是快速排序的的一個優化版本， 將數組分成三段， 即小于基準元素、 等于 基準元素和大于基準元素， 這樣可以比較高效的處理數組中存在相同元素的情況,其它特征與快速排序基本相同。
我這里簡單概括一下思路，有興趣的同學可到上面的鏈接上閱讀：[快速排序及優化(Java實現)][Java]
隨機選取基準值base(支點隨機選取),參考[快速排序算法的優化思路總結][Link 1]
配合著使用插入排序(當問題規模較小時，近乎有序時，插入排序表現的很好)
當大量數據，且重復數多時，用三路快排
<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title></title> <script type="text/javascript"> console.time("test0") function qSort(arr) { if(arr.length == 0) { return []; } var left = []; var right = []; var pivot = arr[0]; for(var i = 1; i < arr.length; i++) { // 注意這里的起始值，因為有一個作為flag了 if(arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return [...qSort(left), pivot, ...qSort(right)]; } console.log(qSort([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0])); console.timeEnd("test0") </script> <script type="text/javascript"> console.time("test1") function qSort3(arr) { //三路快排 if(arr.length == 0) { return []; } var left = []; var center = []; var right = []; var pivot = arr[0]; //偷懶，直接取第一個,實際取值情況 參考[快速排序算法的優化思路總結] for(var i = 0; i < arr.length; i++) { if(arr[i] < pivot) { left.push(arr[i]); } else if(arr[i] == pivot) { center.push(arr[i]); } else { right.push(arr[i]); } } return [...qSort3(left), ...center, ...qSort3(right)]; } console.log(qSort3([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0])) console.timeEnd("test1") </script> </head> <body> </body> </html>
可以看到對有重復數據的數據優化還是很可觀的。
到此，關于“如何使用快速排序”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
