（１）バブルソート

• 隣り合う要素の値を比較し、大小が逆だったら交換する。この比較を必要がなくなるまで繰り返す方法。
• 泡のようにデータが浮かび上がっていくので「バブルソート」。

$arry=array(9,2,8,3,7,4,6,5,1);
$length=count($arry);

for($j=0;$j<$length-1;$j++){
  for($i=0;$i<$length-1;$i++){
    if($arry[$i]>$arry[$i+1]){
      $tmp = $arry[$i];
      $arry[$i] = $arry[$i+1];
      $arry[$i+1] = $tmp;
    }
  }
}
//画面表示
for($i=0;$i<$length;$i++){
  echo $arry[$i];
  //出力結果は123456789
}

（２）選択ソート

最小値を入れておく箱を一つ決めておく。そこに適当に一番左の値を入れ、順に比較していき小さいほうを箱にいれる。これを繰り返していく。

$arry=array(9,2,8,3,7,4,6,5,1);
$length=count($arry);

for($i=0;$i<$length;$i++){
  $k = $i;
  $min = $arry[$i];
  for($j=$i+1;$j<$length;$j++){
    if($min > $arry[$j]){
      $k = $j;
      $min = $arry[$j];
    }
  }
  $arry[$k] = $arry[$i];
  $arry[$i] = $min;
}
//画面表示
for($i=0;$i<$length;$i++){
  echo $arry[$i];
  //出力結果は123456789
}

（３）挿入ソート

$arry=array(9,2,8,3,7,4,6,5,1);
$length=count($arry);

for($i=0; $i<$length; $i++){
  $tmp = $arry[$i];
  for($k=$i; $k>0 && $arry[$k-1] > $tmp; $k--){
    $arry[$k] = $arry[$k-1];
  }
  $arry[$k] = $tmp;
}



// 結果出力
for($i=0; $i<$length; $i++){
  echo $arry[$i];
  //出力結果は123456789
}

（４）クイックソート（バブルソートの発展Ver）

• 基準値を決めて、大小のグループに分ける。基準値は何でもよい。
• 真ん中の位置にある値を基準値に決めたりする。
• ちなみにC言語のqsortは最後の値を基準値としている。
• 基準値より小さいグループと、基準値より大きいグループに分ける。
• お互いのグループの、条件に合ってない値を交換していく。
• できたグループ内でさらに同じ処理を繰り返していく。
• 再帰（同じプログラムquicksortを何度も利用）

$arry = array(9,2,8,3,7,4,6,5,1);
$length = count($arry);

q_sort($arry,0,$length-1);

function q_sort(&$arr,$left,$right){
  if($left>=$right){
    return;
  }
  $key = (int) ($left+$right)/2;
  $pivot = $arr[$key];
  $i = $left;
  $j = $right;
  while($i<=$j){
    while($arr[$i]<$pivot){
      $i++;
    }
    while($arr[$j]>$pivot){
      $j--;
    }
    if($i<=$j){//一度交換すると$i>$jとなる場合があるので、その場合は交換しない
      $tmp = $arr[$i];
      $arr[$i] = $arr[$j];
      $arr[$j] = $tmp;
      $i++;
      $j--;
    }
  }
  q_sort($arr,$left,$j);
  q_sort($arr,$i,$right);
}

//画面表示
for($i=0;$i<$length;$i++){
  echo $arry[$i];
  //出力結果は123456789
}

（５）ヒープソート（選択ソートの発展Ver）

長くなりそうなので別エントリーで書きたいと思います。

取り急ぎCodeZineなどが参考になると思います。

（６）シェルソート（挿入ソートの発展Ver）

• とびとびのところを見ながら挿入ソート
• どんなデータでもそれなりのスピードで並べ替えてくれる。

$arry = array(9,2,8,3,7,4,6,5,1);
$length = count($arry);

for($h= (int) $length/2;$h>0;$h= (int) $h/2){
  for($k=0;$k<$h;$k++){
    for($i=$k+$h;$i<$length;$i+=$h){
      $x = $arry[$i];
      for($j=$i-$h;$j>=$k&&$arry[$j]>$x;$j-=$h){
        $arry[$j+$h] = $arry[$j];
      }
      $arry[$j+$h] = $x;
    }
  }
}
//画面表示
for($i=0;$i<$length;$i++){
  echo $arry[$i];
  //出力結果は123456789
}

（７）　マージソート

• かなり高速
• メモリを多く必要とする

こちらも長くなりそうなので、別エントリーで書きたいと思います。
取り急ぎ、CodeZineなどが参考になりそうです。