php实现排序的7种方法

本文主要是介绍php实现排序的7种方法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

php实现排序的7种方法
首先是创建虚拟数据及获取花费时间的方法

//创建虚拟数据
public function createData(){
   $firtime = microtime();
    $data = [];
    for($i = 0; $i < 1000000;){
        $val = ceil(rand(1,1000000));
        if(!in_array($val, $data)){
            $data[] = $val;
            $i++;
        }
    }
    $sectime = microtime();
    $this->getTimeLimit($firtime, $sectime);
    return $data;
}

//获取花费时间
public function getTimeLimit($a, $b){
    list($seconds1, $msecond1) = explode(' ', $a);
    list($seconds2, $msecond2) = explode(' ', $b);
    var_dump(($seconds2 - $seconds1)+($msecond2 - $msecond1));
}

1.归并排序
（1）归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
（2）复杂度
归并排序是一种稳定的排序算法，归并排序的主要问题在于它需要一个与待排序数组一样大的辅助数组空间。由于归并排序每次划分时两个子序列的长度基本一样，所以归并排序最好、最差和平均时间复杂度都是nlog2n。

//归并排序开始
    public function mergeSort($data)
    {
        $firtime = microtime();
        $res = $this->mergeSortMain($data, 0, count($data)-1);
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }

    public function mergeSortMain(&$data, $from, $to){
        if($from == $to){
            return [$data[$to]];
        }
        $middle = floor(($to + $from)/2);
        $left = $this->mergeSortMain($data, $from, $middle);
        $right = $this->mergeSortMain($data, $middle+1, $to);
        $res = $this->sortTwoSortArr($left, $right);
        return $res;
    }

    public function sortTwoSortArr($arrA, $arrB){
        $res = [];
        $index = 0;
        $indexA = 0;
        $indexB = 0;
        while (count($arrA)&&count($arrB)) {
            if ($arrA[$indexA] < $arrB[$indexB]) {
                $res[$index++] =  $arrA[$indexA];
                unset($arrA[$indexA++]);
            } else {
                $res[$index++] =  $arrB[$indexB];
                unset($arrB[$indexB++]);
            }
        }
        if (count($arrA)) {
            while (count($arrA)) {
                $res[$index++] =  $arrA[$indexA];
                unset($arrA[$indexA++]);
            }
        } elseif (count($arrB)){
            while (count($arrB)) {
                $res[$index++] =  $arrB[$indexB];
                unset($arrB[$indexB++]);
            }
        }
        return $res;
    }
    //归并排序结束

2.快速排序
（1）快速排序：顾名思义，这是实践中的一种快速的排序算法，它平均运行实践是O(N log N).该算法之所以特别快，主要是由于非常精炼和高度优化的内部循环。它的最坏情形性能为O(N^2)。

像归并排序一样，快速排序也是一种分治的递归算法。
（2）步骤：

1、从数列中挑出一个元素，称为"基准"（pivot）

2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

 //快速排序开始
    public function fastSort($data)
    {
        $firtime = microtime();
        $this->fastSortMain(0, count($data) - 1, $data);
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }

    public function fastSortMain($start, $end, &$data){
        if ($start >= $end) {
            return;
        }
        $middle = $this->fastSortSwap($start, $end, $data);
        $this->fastSortMain($start, $middle-1, $data);
        $this->fastSortMain($middle+1, $end, $data);
    }


    //这个方法的作用是把 $data从start到end之间的部分 分成大于某值或者小于某值两部分，并且返回某值的位置
    public function fastSortSwap($start, $end, &$data){
        $flag = $data[$end];
        $resust_key = $start;
        for ($i=$start; $i < $end; $i++) { 
            if ($data[$i] > $flag) {
                continue;
            } else {
                $temp = $data[$i];
                $data[$i] = $data[$resust_key];
                $data[$resust_key++] = $temp;
            }
        }
        $data[$end] = $data[$resust_key];
        $data[$resust_key] = $flag;
        return $resust_key;
    }
    //快速排序结束

3.选择排序
原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完.。

//选择排序开始
public function selectSort($data)
{
     $firtime = microtime();
     for ($i=0; $i <count($data) ; $i++) {
         $minval = $data[$i];
         $minkey = $i;
         for ($j=$i; $j < count($data); $j++) { 
             if($data[$j]<$minval){
                 $minval = $data[$j];
                 $minkey = $j;
             }
         }
         $temp = $data[$i];
         $data[$i] = $minval;
         $data[$minkey] = $temp;
     }
     $sectime = microtime();
     $this->getTimeLimit($firtime, $sectime);
}
 //选择排序结束

4.希尔排序
希尔排序是先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

//希尔排序开始
public function shellSort($data)
{
  $firtime = microtime();
  $jump = floor(count($data)/2);
  while($jump >= 1){
      for ($i = 0; $i < $jump; $i++) {
          for ($j = $i + $jump; $j < count($data);) {
              $temp = $data[$j];
              $k = $j - $jump;
              while ($k >= 0&&$data[$k] > $temp) {
                  $data[$k + $jump] = $data[$k];
                  $k = $k - $jump;
              }
              $data[$k + $jump] = $temp;
              $j += $jump;
          }
      }
      $jump = floor($jump/2);
  }
  $sectime = microtime();
  $this->getTimeLimit($firtime, $sectime);
}
//希尔排序结束

5.冒泡排序
冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

//冒泡排序开始
public function bubbleSort($data)
{
    $firtime = microtime();
    for ($i = count($data)-1; $i > 0; $i--) {
        $flag = true;
        for ($j=0; $j < $i; $j++) { 
            if($data[$j] > $data[$j+1]){
                $temp = $data[$j];
                $data[$j] = $data[$j+1];
                $data[$j+1] = $temp;
                $flag = false;
            }
        }
        if($flag){
            break;
        }
    }
    $sectime = microtime();
    $this->getTimeLimit($firtime, $sectime);
}
//冒泡排序结束

6.插入排序

插入排序思想:

（1）插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。
（2）它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，
（3）找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），
（4）因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

//插入排序开始
public function insertSort($data){
  $firtime = microtime();
  for ($i = 1; $i < count($data); $i++) {
      $temp = $data[$i];
      $j = $i - 1;
      while ($j > 0&&$data[$j] > $temp) {
          $data[$j+1] = $data[$j];
          $j--;
      }
      $data[$j+1] = $temp;
  }
  $sectime = microtime();
  $this->getTimeLimit($firtime, $sectime);
}
//插入排序结束

7.堆排序
堆排序算法：

堆排序就是利用堆（假设利用大根堆）进行排序的方法，它的基本思想是：将待排序的序列构造成一个大根堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n - 1 个序列重新构造成一个堆，这样就会得到 n 个元素中的次小的值。如此反复执行，便能得到一个有序序列了。

大根堆排序算法的基本操作：

①建堆，建堆是不断调整堆的过程，从 len/2 处开始调整，一直到第一个节点，此处 len 是堆中元素的个数。建堆的过程是线性的过程，从 len/2 到 0 处一直调用调整堆的过程，相当于 o(h1) + o(h2) …+ o(hlen/2) 其中 h 表示节点的深度， len/2 表示节点的个数，这是一个求和的过程，结果是线性的 O(n)。

②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点 left(i) , right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是 lgn 的操作，因为是沿着深度方向进行调整的。

③堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面 len-1 个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是 O(nlgn)。因为建堆的时间复杂度是 O(n)（调用一次）；调整堆的时间复杂度是 lgn，调用了 n-1 次，所以堆排序的时间复杂度是 O(nlgn)。

//堆排序开始

public function heapSort($data){
  $firtime = microtime();
  $this->initHeap($data);
  $n = count($data);
  for ($i = $n - 1; $i > 0; $i--) { 
      $this->swap($data, 0, $i);
      $this->down($data, 0, $i - 1);
  }
  $sectime = microtime();
  $this->getTimeLimit($firtime, $sectime);
}

public function initHeap(&$data){
  $n = count($data);
  for ($i = $n/2-1; $i >= 0; $i--) { 
      $this->down($data, $i, $n-1);
  }
}

public function swap(&$data, $i, $j){
  $n = count($data);
  if ($i < 0||$j < 0||$i > $n||$j > $n) {
      return;
  } else {
      $temp = $data[$i];
      $data[$i] = $data[$j];
      $data[$j] = $temp;
  }
}

public function down(&$data, $head, $tail){
  $left_child = $head * 2 + 1;
  $right_child = $left_child + 1;
  $next_head = $left_child;
  $head_val = $data[$head];
  while ($left_child <= $tail) {
      if ($right_child <= $tail&&$data[$right_child] > $data[$left_child]) {
          $next_head = $right_child;
      }
      if ($data[$next_head] > $head_val) {//无论何时都只和最上面的那个值比较
          $data[$head] = $data[$next_head];
      } else {
          break;
      }
      $head = $next_head;
      $left_child = $head * 2 + 1;
      $right_child = $left_child + 1;
      $next_head = $left_child;
  }
  $data[$head] = $head_val;
}
//堆排序结束

最后发现7种排序的效率从低到高依次为

冒泡排序

选择排序

插入排序

希尔排序

归并排序

堆排序

快速排序

这篇关于php实现排序的7种方法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！