php 排序算法-PHP实现排序堆排序算法

bendan520 php

2023-08-26 0 2,603 百度已收录

立即下单

进入商城

进不了网站？换个网络试试！

本文主要为您详细介绍PHP实现的HeapSort算法。有一定的参考价值。有兴趣的男士可以参考一下。

算法介绍：

这里我直接引用《大话数据结构》的开头：

上面提到的简单选择排序，需要比较n-1次才能在待排序的n条记录中选择最小的一条记录。本来，这也是可以理解的。找到第一个需要比较这么多次的数据很正常，不然怎么知道他是最小的记录。

遗憾的是这种操作并没有保存每趟的比较结果。下趟的比较结果比较重，上趟已经做了很多比较，但是因为上趟没有保存这种比较。比较结果，因此下次排序时会重复那些比较操作，因此记录的比较次数较多。

如果每次能够选择最杂的记录，并根据比较结果对其他记录进行相应的调整，那么排序的整体效率会特别高。堆排序是对简单选择排序的改进，这些改进的疗效尤其显着。

基本思想：

在介绍堆排序之前，我们先介绍一下堆：

《大话数据结构》中的定义：堆是一棵完全二叉树，具有以下性质：每个结点的值小于或等于其左右子结点的值，就成为大顶堆（big top heap）根堆）；或者每个节点的值大于或等于其左右节点的值，则成为小顶堆（小根堆）。

当时听到这句话的时候php 排序算法，我也对“堆是否是完全二叉树”产生了疑问。网上有人说不是完全二叉树，不管堆是不是完全二叉树，我还是持保留态度。我们只需要知道，这里我们使用完全二叉树形式的大根堆（小根堆），主要是为了方便存储和计算（后面会听到带来的方便）。

堆排序算法：

堆排序是一种借助堆进行排序的方法（假设使用大的根堆）。它的基本思想是构造一个要排序的序列到一个大的根堆中。此时整个序列的最大值就是堆顶的根节点。将其取出（虽然是与堆链表的末尾元素进行交换，此时末尾元素为最大值），然后将剩余的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)（一次调用）；调整堆的时间复杂度为lgnphp 排序算法，称为n-1次，因此堆排序的时间复杂度为O(nlgn)。

这个过程中需要很多图标才能看清楚，我比较懒。。。。。。

算法实现：

<?php
//堆排序（对简单选择排序的改进）
function swap(array &$arr,$a,$b){
 $temp = $arr[$a];
 $arr[$a] = $arr[$b];
 $arr[$b] = $temp;
}
//调整 $arr[$start]的关键字，使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆（根节点最大的完全二叉树）
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 （数组开始下标为 0 时）
function HeapAdjust(array &$arr,$start,$end){
 $temp = $arr[$start];
 //沿关键字较大的孩子节点向下筛选
 //左右孩子计算（我这里数组开始下标识 0）
 //左孩子2 * $start + 1，右孩子2 * $start + 2
 for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
  if($j != $end && $arr[$j] = $arr[$j]){
   break; //已经满足大根堆
  }
  //将根节点设置为子节点的较大值
  $arr[$start] = $arr[$j];
  //继续往下
  $start = $j;
 }
 $arr[$start] = $temp;
}
function HeapSort(array &$arr){
 $count = count($arr);
 //先将数组构造成大根堆（由于是完全二叉树，所以这里用floor($count/2)-1，下标小于或等于这数的节点都是有孩子的节点)
 for($i = floor($count / 2) - 1;$i >= 0;$i --){
  HeapAdjust($arr,$i,$count);
 }
 for($i = $count - 1;$i >= 0;$i --){
  //将堆顶元素与最后一个元素交换，获取到最大元素（交换后的最后一个元素），将最大元素放到数组末尾
  swap($arr,0,$i); 
  //经过交换，将最后一个元素（最大元素）脱离大根堆，并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
  HeapAdjust($arr,0,$i - 1);
 }
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);