クイックソートはよく使われるソートアルゴリズムの一つで、その時間計算量は O(nlogn) です。ほとんどの場合、一般的なソートアルゴリズムよりも高速であるため広く利用されており、そこで、自分で実装してみることにしました。

原理#

クイックソートは分割統治法の原理を利用しています。   配列からランダムに1つの数字を選び、その配列を2つの部分に分割します。選んだ数字をピボット（基準数）として、ピボットより小さい数字をその左側に、ピボットより大きい数字をその右側に配置します。これにより、ピボットの左側にはそれより小さい数字が、右側にはそれより大きい数字が集まります。その後、ピボットの左側と右側の部分配列に対して、このプロセスを繰り返します。各部分配列の長さが1になるまで続けます。最後に、分割されたこれらの配列を結合すれば完了です。手順は以下の通りです。

1. 配列からランダムに1つの数字をピボットとして選び、配列内の各数字をピボットと比較します。ピボットより小さい数字はピボットの左側に、大きい数字はピボットの右側に配置します。
2. 上記の処理が完了した左右の2つの部分配列に対して、ステップ1を繰り返します。
3. すべての部分配列の長さが1になったら停止します。

実装#

以下は、私が慣れている言語での実装例です（最初の数字をピボットとし、再帰的な方法を採用しています）。

Python版#

    def quick_sort(lst,left,right):
    	i = left;
    	j = right
    	if i >= j:
    		return lst
    	k = lst[i]
    	while i < j:
    		while i < j and lst[j] >= k:		#lst[j]<=k时，循环结束，并将其值赋给lst[i]
    			j -= 1
    		lst[i] = lst[j]
    		while i < j and lst[i] <= k:		#lst[i]>=k时，循环结束，并将其值赋给lst[j]
    			i += 1
    		lst[j] = lst[i]
    	lst[i] = k								#当i>=j时，将k的值赋给lst[i]
    	quick_sort(lst,left,i-1)
    	quick_sort(lst,j+1,right)
    	return lst

JavaScript版#

function quick_sort(lst, l, r) {
  var i = l,
    j = r,
    k = lst[l];
  if (i >= j) {
    return lst;
  }
  while (i < j) {
    for (; i < j; j--) {
      if (lst[j] <= k) {
        lst[i] = lst[j];
        i++;
        break;
      }
    }
    for (; i < j; i++) {
      if (lst[i] >= k) {
        lst[j] = lst[i];
        j--;
        break;
      }
    }
  }
  lst[i] = k;
  quick_sort(lst, l, i - 1);
  quick_sort(lst, j + 1, r);
  return lst;
}

C言語版#

    void qucik_sort(int lst[],int l,int r)
    {
    	if(l < r)
    	{
    		int i = l, j = r, k = lst[l];
    		while (i < j){
    			for (; i < j; --j)
    			{
    				if (lst[j] <= k)
    				{
    					lst[i] = lst [j];
    					i++;
    					break;
    				}
    			}
    			for (; i < j; ++i)
    			{
    				if (lst[i] >= k)
    				{
    					lst[j] = lst[i];
    					j--;
    					break;
    				}
    			}
    		}
    		lst[i] = k;
    		qucik_sort(lst, l, i-1);
    		qucik_sort(lst, j+1, r);
    	}
    }