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

2019-11-19 16:49:26

字體：大中小

供稿：網(wǎng)友

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

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

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

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

示例如下：

算法思想如下：

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

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

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

我們通過(guò)js實(shí)現(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){//分成兩個(gè)之序列        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>

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