完美世界前传下载,《完美世界》txt全集,重生之毒妃梅果小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

你可能不知道的快速排序：三路快排

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

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

在數(shù)據(jù)集之中，選擇一個元素作為"基準"（pivot）。
所有小于"基準"的元素，都移到"基準"的左邊；所有大于"基準"的元素，都移到"基準"的右邊。
對"基準"左邊和右邊的兩個子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個元素為止。

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

步驟
找到該數(shù)組的基準點(中間數(shù))，并創(chuàng)建兩個空數(shù)組left和right；
遍歷數(shù)組，拿出數(shù)組中的每個數(shù)和基準點進行比較，如果比基準點小就放到left數(shù)組中，如果比基準點大就放到right數(shù)組中；
對數(shù)組left和right進行遞歸調(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   
  
  
  
        if (arr[i] < base) {   
  
  
            left.push(arr[i])   
  
  
          }else {   
  
  
            right.push(arr[i])   
  
  
          }   
  
  
        }   
  
  
     
  
  
        return quickSort(left).concat([base], quickSort(right));   
  
  
      }

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

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

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

隨機選取基準值base(支點隨機選取),參考[快速排序算法的優(yōu)化思路總結(jié)][Link 1]
配合著使用插入排序(當問題規(guī)模較小時，近乎有序時，插入排序表現(xiàn)的很好)
當大量數(shù)據(jù)，且重復(fù)數(shù)多時，用三路快排

 
 
 
   
  
  
     
  
  
       
  
  
       
  
  
        
  
  
         
  
  
         
  
  
         
  
  
       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")   
  
  
         
  
  
         
  
  
       console.time("test1")   
  
  
       function qSort3(arr) {       //三路快排   
  
  
        if(arr.length == 0) {   
  
  
         return [];   
  
  
        }   
  
  
        var left = [];   
  
  
        var center = [];   
  
  
        var right = [];   
  
  
        var pivot = arr[0];    //偷懶，直接取第一個,實際取值情況 參考[快速排序算法的優(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")

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

文章名稱：你可能不知道的快速排序：三路快排
本文路徑：http://m.fisionsoft.com.cn/article/cdcjhjh.html

新聞中心

其他資訊