基于JavaScript實現(xiàn)的快速排序算法分析

發(fā)布時間：2020-10-11 20:06:38 來源：腳本之家閱讀：126 作者：布瑞澤的童話欄目：web開發(fā)

本文實例講述了基于JavaScript實現(xiàn)的快速排序算法。分享給大家供大家參考，具體如下：

首先要介紹一下冒泡排序，冒泡排序的過程很簡單，首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序，則將兩個關(guān)鍵字交換，然后比較第二個和第三個，直到最后一個比較完成。這是第一趟冒泡，其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個位置上了。然后對序列前n-1個元素進行第二次冒泡，將倒數(shù)第二個選出。以此類推直到所有被選出，冒泡結(jié)束。

通過分析可以得出，冒泡排序的時間復(fù)雜度為O（n2）。

快速排序是對冒泡排序的一種改進，它是處理大數(shù)據(jù)集最快的排序之一，通過遞歸的方式將數(shù)據(jù)依次分解為包含較小元素和較大元素的不同子序列，不斷重復(fù)該過程直到所有數(shù)據(jù)都是有序的。這個算法首先要選擇一個基準(zhǔn)值，圍繞基準(zhǔn)值進行。

示例如下：

基于JavaScript實現(xiàn)的快速排序算法分析

算法思想如下：

選擇一個基準(zhǔn)元素，將列表分為兩個子序列；

對列表重新排序，將所有小于基準(zhǔn)元素的元素放前面，大的放后面；

分別對較小元素的子序列和較大元素的子序列重復(fù)上面兩個步驟。

我們通過js實現(xiàn)代碼如下：

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>JavaScript快速排序</title>
</head>
<body>
<script type="text/javascript">
  function qSort(nums) {//快速排序
    if(nums.length==0){
      return [];
    }
    var lesser=[];
    var greater=[];
    var pivot=nums[0];//選擇基準(zhǔn)元素
    for(var i=1;i<nums.length;i++){
      if(nums[i]<pivot){//分成兩個之序列
        lesser.push(nums[i]);
      }else{
        greater.push(nums[i]);
      }
    }
    return qSort(lesser).concat(pivot,qSort(greater));//遞歸
  }
  function show(nums){//顯示數(shù)組
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+' ');
    }
    document.write('<br>');
  }
  var nums=[68,80,12,80,95,70,79,27,88,93];
  show(nums);//newNums
  var newNums=qSort(nums);//希爾排序
  show(newNums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>

就平均時間而言，快速排序是目前被認為最好的一種內(nèi)部排序方法。快速排序非常適用于大型數(shù)據(jù)集合，在處理小數(shù)據(jù)集時性能反而會下降。其時間復(fù)雜度為O（nlog2n）

基于JavaScript實現(xiàn)的快速排序算法分析

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

向AI問一下細節(jié)

基于JavaScript實現(xiàn)的快速排序算法分析

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽