PHP實作堆疊排序的方法詳解

黄舟
發布: 2023-03-06 17:48:02
原創
1580 人瀏覽過

堆的定義:

n個關鍵字序列Kl,K2,…,Kn稱為(Heap),當且僅當此序列滿足如下性質(簡稱為堆性質):(1) ki<=k(2i) 且ki<=k(2i+1)(1≤i≤n/2),當然,這是小根堆,大根堆則換成>=號。 k(i)相當於二元樹的非葉子結點,K(2i)則是左子節點,k(2i+1)是右子節點。若將此序列所儲存的向量R[1..n]看做是一棵完全二元樹的儲存結構,則堆疊實質上是滿足如下性質的完全二元樹:樹中任一非葉子結點的關鍵字均不大於(或不小於)其左右孩子(若有)結點的關鍵字。

/**
 * 调整堆
 * @param array $arr	排序数组
 * @param int $i    	待调节元素的下标
 * @param int $size 	数组大小, 准确来说是数组最大索引值加1
 */
function heapAjust(& $arr, $i, $size)
{
	$key = $arr[$i];
	// 索引从0开始
	// 左孩子节点为 2i+1, 右孩子节点为 2i+2
	for($j = 2 * $i + 1; $j < $size; $j = 2 * $j + 1) {
		if($j + 1 < $size && $arr[$j] < $arr[$j + 1])
			$j++;
		if($key > $arr[$j])
			break ;
		$arr[$i] = $arr[$j]; //调换值
		$i = $j;
	}
	$arr[$i] = $key;
}

/**
 * 堆排序
 * 时间复杂度:O(nlogn)
 * 不稳定的排序算法
 */
function heapSort(& $arr)
{
	$len = count($arr);
	
	// 构建初始大根堆
	for($i = intval($len/2); $i >= 0; $i--) {
		heapAjust($arr, $i, $len);
	}

	// 调换堆顶元素和最后一个元素
	for($j = $len - 1; $j > 0; $j--) {
		$swap = $arr[0];
		$arr[0] = $arr[$j];
		$arr[$j] = $swap;
		heapAjust($arr, 0, $j); //继续调整剩余元素为大根堆
	}
}
登入後複製

以上是PHP實作堆疊排序的方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板