排序算法

1. 冒泡排序（将无序表中的所有记录，通过指针后移，其值不断的进行两两比较，大小不一则进行互换，得出升序序列或者降序序列）

   function swap(&$x, &$y) {
   	$t = $x;
   	$x = $y;
   	$y = $t;
   }
   
   function bubble_sort(&$arr) {
   	for ($i = 0; $i < count($arr) - 1; $i++)
   		for ($j = 0; $j < count($arr) - 1 - $i; $j++)
   			if ($arr[$j] > $arr[$j + 1])
   				swap($arr[$j], $arr[$j + 1]);
   }

2. 选择排序（ n 个记录的无序表遍历 n-1 次，第 i 次从无序表中第 i 个记录开始，找出后序关键字中最小的记录，然后放置在第 i 的位置上）

   function selectionSort($arr)
   {
       $len = count($arr);
       for ($i = 0; $i < $len - 1; $i++) {
           $minIndex = $i;
           for ($j = $i + 1; $j < $len; $j++) {
               if ($arr[$j] < $arr[$minIndex]) {
                   $minIndex = $j;
               }
           }
           $temp = $arr[$i];
           $arr[$i] = $arr[$minIndex];
           $arr[$minIndex] = $temp;
       }
       return $arr;
   }

3. 插入排序（重写，将数据按照一定的顺序一个一个的插入到有序的表，两两相比，大小不一就互换位置）

function insertionSort($arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $preIndex = $i - 1;
        while($preIndex >= 0 && $arr[$preIndex] > $arr[$preIndex + 1]) {
            list($arr[$preIndex+1],$arr[$preIndex]) = [$arr[$preIndex],$arr[$preIndex+1]];
                $preIndex--;
        }
    }
    return $arr;
}

4. 希尔排序 （其实就是另类的插入排序，先不断的分批小段（跳跃固定数量进行组合）进行插入排序，使得总体数据归于有序，最终所有的再一起排序，降低了时间复杂度）

   function shellSort($arr)
   {
       $len = count($arr);
       $temp = 0;
       $gap = 1;
       while($gap < $len / 3) {
           $gap = $gap * 3 + 1;
       }
       for ($gap; $gap > 0; $gap = floor($gap / 3)) {
           for ($i = $gap; $i < $len; $i++) {
               $temp = $arr[$i];
               for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
                   $arr[$j+$gap] = $arr[$j];
               }
               $arr[$j+$gap] = $temp;
           }
       }
       return $arr;
   }

5. 基数排序（按照数学意义上的个十百千万来进行排序，实际写代码基本用不到）

   function radixSort($arr, $maxDigit = null)
   {
       if ($maxDigit === null) {
           $maxDigit = max($arr);
       }
       $counter = [];
       for ($i = 0; $i < $maxDigit; $i++) {
           for ($j = 0; $j < count($arr); $j++) {
               preg_match_all('/\d/', (string) $arr[$j], $matches);
               $numArr = $matches[0];
               $lenTmp = count($numArr);
               $bucket = array_key_exists($lenTmp - $i - 1, $numArr)
                   ? intval($numArr[$lenTmp - $i - 1])
                   : 0;
               if (!array_key_exists($bucket, $counter)) {
                   $counter[$bucket] = [];
               }
               $counter[$bucket][] = $arr[$j];
           }
           $pos = 0;
           for ($j = 0; $j < count($counter); $j++) {
               $value = null;
               if ($counter[$j] !== null) {
                   while (($value = array_shift($counter[$j])) !== null) {
                       $arr[$pos++] = $value;
                   }
             }
           }
       }
   
       return $arr;
   }

6. 快速排序（基于比较的排序，每次选定一个数，将小于的放左边，大于的放右边，不断递归，最终就由小到大排序了）

   function quickSort($arr)
   {
       if (count($arr) <= 1)
           return $arr;
       $middle = $arr[0];
       $leftArray = array();
       $rightArray = array();
   
       for ($i = 1; $i < count($arr); $i++) {
           if ($arr[$i] > $middle)
               $rightArray[] = $arr[$i];
           else
               $leftArray[] = $arr[$i];
       }
       $leftArray = quickSort($leftArray);
       $leftArray[] = $middle;
   
       $rightArray = quickSort($rightArray);
       return array_merge($leftArray, $rightArray);
   }

7. 记数排序

   function countingSort($arr, $maxValue = null)
   {
       if ($maxValue === null) {
           $maxValue = max($arr);
       }
       for ($m = 0; $m < $maxValue + 1; $m++) {
           $bucket[] = null;
       }
   
       $arrLen = count($arr);
       for ($i = 0; $i < $arrLen; $i++) {
           if (!array_key_exists($arr[$i], $bucket)) {
               $bucket[$arr[$i]] = 0;
           }
           $bucket[$arr[$i]]++;
       }
   
       $sortedIndex = 0;
       foreach ($bucket as $key => $len) {
          
           if($len !== null){
               for($j = 0; $j < $len; $j++){
                   $arr[$sortedIndex++] = $key;
               }
           }
       }
   
       return $arr;
   }