<？
$arr = array(49, 38, 65, 97, 76, 13, 27, 49);
echo 'original_arr: '; print_r($arr); 

//插入排序
function insertSort($arr) {
     $count = count($arr);
     for ($i=1; $i<$count; $i++) {
          $tmp = $arr[$i];
          $j = $i - 1;
          while ($j >= 0 && $arr[$j] > $tmp) {
               list($arr[$j+1], $arr[$j]) = array($arr[$j], $tmp);
               $j--;
          }
     }
     return $arr;
}
echo 'insertSort: '; print_r(insertSort($arr));

//选择排序
function selectSort($arr) {
     $count = count($arr);
     for ($i=0; $i<$count; $i++) {
          $k = $i;
          for ($j=$i+1; $j<$count; $j++) {
               if ($arr[$k] > $arr[$j]) {
                    $k = $j;
               }
          }
          if ($i != $k) {
               list($arr[$i], $arr[$k]) = array($arr[$k], $arr[$i]);
          }
         
     }
     return $arr;
}
echo 'selectSort: '; print_r(selectSort($arr));

//冒泡排序
function bubbleSort($arr) {
     $count = count($arr);
     for ($i=0; $i<$count; $i++) {
          for($j=$count-1; $j>$i; $j--) {
               if ($arr[$j] < $arr[$j-1]) {
                    list($arr[$j], $arr[$j-1]) = array($arr[$j-1], $arr[$j]);
               }
          }
     }
     return $arr;
}
echo 'bubbleSort: '; print_r(bubbleSort($arr)); 

//快速排序
function quickSort($arr) {
     $count = count($arr);
     if ($count <= 1) return $arr;
     $key = $arr[0];
     $left = $right = array();
     for($i=1; $i<$count; $i++) {
          if ($arr[$i] <= $key) {
               $left[] = $arr[$i];
          } else {
               $right[] = $arr[$i];
          }
     }
     $left =  quickSort($left);
     $right = quickSort($right);
     return array_merge($left, array($key), $right);
}
echo 'quickSort: '; print_r(quickSort($arr));

//希尔排序
function shellSort($arr) {
     $count = count($arr);
     for ($inc=intval($count/2); $inc>0; $inc=intval($inc/2)) {
          for ($i=$inc; $i<$count; $i++) {
               $tmp = $arr[$i];
               for ($j=$i; $j>=$inc; $j-=$inc) {
                    if ($tmp < $arr[$j-$inc]) {
                         $arr[$j] = $arr[$j-$inc];
                    } else {
                         break;
                    }
                    $arr[$j] = $tmp;
               }
          }
     }
     return $arr;
}
echo 'shellSort: '; print_r(shellSort($arr));