PHP实现排序算法

一、插入排序

1.排序思想

插入排序(InsertionSort)，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。
插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

2.代码实现

function insertionSort($arr)
{
      $arr_nums = count($arr);
      for ($i=1; $i < $arr_nums; $i++) {
          $temp = $arr[$i];
          $j = $i;
          while ($j > 0 && $arr[$j - 1] > $temp) {
              $arr[$j] = $arr[$j - 1];
              $arr[$j - 1] = $temp;
              $j--;
          }
      }
      return $arr;
}

二、冒泡排序

1.排序步骤

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2.代码实现

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

三、选择排序

1.排序步骤

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

2.代码实现

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

四、快速排序

1.算法思想

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

2.排序步骤

• 从数列中挑出一个元素，称为 "基准"（pivot）;
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

3.代码实现

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

五、归并排序

1.排序步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  -重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

2.代码实现

public function mergeSort($arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }

    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    return merge(mergeSort($left), mergeSort($right));
}

public function merge($left, $right)
{
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    while (count($left)) {
        $result[] = array_shift($left);
    }
    while (count($right)) {
        $result[] = array_shift($right);
    }
    return $result;
 }