交換ソート---クイックソートアルゴリズム(Javascript版)

急速な並べ替えは発泡体秩序の改善である.順序付けによって順序付けされるデータは独立した2つの部分に分割され、そのうちの一部のすべてのデータは他の部分のすべてのデータよりも小さい.その後、この方法でこれらの2つの部分のデータをそれぞれ高速に並べ替え、順序付けプロセス全体が再帰的に行われ、最終的にはデータ全体が秩序化されたシーケンスになる.
並べ替えられる配列がA[0]…….A[N-1]であると仮定して、まず任意のデータ(行列の最初の数を選択します)を基準データとして選択し、それより小さい数をすべて前に置いて、それより大きい数を全部その後ろに置いてください.このプロセスをクイックソートといいます.注目すべきは、高速ソートは安定したソートアルゴリズムではなく、つまり、複数の同じ値の相対位置はアルゴリズム終了時に変動するかもしれない.高速並べ替えのアルゴリズムは、1)二つの変数low、highを設定し、並べ替え開始時:low=0、high=N-1;2)最初の配列要素を基準データとしてベース、すなわちベース=A[0];3)highから前へ検索を開始し、後から前へ検索を開始し、最初のbaseより小さい値A[high]を見つけ、A[high]とA[low]を交換する.4)lowから後方検索を開始し、つまり前から後ろへ検索し(low+)、最初のbaseより大きいA[low]を見つけ、A[low]とA[high]を交換する.5)第3、4ステップを繰り返し、low＝highになるまで;
 
以下のコードはnodejsで実行します.

function partition(elements, low, high){

  //              

  var base=elements[low];

  while(low < high){

    //      ，             ，     

    while(low < high && elements[high] >= base) high--;

    var swap1=elements[low];elements[low]=elements[high];elements[high]=swap1;



    //      ，             ，     

    while(low < high && elements[low] <= base) low++;

    var swap2=elements[low];elements[low]=elements[high];elements[high]=swap2;

    

  }



  //         ，         

  return low;

}



function sort(elements, low, high){

  if(low<high){

    //       ，           ，           ，           

    var partitionPos=partition(elements, low, high);

    //          

    sort(elements, 0, partitionPos-1);

    //          

    sort(elements, partitionPos+1, high);

  }

}



var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];

console.log('before: ' + elements);

sort(elements, 0, elements.length-1);

console.log(' after: ' + elements);

 
効率:
時間複雑度:一番いいのはO(nlog 2 n)で、最悪はO(n^2)で、平均はO(nlog 2 n)です.
空間複雑度:O(nlog 2 n).
安定性:不安定です.