クイックソートjavascript実現

2240 ワード

JavaScript クイックソート

(最近先端の技術を勉強しています.ちょうどチャンスがあれば、javascriptを試してみて、簡単なアルゴリズムを実現します.)並べ替え思想:
並べ替えによって、並べ替えられたレコードは二つの部分に分けられます.その中の一部のキーワードは他の部分のキーワードより小さいです.この2つの部分は、順序が整うまで、それぞれ並べ替えられます.
型配列を例にとって、高速な順序付けの方法:
並べ替え待ちシーケンスはR[low...high]であり、一つの基準を取る.一般的にR[low]である.
i=low、j=high-1を設定します.
①j==iまたはR[j]＜R[low]までj[j]とR[i]を交換②iから後ろへ検索し、j<=iまたはR[i]>R[low]までR[i]とR[j]を交換して①、②ステップを繰り返し、j<=iまで並べ替えを完了すると、iは最終基準に配置された位置である.
最高の場合:1つの順序は記録を約n回比較する必要があり、全体の時間複雑度は実行分割の回数による.理想的には、区分毎にシーケンスを2つの等長部分に分けると、時間複雑度はO(nlogn)である.最悪の場合は、区分毎にシーケンスを一部に分け、時間複雑度はO(n^2)となります.
平均時間の複雑度はO(nlogn)です.

<html>
  <head>
    <title>QuikSort</title>

    <script type="text/javascript">
    function quikSort(){
       var dataArr =new Array(34,23,67,3,5,56,35,343,34,54,32,89);
       var low = 0;
       var high = dataArr.length-1;
       alert('    ：'+dataArr);
       quik(dataArr,low,high);
       alert('    ：'+dataArr);
       
    }
    //      
     function quik(dataArray,left,right){
      if(dataArray.length>0){
      if(left<right){
       var middleIndex = getMiddle(dataArray,left,right);
       quik(dataArray,left,middleIndex-1);
       quik(dataArray,middleIndex+1,right);
       }
      }
     }
    
    //        
    function getMiddle(dataArr,low,high){
      var tmp = dataArr[low];
      while(low<high){ 
      while(low<high&&dataArr[high]>=tmp){
            high = high-1;
         }
        dataArr[low] = dataArr[high];
       
       while(low<high&&dataArr[low]<=tmp){
            low = low+1;
         }
        dataArr[high] = dataArr[low];
        
       }
       dataArr[low] = tmp;    
       return(low);   
    }
    </script>

  </head>
  <body>
  <button id="quikSort" onClick = "quikSort()">quikSort</button>
  <div id="originalData"></div>
    
  </body>
</html>

オリジナルjavascriptは、指定された要素の下のすべての後代元素コードのインスタンスを取得することを実現する.