7种php基本排序实现方法

  • 更新时间:2022-07-12 08:53:16
  • 编辑:燕正青

本文总结了一下常用的7种排序方法,并用php语言实现。

1、直接插入排序

/*
 *  直接插入排序,插入排序的思想是:当前插入位置之前的元素有序,
 *  若插入当前位置的元素比有序元素最后一个元素大,则什么也不做,
 *  否则在有序序列中找到插入的位置,并插入
 */
function insertSort($arr) {
  $len = count($arr);  
  for($i = 1; $i < $len; $i++) {
    if($arr[$i-1] > $arr[i]) {
      for($j = $i - 1;$j >= 0; $j-- ) {
        $tmp = $arr[$j+1];
        if($tmp < $arr[$j]) {
          $arr[$j+1] = $arr[$j];
          $arr[$j] = $tmp;
        }else{
          break;
        }          
      }  
    }
  }  
  return $arr;
}

2、冒泡排序

/*
  冒泡排序,冒泡排序思想:进行 n-1 趟冒泡排序, 每趟两两比较调整最大值到数组(子数组)末尾
*/
function bubbleSort($arr) {
  $len = count($arr);
  for($i = 1; $i < $len; $i++) {
    for($j = 0; $j < $len-$i; $j++) {
      if($arr[$j] > $arr[$j+1]) {
        $tmp = $arr[$j+1];
        $arr[$j+1] = $arr[$j];
        $arr[$j] = $tmp;
      }
    }
  }
  return $arr;
}

3、简单选择排序

/*
  简单选择排序, 简单排序思想:从数组第一个元素开始依次确定从小到大的元素
*/
function selectSort($arr) {
  $len = count($arr);
  for($i = 0; $i < $len; $i++) {
    $k = $i;
    for($j = $i+1; $j < $len; $j++) {
      if($arr[$k] > $arr[$j]) {
        $k = $j;
      }
    }
    if($k != $i) {
      $tmp = $arr[$i];
      $arr[$i] = $arr[$k];
      $arr[$k] = $tmp;
    }
  }
  return $arr;
}

4、希尔排序

/*
  希尔排序,希尔排序原理:将数组按指定步长分隔成若干子序列,然后分别对子序列进行排序(在这是直接)
*/
function shellSort($arr) {
  $len = count($arr);
  $k = floor($len/2);
  while($k > 0) {
    for($i = 0; $i < $k; $i++) {
      for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) {
        if($arr[$j] > $arr[$j+$k]) {
          $tmp = $arr[$j+$k];
          $arr[$j+$k] = $arr[$j];
          $arr[$j] = $tmp;
        }
      }
    }
    $k = floor($k/2);
  }
  return $arr;
}

5、快速排序

/*
 *  快速排序,快排思想:通过一趟排序将待排的记录分为两个独立的部分,其中一部分的记录的关键字均不大于
 *  另一部分记录的关键字,然后再分别对这两部分记录继续进行快速排序,以达到整个序列有序,具体做法需要
 *  每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。
 *  quickSort($arr, 0, count($arr) -1);
 */
function quickSort(&$arr,$low,$high) {
  if($low < $high) {
    $i = $low;
    $j = $high;
    $primary = $arr[$low];
    while($i < $j) {
      while($i < $j && $arr[$j] >= $primary) {
        $j--;
      }
      if($i < $j) {
        $arr[$i++] = $arr[$j];
      }
      while($i < $j && $arr[$i] <= $primary) {
        $i++;
      }
      if($i < $j) {
        $arr[$j--] = $arr[$i];
      }
    }
    $arr[$i] = $primary;
    quickSort($arr, $low, $i-1);
    quickSort($arr, $i+1, $high);
  }
}

6、堆排序

/*
  堆排序
*/

// 调整子堆的为大根堆的过程,$s为子堆的根的位置,$m为堆最后一个元素位置
function heapAdjust(&$arr, $s, $m) {
  $tmp = $arr[$s];
  // 在调整为大根堆的过程中可能会影响左子堆或右子堆
  // for循环的作用是要保证子堆也是大根堆
  for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) {
    // 找到根节点的左右孩子中的最大者,然后用这个最大者与根节点比较,
    // 若大则进行调整,否则符合大根堆的 特点跳出循环  
    if($j < $m && $arr[$j] < $arr[$j+1]) {
      $j++;
    }
    if($tmp >= $arr[$j] ) {
      break;
    }
    $arr[$s] = $arr[$j];
    $s = $j;
  }
  $arr[$s] = $tmp;
}

// 堆排序
function heapSort($arr) {
  $len = count($arr);
  // 依次从子堆开始调整堆为大根堆
  for($i = floor($len/2-1); $i >= 0; $i--) {
    heapAdjust($arr, $i, $len-1);
  }
  // 依次把根节点调换至最后一个位置,再次调整堆为大根堆,找到次最大值,
  // 依次类推得到一个有序数组
  for($n = $len-1; $n > 0; $n--) {
    $tmp = $arr[$n];
    $arr[$n] = $arr[0];
    $arr[0] = $tmp;
    heapAdjust($arr, 0, $n-1);
  }
  return $arr;
}

7、归并排序

/*
  归并排序,这里实现的是两路归并
*/
// 分别将有序的$arr1[s..m]、$arr2[m+1..n]归并为有序的$arr2[s..n]
function Merge(&$arr1, &$arr2, $s, $m, $n) {
  for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) {
    if($arr1[$i]<$arr1[$j]) {
      $arr2[$k] = $arr1[$i++];
    }else {
      $arr2[$k] = $arr1[$j++];
    }
  }
  if($i <= $m) {
    for(; $i <= $m; $i++) {
      $arr2[$k++] = $arr1[$i];
    }
  } else if($j <= $n) {
    for(; $j <= $n; $j++) {
      $arr2[$k++] = $arr1[$j];
    }
  }
}

// 递归形式的两路归并
function MSort(&$arr1, &$arr2, $s, $t) {
  if($s == $t) {
    $arr2[$s] = $arr1[$s];
  }else {
    $m = floor(($s+$t)/2);
    $tmp_arr = array();
    MSort($arr1, $tmp_arr, $s, $m);
    MSort($arr1, $tmp_arr, $m+1, $t);
    Merge($tmp_arr, $arr2, $s, $m, $t);
  }
}

// 对一位数组$arr[0..n-1]中的元素进行两路归并
function mergeSort($arr) {
  $len = count($arr);
  MSort($arr, $arr, 0, $len-1);
  return $arr;
}

使用经验
若排序的记录数目n较小时,可以采用直接插入排序和简单选择排序,当记录本身信息量较大时,用简单选择排序方法较好。
若待排序记录按关键字基本有序,适合采用直接插入排序和冒泡排序。
若n值较大时,可以采用快速排序、堆排序和归并排序。另外快速排序被认为是内部排序方法中最好的方法。

以上就是本文的全部内容,希望对大家的学习有所帮助。

相关教程

  • PHP Include文件实例讲解

    给网友朋友们带来一篇关于PHP的教程,在本文里我们给大家分享了关于PHP Include文件实例内容,对此知识点有兴趣的读者们学习下。

    发布时间:2022-07-12

  • php中curl实现的股票信息查询的实例详解

    这篇文章主要介绍了php基于curl实现的股票信息查询类,结合完整实例形式分析了php使用curl调用API接口实现股票信息查询功能的相关操作技巧,需要的朋友可以参考下

    发布时间:2019-11-02

  • php中Magic methods的用法总结

    有些东西如果不是经常使用,很容易忘记,比如魔术方法和魔术常量,这篇文章主要介绍了php魔术方法(Magic methods)的使用方法,感兴趣的小伙伴们可以参考一下

    发布时间:2020-03-27

  • PHP自定义函数实现格式化秒的代码分享

    这篇文章主要介绍了PHP自定义函数实现格式化秒的方法,涉及php数组及数值运算的操作技巧,需要的朋友可以参考下

    发布时间:2020-02-15

  • PHP调整数组顺序使奇数位于偶数前(代码/闭包扩展)

    本篇文章给大家带来的内容是关于php如何实现原址排序数组使奇数位于偶数前面(代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

    发布时间:2018-10-19

  • PHP实现微信红包金额拆分试玩的算法实例详解

    本篇文章主要介绍了PHP实现微信红包金额拆分试玩的算法示例,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

    发布时间:2020-02-01

  • PHP批量获取网页中所有固定种子链接的实例代码

    这篇文章主要介绍了PHP批量获取网页中所有固定种子链接的方法,涉及php字符串与文件操作的相关技巧,需要的朋友可以参考下

    发布时间:2019-08-29

  • php获取目录下所有文件及目录的方法

    这篇文章主要介绍了php获取目录下所有文件及目录多种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2020-07-24

  • 详解php 的反射及实例分析

    本文主要介绍PHP的反射内容的知识,这里提供相关的资料讲解,及简单示例代码供大家参考,有兴趣的小伙伴可以参考下

    发布时间:2020-01-26

用户留言