クイックソートアルゴリズムのJavaScript実装のコードグラフィック解析-jsチュートリアル-php.cn

クイックソートアルゴリズムのJavaScript実装のコードグラフィック解析

黄舟

リリース： 2017-04-15 09:31:27

オリジナル

1602 人が閲覧しました

この記事では、主に JavaScript に基づくクイックソートアルゴリズムを紹介し、クイックソートの原理を分析し、JavaScript クイックソートの操作手順と関連実装テクニックを例の形で提供します。必要な友達はこの記事を参照してください。

この例では、JavaScript に基づいたクイック並べ替えアルゴリズムについて説明します。詳細は以下の通りです:

まず、

バブルソートのプロセスは非常に簡単ですまず、最初のレコードのキーワードを結合します。 2 番目のレコードのキーワードとの比較が行われ、順序が逆の場合は 2 つのキーが交換され、最後の比較が完了するまで 2 番目と 3 番目のキーが比較されます。これが最初のバブリングであり、その結果、最大のキーワードを持つレコードが最後の位置に配置されます。次に、シーケンスの最初の n-1 個の要素を 2 度目にバブルし、最後から 2 番目の要素を選択します。すべてが選択されて泡立ちが終わるまで、同様に続きます。分析により、バブルソートの時間計算量はO(n2)

であると結論付けることができます。

クイックソートはバブルソートを改良したもので、大規模なデータセット

を処理するための最も高速なソート方法の1つであり、異なるサブシーケンスの

再帰を通じてデータを順番に小さな要素と大きな要素に分割します。すべてのデータが整うまでこのプロセスが繰り返されます。このアルゴリズムは、まずベースライン値を選択し、ベースライン値を中心に処理を進める必要があります。 例は次のとおりです。

アルゴリズムのアイデアは次のとおりです:

ベンチマーク要素を選択し、リストを 2 つのサブシーケンスに分割します

リストを並べ替えて、すべての要素をベンチマーク要素を前に置き、大きい方を後ろに置きます

小さい要素のサブシーケンスと大きい要素のサブシーケンスに対してそれぞれ上記の 2 つの手順を繰り返します。

次のように

を通じてコードを実装します:

<!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)

以上がクイックソートアルゴリズムのJavaScript実装のコードグラフィック解析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。