/**
* 冒泡排序
* @param array $arr
*/
function bubbleSort(array &$arr) : void{
  $length = count($arr);
  // 外層循環(huán)，從數(shù)組首部開始，每完成一次循環(huán)，可確定$arr[$i] 位置的元素
  for ($i = 0; $i < $length; $i++){
    // 內(nèi)層循環(huán)，$j 從后往前循環(huán)
    for ($j = $length - 1; $j > $i; $j--) {
      // 若前面的值大于后面的值，則互換位置
      if ($arr[$j] < $arr[$j - 1]) {
        // 互換數(shù)組兩個(gè)位置的值
        [$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
      }
    }
  }
}

function shell_sort(array $arr){
      // 將$arr按升序排列
      $len = count($arr);
      $f = 3;// 定義因子
      $h = 1;// 最小為1
      while ($h < $len/$f){
          $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
      }
      while ($h >= 1){  // 將數(shù)組變?yōu)閔有序
          for ($i = $h; $i < $len; $i++){  // 將a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的關(guān)鍵
              for ($j = $i; $j >= $h;  $j -= $h){
                  if ($arr[$j] < $arr[$j-$h]){
                      $temp = $arr[$j];
                      $arr[$j] = $arr[$j-$h];
                      $arr[$j-$h] = $temp;
                  }
                  //print_r($arr);echo '<br/>'; // 打開這行注釋，可以看到每一步被替換的情形
              }
          }
          $h = intval($h/$f);
      }
      return $arr;
  }

/**
* 選擇排序
* @param array $arr
*/
function selectionSort(array &$arr) : void{
    $length = count($arr);
    // 外層循環(huán)，從數(shù)組首部開始，每完成一次循環(huán)，可確定一個(gè)元素的位置
    for ($i = 0; $i < $length - 1; $i++) {
        // 選定的最小值的索引
        $minIdx = $i;
        // 從$i + 1 位開始循環(huán)，判斷當(dāng)前選定的元素是否是當(dāng)次循環(huán)的最小值
        for ($j = $i + 1; $j < $length; $j++) {
            // 若出現(xiàn)比選定的值還小的值，則替換最小值的索引
            if ($arr[$minIdx] > $arr[$j]) {
                $minIdx = $j;
             }
        }
        // 互換數(shù)組兩個(gè)位置的值
        [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
    }
}


/**
* 選擇排序- 方法2
* @param array $arr
*/
function selectionSort2(array &$arr) : void{
    $length = count($arr);
    // 外層循環(huán)，從數(shù)組首部開始，每完成一次循環(huán)，依次確定數(shù)組元素的位置
    for ($i = 0; $i < $length; $i++) {
        // 從$i + 1 位開始循環(huán)，依次判定$arr[$i] 與$arr[$j] 的大小
        for ($j = $i + 1; $j < $length; $j++) {
            // 若$arr[$i] 比$arr[$j] 大，則互換兩個(gè)元素的位置
            if ($arr[$i] > $arr[$j]) {
                // 互換數(shù)組兩個(gè)位置的值
                [$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
            }
        }
     }
}

/**
* 插入排序
* @param array $arr
*/
function insertionSort(array &$arr) : void{
    $length = count($arr);
    // 從數(shù)組首部開始排序，每完成一次循環(huán)，可確定一個(gè)元素的位置
    for ($i = 0; $i < $length - 1; $i++) {
        // 內(nèi)層循環(huán)從$i + 1 個(gè)元素開始，一位一位向前比較
        // 若前面的值比自己大，則替換，直到前面的值比自己小了，停止循環(huán)
        for ($j = $i + 1; $j > 0; $j--) {
            if ($arr[$j] >= $arr[$j - 1]) {
                break;
            }
            [[$arr[$j], $arr[$j - 1]]] = [[$arr[$j - 1], $arr[$j]]];
        }
     }
}


/**
* 插入排序- 方法2
* @param array $arr
*/
function insertionSort2(array &$arr) : void{
    $length = count($arr);
    // 從數(shù)組首部開始排序，每完成一次循環(huán)，可確定一個(gè)元素的位置
    for ($i = 0; $i < $length - 1; $i++) {
        // 從第二個(gè)元素開始，選擇固定位置的值作為基準(zhǔn)值
        $currentVal = $arr[$i + 1];
        // 初始鍵位于選定值的前一個(gè)位置
        $preIdx = $i;
        // 拿基準(zhǔn)值一步一步向前比較，直到基準(zhǔn)值比前面的值小，則兩值互換位置
        while ($preIdx >= 0 && $currentVal < $arr[$preIdx]) {
            $arr[$preIdx + 1] = $arr[$preIdx];
            $arr[$preIdx] = $currentVal;
            $preIdx--;
        }
    }
}

/**
* 快速排序
* @param $arr
*/
function quickSort(& $arr) : void{
    $length = count($arr);
    // 若數(shù)組為空，則不需要運(yùn)行
    if ($length <= 1) {
        return;
    }
    $middle = $arr[0]; // 選定一個(gè)中間值
    $left = []; // 接收小于中間值
    $right = [];// 接收大于中間值
    // 循環(huán)比較
    for ($i = 1; $i < $length; $i++) {
        if ($middle < $arr[$i]) {
           // 大于中間值
           $right[] = $arr[$i];
        } else {
            // 小于或等于中間值
            $left[] = $arr[$i];
        }
    }
    // 遞歸排序劃分好的左右兩邊
    quickSort($left);
    quickSort($right);
    $arr = array_merge($left, [$middle], $right);
}

//因?yàn)槭菙?shù)組,下標(biāo)從0開始,所以,下標(biāo)為n根結(jié)點(diǎn)的左子結(jié)點(diǎn)為2n+1,右子結(jié)點(diǎn)為2n+2;  
    //初始化值,建立初始堆
    $arr=array(49,38,65,97,76,13,27,50);
    $arrSize=count($arr);


    //將第一次排序抽出來，因?yàn)樽詈笠淮闻判虿恍枰俳粨Q值了。
    buildHeap($arr,$arrSize);


    for($i=$arrSize-1;$i>0;$i--){
        swap($arr,$i,0);
        $arrSize--;
        buildHeap($arr,$arrSize);   
    }


    //用數(shù)組建立最小堆
    function buildHeap(&$arr,$arrSize){
        //計(jì)算出最開始的下標(biāo)$index,如圖,為數(shù)字"97"所在位置,比較每一個(gè)子樹的父結(jié)點(diǎn)和子結(jié)點(diǎn),將最小值存入父結(jié)點(diǎn)中
        //從$index處對(duì)一個(gè)樹進(jìn)行循環(huán)比較,形成最小堆
        for($index=intval($arrSize/2)-1; $index>=0; $index--){
            //如果有左節(jié)點(diǎn),將其下標(biāo)存進(jìn)最小值$min
            if($index*2+1<$arrSize){
                $min=$index*2+1;
                //如果有右子結(jié)點(diǎn),比較左右結(jié)點(diǎn)的大小,如果右子結(jié)點(diǎn)更小,將其結(jié)點(diǎn)的下標(biāo)記錄進(jìn)最小值$min
                if($index*2+2<$arrSize){
                    if($arr[$index*2+2]<$arr[$min]){
                        $min=$index*2+2;
                    }
                }
                //將子結(jié)點(diǎn)中較小的和父結(jié)點(diǎn)比較,若子結(jié)點(diǎn)較小,與父結(jié)點(diǎn)交換位置,同時(shí)更新較小
                if($arr[$min]<$arr[$index]){
                    swap($arr,$min,$index);
                }   
            }
        }
    }


    //此函數(shù)用來交換下數(shù)組$arr中下標(biāo)為$one和$another的數(shù)據(jù)
    function swap(&$arr,$one,$another){
        $tmp=$arr[$one];
        $arr[$one]=$arr[$another];
        $arr[$another]=$tmp;
    }

/**
* 歸并排序
* @param array $arr
* @return array
*/
function mergeSort(array $arr){
    // 計(jì)算數(shù)組長(zhǎng)度，若長(zhǎng)度不大于1，則不需要排序
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    // 獲取數(shù)組中間位置的索引
    $midIdx = floor($length / 2);
    // 把數(shù)組從中間拆分成左右兩部分
    $left = mergeSort(array_slice($arr, 0, $midIdx));
    $right = mergeSort(array_slice($arr, $midIdx));
    // 合并兩部分，同時(shí)進(jìn)行排序
    return merge($left, $right);
}


/**
* 合并數(shù)組，同時(shí)進(jìn)行排序
* @param array $left
* @param array $right
* @return array
*/
function merge(array $left, array $right){
    // 分別計(jì)算左右兩數(shù)組的長(zhǎng)度
    $lLength = count($left);
    $rLength = count($right);
    // 左右兩數(shù)組的索引
    $l = $r = 0;
    $lists = [];
    // 只有左右兩數(shù)組都未遍歷完成時(shí)，才有必要繼續(xù)遍歷
    // 當(dāng)其中一個(gè)數(shù)組的元素遍歷完成，說明另一個(gè)數(shù)組中未遍歷過的值比遍歷過的值都大
    while ($l < $lLength && $r < $rLength) {
        // 比較$left[$l] 和$right[$r]，取其中較小的值加入到$lists 數(shù)組中
        if ($left[$l] < $right[$r]) {
            $lists[] = $left[$l];
            $l++;
        } else {
            $lists[] = $right[$r];
            $r++;
        }
    }
    // 合并$lists 和$left、$right 中剩余的元素
    return array_merge($lists, array_slice($left, $l), array_slice($right,$r));
}


/**
* 合并數(shù)組，同時(shí)進(jìn)行排序- 方法2
* @param array $left
* @param array $right
* @return array
*/
function merge2(array $left, array $right){
    // 分別計(jì)算左右兩數(shù)組的長(zhǎng)度
    $lLength = count($left);
    $rLength = count($right);
    // 左右兩數(shù)組的索引
    $l = $r = 0;
    $lists = [];
    // 只有左右兩數(shù)組都未遍歷完成時(shí)，才有必要繼續(xù)遍歷
    // 當(dāng)其中一個(gè)數(shù)組的元素遍歷完成，說明另一個(gè)數(shù)組中未遍歷過的值比遍歷過的值都大
    while ($l < $lLength && $r < $rLength) {
        // 比較$left[$l] 和$right[$r]，取其中較小的值加入到$lists 數(shù)組中
        if ($left[$l] < $right[$r]) {
            $lists[] = $left[$l];
            // PHP 中unset 掉數(shù)組中的元素后，其他元素的鍵名不變
            unset($left[$l]);
            $l++;
        } else {
            $lists[] = $right[$r];
            unset($right[$r]);
            $r++;
        }
    }
    // 合并$lists 和$left、$right 中剩余的元素
    return array_merge($lists, $left, $right);
}


/**
* 合并數(shù)組，同時(shí)進(jìn)行排序- 方法3
* @param array $left
* @param array $right
* @return array
*/
function merge3(array $left, array $right){
    // 分別計(jì)算左右兩數(shù)組的長(zhǎng)度
    $lLength = count($left);
    $rLength = count($right);
    $lists = [];
    // 只有左右兩數(shù)組都未遍歷完成時(shí)，才有必要繼續(xù)遍歷
    // 當(dāng)其中一個(gè)數(shù)組的元素遍歷完成，說明另一個(gè)數(shù)組中未遍歷過的值比遍歷過的值都大
    while ($lLength > 0 && $rLength > 0) {
      // 比較$left[$l] 和$right[$r]，取其中較小的值加入到$lists 數(shù)組中
      if ($left[0] < $right[0]) {
          $lists[] = $left[0];
          // PHP 中unset 掉數(shù)組中的元素后，其他元素的鍵名不變
          unset($left[0]);
          // 重建數(shù)組索引，始終讓比較的值在第一位
          $left = array_values($left);
          $lLength--;
      } else {
          $lists[] = $right[0];
          unset($right[0]);
          $right = array_values($right);
          $rLength--;
      }
  }
  // 合并$lists 和$left、$right 中剩余的元素
  return array_merge($lists, $left, $right);
}