JavaScript實作快速排序演算法的程式碼圖文分析-js教程-PHP中文網

JavaScript實作快速排序演算法的程式碼圖文分析

黄舟

發布： 2017-04-15 09:31:27

原創

1602 人瀏覽過

這篇文章主要介紹了基於JavaScript實現的快速排序演算法,分析了快速排序的原理並結合實例形式給出了javascript快速排序的操作步驟與相關實現技巧,需要的朋友可以參考下

本文實例講述了基於JavaScript實作的快速排序演算法。分享給大家供大家參考，具體如下：

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

透過分析可以得出，冒泡排序的時間複雜度為O（n2）。

快速排序是對冒泡排序的一種改進，它是處理大資料集最快的排序之一，透過遞歸的方式將資料依序分解為包含較小元素和較大元素的不同子序列，並不斷重複該過程直到所有資料都是有序的。 這個演算法首先要選擇一個基準值，圍繞著基準值進行。

範例如下：

演算法想法如下：

選擇一個基準元素，將列表分成兩個子序列；

對清單重新排序，將所有小於基準元素的元素放前面，大的放後面；

分別對較小元素的子序列和較大元素的子序列重複上面兩個步驟。

我們透過js實作程式碼如下：

<!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];//选择基准元素
    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){//显示数组
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+&#39; &#39;);
    }
    document.write(&#39;<br>&#39;);
  }
  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>

登入後複製

就平均時間而言，快速排序是目前被認為最好的一種內部排序方法。快速排序非常適用於大型資料集合，在處理小資料集時效能反而會下降。其時間複雜度為O（nlog2n）