溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

如何使用快速排序

發(fā)布時(shí)間：2021-10-26 15:28:03 來源：億速云 閱讀：120 作者：iii 欄目：web開發(fā)

這篇文章主要介紹“如何使用快速排序”，在日常操作中，相信很多人在如何使用快速排序問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”如何使用快速排序”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

 快速排序
快速排序是什么 快速排序是圖靈獎(jiǎng)得主C. A. R. Hoare（1934--）于1960時(shí)提出來的。

如何使用快速排序

快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。整個(gè)排序過程只需要三步：

  • 在數(shù)據(jù)集之中，選擇一個(gè)元素作為"基準(zhǔn)"（pivot）。

  • 所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。

  • 對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。

引自wikipedia 快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序n個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他Ο(n log n)算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。

步驟
找到該數(shù)組的基準(zhǔn)點(diǎn)(中間數(shù))，并創(chuàng)建兩個(gè)空數(shù)組left和right；
遍歷數(shù)組，拿出數(shù)組中的每個(gè)數(shù)和基準(zhǔn)點(diǎn)進(jìn)行比較，如果比基準(zhǔn)點(diǎn)小就放到left數(shù)組中，如果比基準(zhǔn)點(diǎn)大就放到right數(shù)組中；
對(duì)數(shù)組left和right進(jìn)行遞歸調(diào)用。
方法一

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));     }

實(shí)現(xiàn)一個(gè)quickSort的封裝，并且定義left和right，找到數(shù)組的基準(zhǔn)點(diǎn)baseDot和對(duì)應(yīng)的基數(shù)base，然后遍歷數(shù)組的每一項(xiàng)和base進(jìn)行對(duì)比，最后遞歸調(diào)用，給出一個(gè)跳出條件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 在計(jì)算機(jī)科學(xué)中，分治法是建基于多項(xiàng)分支遞歸的一種很重要的算法范式。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。

快速排序的改進(jìn)方法：三路快排
定義
三路快速排序是快速排序的的一個(gè)優(yōu)化版本， 將數(shù)組分成三段， 即小于基準(zhǔn)元素、 等于 基準(zhǔn)元素和大于基準(zhǔn)元素， 這樣可以比較高效的處理數(shù)組中存在相同元素的情況,其它特征與快速排序基本相同。

我這里簡(jiǎn)單概括一下思路，有興趣的同學(xué)可到上面的鏈接上閱讀：[快速排序及優(yōu)化(Java實(shí)現(xiàn))][Java]

  • 隨機(jī)選取基準(zhǔn)值base(支點(diǎn)隨機(jī)選取),參考[快速排序算法的優(yōu)化思路總結(jié)][Link 1]

  • 配合著使用插入排序(當(dāng)問題規(guī)模較小時(shí)，近乎有序時(shí)，插入排序表現(xiàn)的很好)

  • 當(dāng)大量數(shù)據(jù)，且重復(fù)數(shù)多時(shí)，用三路快排

<!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++) { // 注意這里的起始值，因?yàn)橛幸粋€(gè)作為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];    //偷懶，直接取第一個(gè),實(shí)際取值情況 參考[快速排序算法的優(yōu)化思路總結(jié)]       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>

如何使用快速排序

如何使用快速排序

如何使用快速排序

可以看到對(duì)有重復(fù)數(shù)據(jù)的數(shù)據(jù)優(yōu)化還是很可觀的。

到此，關(guān)于“如何使用快速排序”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手