先上堆排序代码:
<?php
$arr = [4,1,3,2,16,9,10,1,14,9,8,7,];//注意有重复值。
$arr = heap_sort($arr);
var_dump($arr);
//排序结果如下:
// [1,1,2,3,4,7,8,9,9,10,14,16,]
/**
* 从小到大 的排序。
*
* 1、初始化最大堆,把一维数组改变成映射为最大堆的一维数组。
* 2、把堆顶的最大值和堆最后一个结点交换。(于是最大值出现,并放好位置了。)
* 3、排除最后一个结点,把堆重新调整为最大堆。
* 4、把堆顶和倒数第2个结点交换。(于是次大值出现,也放好位置了。)
* 5、排除最后两个结点,把堆调整为最大推。
* 6、重复2和3,直到最后一个结点即堆顶。堆顶不需排,因为必然最小。
*
* @param array $arr
* @return array
*/
function heap_sort($arr) {
$len = count($arr);
//初始化,i從最後一個父節點開始調整
// 初始化的目的是建立一个最大堆。
// 要点是,必须自底向上,而不能自顶向下,否则bug。
for ($index = ceil($len/2) - 1; $index >= 0; $index--) {
max_heapify($arr, $index, $len);
}
// 推排序是很有规律的,先找出最大值,放到堆的最后,然后假装堆的结点数减少,
// 继续排序,找出次大的,等等。
// 巧妙利用堆和数组的映射,实现排序。
for ($index = $len - 1; $index > 0; $index--) {
$arr = swap ( $arr, 0, $index );
max_heapify($arr, 0, $index);
}
return $arr;
}
/**
* 堆排序核心算法,
* 对于一个给定的堆,给定的起始下标和结束下标,进行堆排序,会递归调用。
* 事实上,只排序起始下标指向的父节点,结束下标仅仅用于递归判断的返回。
* 这是指针形式的调用,这样的话,代码速度快,且代码容易理解。
*
* @param array $arr
* @param int $start_index
* @param int $end_index
*/
function max_heapify(&$arr, $start_index, $end_index) {
//建立父節點指標和子節點指標
$dad_index = $start_index;
$son_index = $dad_index * 2 + 1;
//若子節點指標超過範圍直接跳出函數
if ($son_index >= $end_index) {
return;
}
//先比較兩個子節點大小,選擇最大的
if ($son_index + 1 < $end_index && $arr[$son_index] < $arr[$son_index + 1]) {
$son_index++;
}
//如果父節點小於子節點時,交換父子內容再繼續子節點和孫節點比較
if ($arr[$dad_index] < $arr[$son_index]) {
$arr = swap($arr, $dad_index, $son_index);
max_heapify($arr, $son_index, $end_index);
}
}
/**
* 交换一个数组中两个不同下标的值。
* @param array $arr
* @param int $index1
* @param int $index2
* @return array
*/
function swap($arr, $index1, $index2) {
list( $arr[$index1], $arr[$index2] ) = [ $arr[$index2], $arr[$index1] ];
return $arr;
}
其实可以看到,堆排序代码并不算多,关键在于理解。
本文有参考:http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
作者不知是谁,描述的很清楚。
- 堆是一棵二叉数。
- 堆是一棵完全二叉数,于是,堆可以轻松用数组表达
- 假设下标是i,则父节点和子节点都有下标计算公式。
- 堆排序算法是先初始化成最大堆,然后交换堆顶和堆最后结点,然后结点数减1,再依次操作,就排序好了。
下图仅供参考,注意开始已经初始化过最大堆了。
- 大小: 299.2 KB
分享到:
相关推荐
#### 三、PHP实现堆排序的关键函数 根据提供的代码片段,我们可以看到实现堆排序的关键函数及其作用: - **`heapArray($arr)`**:该函数用于将数组转换为从索引1开始的堆结构,方便后续处理。 - **`Max_Heapify($i...
在PHP中实现堆排序,首先需要理解堆的构建过程。这里以降序排序为例,使用小顶堆。堆排序的基本步骤如下: 1. 初始化堆:将待排序的数组转换成一个合法的小顶堆。对于数组`$arr`,从倒数第二个非叶子节点(即`int...
PHP实现堆排序算法是一种有效的数据排序方法,其核心思想是利用数据结构中的堆这种数据结构进行排序,堆是一种特殊的完全二叉树结构。堆排序算法相对于其他排序算法(如简单选择排序)而言,它能够更有效地处理数据...
在 PHP 中,我们可以使用面向对象的编程思想来实现堆排序算法。 堆排序的原理 堆排序的原理是基于堆的性质。堆是一种特殊的二叉树,每个节点的值都小于或等于其子节点的值。在堆排序中,我们首先将待排序的数组...
根据给定文件的信息,我们可以详细地探讨三种不同的排序算法:冒泡排序(Bubble Sort)、快速排序(Quick Sort)以及堆排序(Heap Sort),并重点分析它们在PHP中的具体实现方式。 ### 一、冒泡排序 冒泡排序是一...
首先,排序算法是用来对一组数据进行排列的逻辑过程,它可以是升序或降序,常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。在PHP中,我们可以直接使用内置的`sort()`、`rsort()`、`a...
在PHP中实现堆排序首先需要理解堆的性质,即对于任意的非叶子节点i,其值要大于或等于其左右子节点的值(大顶堆)或小于或等于(小顶堆)。通过维护这种性质,堆排序算法可以实现高效的排序功能。 PHP堆排序的实现...
在PHP中,我们可以实现堆排序来对一组数值进行升序或降序排列。堆排序的主要步骤包括构建堆、交换堆顶元素和调整堆。 首先,我们需要理解堆的概念。堆通常是一个可以被视为一棵完全二叉树的数组对象,其中每个节点...
本资料包"用php实现几种常见的排序算法共6页.pdf.zip"聚焦于PHP如何实现几种经典的排序算法,这对于理解数据结构与算法以及提升PHP编程技能至关重要。排序算法是计算机科学中的基础,它们对大量数据进行有序排列,对...
PHP语言实现堆排序算法的过程中,需要定义一个交换函数swap用于交换数组中两个元素的值,以及一个HeapAdjust函数用于调整数组中某个子序列成为大根堆。建堆操作利用HeapAdjust函数从最后一个非叶子节点开始向上递归...
在实际应用中,更高效的排序算法如快速排序、归并排序或堆排序等会更为常见。然而,冒泡排序在教学和理解排序算法的基本概念上具有重要意义。 总结一下,这份"php-使用php开发的排序算法之BubbleSort-排序算法实现....
在实际开发中,我们通常会选择更高效的排序算法,如快速排序、归并排序或堆排序等。 了解并掌握冒泡排序算法有助于理解其他更复杂的排序算法,同时也能提升编程能力。在PHP开发中,虽然有内置的`sort()`和`asort()`...
4. 堆排序(Heap Sort):利用二叉堆的特性进行排序。首先构建最大堆,然后每次删除堆顶元素(即最大元素),将其放入结果数组,这样就能得到一个有序数组。 在PHP中,我们可以自定义一个二叉堆类,包含上述操作的...
冒泡排序是一种基础的排序算法,它...在实际应用中,更高效的排序算法如快速排序、归并排序和堆排序等通常会被优先考虑。然而,冒泡排序在某些特殊情况下,例如数组已经部分排序或者接近有序,其性能可以得到显著提升。
最后,堆调整是堆排序算法中的关键步骤,它通过反复交换子堆节点以调整子堆为大根堆(或小根堆)。调整过程是通过双亲节点和子节点之间的比较和交换来完成的,以保证子堆满足堆的性质。 以上七种排序算法在PHP中的...