基本的排序算法

基本的排序算法有

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序

各种排序的复杂度

排序方法	时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定	简单
插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
希尔排序	O(nlog2n)	O(n^2)	O(n)	O(1)	不稳定	较复杂
归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定	较复杂
快速排序	O(nlog2n)	O(n^2)	O(nlog2n)	O(nlog2n)	不稳定	较复杂
堆排序	O(nlog2^n)	O(nlog2^n)	O(nlog2^n)	O(1)	不稳定	较复杂
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(n+r)	稳定	较复杂

冒泡排序

你可以这样理解：（从小到大排序）存在10个不同大小的气泡，由底至上地把较少的气泡逐步地向上升，这样经过遍历一次后，最小的气泡就会被上升到顶（下标为0），然后再从底至上地这样升，循环直至十个气泡大小有序。

在冒泡排序中，最重要的思想是两两比较，将两者较少的升上去

<?php
  function maopao(&$arr) {
    $length = count($arr);
    // 从第二个元素开始遍历每个元素，分别冒泡
    for ($i = 1; $i < $length; $i++) {
      $j = $i-1;
      // 如果元素$j存在，并且前面的大于后面的，则交换位置
      while($j>=0 && $arr[$j] > $arr[$j+1]) {
              $temp = $arr[$j];
              $arr[$j] = $arr[$j+1];
              $arr[$j+1] = $temp;
              $j--;
      }
    }
  }

  $arr = [5,9,2,3,7,6,1,8,4];
  maopao($arr);
  var_dump($arr);

选择排序

选择排序的思路是，从前向后扫描找到最大（或最小）的元素，将此元素同扫描开始的位置交换，起始位置+1，再重复此操作，操作完成后即得到一个从大到小（或从小到大）的排序。

<?php
function xuanze(&$arr) {
    $length = count($arr);
    // 从第一个元素开始扫描
    for($i = 0; $i < $length; $i++) {
        // 先将起始位置记为最小位置$min
        $min = $i;
        $j = $i+1;
        while ($j < $length) {
            // 如果元素值小于最小位置的值，更新最小位置
            if ($arr[$j] < $arr[$min]) {
                $min = $j;
            }
            $j++;
        }
        // 扫描一遍后将最小值的位置与起始位置交换
        $temp = $arr[$min];
        $arr[$min] = $arr[$i];
        $arr[$i] = $temp;
    }
}

$arr = [5,9,2,3,7,6,1,8,4];
xuanze($arr);
var_dump($arr);

插入排序

插入排序就像我们整理扑克牌的顺序一样，从前向后检查每张牌，将此牌向前插入到一个合适的位置，遍历之后即得到一个有序的排序。

<?php
  function charu(&$arr) {
    $length = count($arr);
    // 从第二个元素开始，依次执行插入操作
    for ($i = 1; $i < $length; $i++) {
      // 记录当前的这个值，因为在元素向后平移的时候，这个值可能被覆盖掉
      $key = $arr[$i];
      $j = $i-1;
      // 向前遍历每个元素，如果此元素大于$key,则这个元素向后平移一位
      while($j >= 0 && $arr[$j] > $key) {
        $arr[$j+1] = $arr[$j];
        $j--;
      }
      // 遍历完成后，$j+1这个位置就是$key要插入的位置，赋值即可
      $arr[$j+1] = $key;
    }
  }

  $arr = [5,9,2,3,7,6,1,8,4];
  charu($arr);
  var_dump($arr);

希尔排序

希尔排序可以看做是一个有步长的插入排序，步长从大到小，根据步长对原序列的子序列进行插入排序，然后缩小步长，重复操作，直到步长为1时（就是插入排序），即可得到一个有序的序列。对比着插入排序就好理解希尔排序的算法。

<?php
  function xier(&$arr) {
    $length = count($arr);
    // 取一个步长$n
    $n = floor($length/3);
    // 步长$n不为1时，我们就根据步长对子序列进行插入排序
    while ($n > 0) {
      for ($i = 1; $i < $length; $i+=$n) {
        $key = $arr[$i];
        $j = $i-$n;
        while($j >= 0 && $arr[$j] > $key) {
          $arr[$j+$n] = $arr[$j];
          $j-=$n;
        }
        $arr[$j+$n] = $key;
      }
      // 缩小步长
      $n = floor($n/2);
    }
  }

  $arr = [5,9,2,3,7,6,1,8,4];
  xier($arr);
  var_dump($arr);

归并排序

基本思想:归并（Merge）排序法是将两个（或两个以上）有序数组合并成一个新的有序数组，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。整体思想是使用了递归。

<?php
  function guibin($arr) {
    $length = count($arr);
    // 如果数组元素小于2，则不需归并，直接返回该数组
    if ($length < 2) {
        return $arr;
    }
    // 否则将数组分为2部分，分别归并左边和右边
    $mid = floor($length/2);
    $left = guibin(array_slice($arr, 0, $mid));
    $right = guibin(array_slice($arr, $mid));
    // 将左右2个数组合并为一个从小到大有序的新数组
    $result = [];
    while (count($left) && count($right)) {
        $result[] = ($left[0] < $right[0]) ? array_shift($left) : array_shift($right);
    }
    return array_merge($result, $left, $right);
  }

  $arr = [5,9,2,3,7,6,1,8,4];
  $result = guibin($arr);
  var_dump($result);

快速排序

快速排序也是使用了递归的思想。我们通过一个序列中的某个元素，把比这个元素小的值放在它的左边，把比这个元素大的值放在它的右边，然后分别对左边和右边递归的调用快速排序。

<?php
  function kuaipai(&$arr, $from, $to) {
      // 如果 $from >= $to 则不做处理
      if ($from >= $to) {
        return;
      }
      // $j指向的就是最后一个比$arr[$to]小的元素，初始值为$from-1
      $j = $from-1;
      $i = $from;
      while($i < $to) {
        // 取$arr[$to]作为比较元素，当$arr[$i]小于它时，就把$j++，并且交换位置
        if ($arr[$i] < $arr[$to]) {
           $j++;
           $temp = $arr[$i];
           $arr[$i] = $arr[$j];
           $arr[$j] = $temp;
        }
        $i++;
      }
      // 遍历完成之后，$j指向的还是最后一个比$arr[$to]小的元素，$j++指向的就是第一个比$arr[$to]大的元素
      $j++;
      // 交换位置，将$arr[$to]放在中间位置
      $temp = $arr[$j];
      $arr[$j] = $arr[$to];
      $arr[$to] = $temp;
      // 分别快排左边和右边
      kuaipai($arr, $from, $j-1);
      kuaipai($arr, $j+1, $to);
  }

  $arr = [5,9,2,3,7,6,1,8,4];
  kuaipai($arr, 0, count($arr)-1);
  var_dump($arr);

注：此算法移植于《算法导论》中的快排思路，它相对于网上其他PHP快排实现方式的优点是，没有使用更多的内存空间。

堆排序

堆排序的主要思路是构建一个小头堆或大头堆（二叉树实现，用数组来存数据，下标从1开始），插入时插入新元素到最后，然后从N/2开始向上调整（因为N/2这个元素是最后一个具有叶子节点的元素）这棵树，上浮操作使得根节点的元素最小或最大；想获得有序序列时，只需将根节点同最后一个节点交换，再将调整的范围缩小1进行上浮操作，那么新的根节点就是第二小元素，再反复执行此操作，当范围为1的时候，就得到了有序的序列数组。

<?php
  // 堆排序
  function dui(&$arr, $to) {
    // 如果调整范围为1，则不需处理
    if ($to<=1) {
      return;
    }
    // 从最大范围的二分之一处，开始向上调整，调整后根节的值最小
    fixUp($arr, floor($to/2), $to);
    // 交换根节点和调整范围的最后一个元素
    swap($arr, 1, $to);
    // 缩小调整范围，递归调用堆排序
    dui($arr, $to-1);
  }

  // 最小元素上浮操作
  function fixUp(&$arr, $start, $size) {
    // 如果调整的起始元素为0，则说明上浮操作调整完了
    if ($start == 0) {
      return;
    }
    $min = $arr[$start];
    $s1 = $start*2;
    $s2 = $s1+1;
    // 分别判断叶子节点s1和s2的值，将最小的元素放到start位置
    if ($s1 <= $size && $arr[$s1] < $min) {
      $min = $arr[$s1];
      swap($arr, $s1, $start);
    }
    if ($s2 <= $size && $arr[$s2] < $min) {
      swap($arr, $s2, $start);
    }
    // start缩小1，递归的调用上浮操作
    fixUp($arr, $start-1, $size);
  }

  function swap(&$arr, $a, $b) {
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
  }

  $arr = [5,9,2,3,7,6,1,8,4];
  $n = count($arr);
  // 在首位压入一个NULL，为了让元素下标从1开始
  array_unshift($arr, NULL);
  // 堆排序处理数组
  dui($arr, $n);
  // 删除首位的NULL元素
  array_shift($arr);
  var_dump($arr);