php实现常见排序,插入排序、希尔排序、直接选择、堆排序、冒泡排序、快速排序、归并排序、基数排序

Feb 5, 2018

 backend  php  排序

php实现常见排序,插入排序、希尔排序、直接选择、堆排序、冒泡排序、快速排序、归并排序、基数排序

常见排序

  • 常见排序有插入排序、希尔排序、直接选择、堆排序、冒泡排序、快速排序、归并排序、基数排序
  • 按照稳定情况：
    • 稳定：插入排序、冒泡排序、归并排序、基数排序
    • 不稳定：希尔排序、直接选择、堆排序、快速排序

实现

1. 冒泡排序

        /**
        * 冒泡排序
        */
        function bubbleSort (){
            $arr = [5, 1, 3, 4, 2];
            $len = count($arr);
            //循环控制冒泡的轮数
            for ($i = 0; $i < $len - 1; $i++) {
                for ($j = 0; $j < $len - $i - 1; $j++) {
                    if ($arr[$j] > $arr[$j + 1]) {
                        $temp = $arr[$j];
                        $arr[$j] = $arr[$j + 1];
                        $arr[$j + 1] = $temp;
                    }
                }
            }
            var_dump($arr); # [1, 2, 3, 4, 5]
        }

2. 选择排序

  • 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，

  • 然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

      function selectSort(){
      $arr = [5, 1, 3, 4, 2];
      $len = count($arr);
      # 从待匹配区选择最小的放入已排序的 $i=0开始
      for ($i = 0; $i < $len; $i++) {
          $min = $i;
          for ($j = $i + 1; $j < $len; $j++) {
              if ($arr[$min] > $arr[$j]) {
                  $min = $j;
              }
          }
          if ($min != $i) {
              $tmp = $arr[$i];
              $arr[$i] = $arr[$min];
              $arr[$min] = $tmp;
          }
      }
      var_dump($arr); # [1, 2, 3, 4, 5]
  }

3. 插入排序

  • 它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。

      function insertSort(){
      $arr = [5, 1, 3, 4, 2];
      $len = count($arr);
      # 待排序区拿出一个插入到已排序区
      for ($i = 0; $i < $len - 1; $i++) {
          $key = $arr[$i + 1];
          for ($j = $i; $j >= 0; $j--) {
              if ($arr[$j] > $key) {
                  $arr[$j + 1] = $arr[$j];
              } else {
                  break;
              }
          }
          $arr[$j + 1] = $key;
      }
      var_dump($arr); # [1, 2, 3, 4, 5]
  }

4. 快速排序

  • 基本思想：
    1. 先从数列中取出一个数作为基准数。
    2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
    3. 再对左右区间重复第二步，直到各区间只有一个数。
  • 总结：
    1. 性能方面其实是看php版本，比如我用php 8.1测的结果，随机生成1w个数，然后分别调用两个排序各1000次，得出的结果是，执行的时间差1s不到

  • 递归

          function quickSortByRecursion($arr)
      {
          $len = count($arr);
          if ($len <= 1) {
              return $arr;
          }
          $left = $right = [];
          //使用for循环进行遍历，把第一个元素当做比较的对象
          for ($i = 1; $i<$len; $i++) {
              if ($arr[$i] < $arr[0]) {
                  $left[] = $arr[$i];
              } else {
                  $right[] = $arr[$i];
              }
          }
          //递归调用
          $left = quickSortByRecursion($left);
          $right = quickSortByRecursion($right);

          //将所有的结果合并
          return array_merge($left, [$arr[0]], $right);
      }

  • 压栈

          function quickSortByStack($arr)
      {
          // 用stack栈来存储左中右数据
          $stack = [$arr];
          $sort = [];
          while (!empty($stack)) {
              $tmpArr = array_pop($stack);
              $size = count($tmpArr);
              if ($size <= 1) {
                  if ($size == 1) {
                      $sort[] = $tmpArr[0];
                  }
                  continue;
              }
              $mid = $tmpArr[0];
              $left = [];
              $right = [];
              for ($i=1;$i<$size;$i++) {
                  if ($tmpArr[$i] > $mid) {
                      $right[] = $tmpArr[$i];
                  } else {
                      $left[] = $tmpArr[$i];
                  }
              }
              $stack[] = $right;
              $stack[] = [$mid];
              $stack[] = $left;
          }
          return $sort;
      }
  • 希尔排序
    • 是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
      function shellSort()
  {
      $arr = [5, 1, 7, 8, 3, 4, 6, 2];
      $len = count($arr);
      $diff = (int) floor($len / 2); # 需要分成几组
      for (; $diff > 0; $diff = (int) floor($diff / 2)) { # 需要几次分组
          for ($i = 0; $i < $diff; $i++) { # 每个分组排序
              for ($j = $i; $j < $len && $j + $diff < $len; $j++) {
                  if ($arr[$j] > $arr[$j + $diff]) {
                      $tmp = $arr[$j + $diff];
                      $arr[$j + $diff] = $arr[$j];
                      $arr[$j] = $tmp;
                  }
              }
          }
      }
      var_dump($arr); # [1,2,3,4,5,6,7,8]
  }
 Toc
 Tags
 Related