PHP實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的排序算法

冒泡排序

【基本原理】

相鄰兩數(shù)依次比較，將小數(shù)放在前面，大數(shù)放在后面。第一趟結(jié)束，將最大的數(shù)放到了最后。第二趟結(jié)束，將最大的數(shù)放到了倒數(shù)第二。依次一直下去，直至最終完成排序。

冒泡排序，只需要使用兩重循環(huán)實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(n*n)。

【代碼實(shí)現(xiàn)】

實(shí)現(xiàn)：兩兩比較，把小的數(shù)放在前面

<?phpfunction bubble_sort($array){	if(!is_array($array))	{		return false;	}		$len=count($array);		for($i=0;$i < $len-1;$i++)	{		$flag = false;				for($j=0;$j < $len-$i-1;$j++)		{			if($array[$j] > $array[$j+1])			{				$temp=$array[$j];								$array[$j]=$array[$j+1];								$array[$j+1]=$temp;								$flag = true;			}		}		if(! $flag)//本趟排序沒(méi)有值交換，則提前終止程序  			return $array;	}}//調(diào)用實(shí)現(xiàn)$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);print_r(bubble_sort($array));?>

希爾排序

【基本原理】

         先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為d1

的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)

上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行

直接插入排序?yàn)橹埂?

【代碼實(shí)現(xiàn)】

實(shí)現(xiàn)：與增量間隔的數(shù)比較，直到把大的數(shù)放到最后

<?php/*** 數(shù)據(jù)結(jié)構(gòu)中希爾排序PHP實(shí)現(xiàn) ** 時(shí)間復(fù)雜度為 O(N*(logN)2)*/function shell_sort($array){	if(!is_array($array))	{		return false;	}		$len=count($array);		$d=$len;//隨機(jī)增量，初始值為數(shù)組長(zhǎng)度，以不斷除2取值		while($d >1)	{		$d=intval($d / 2);//分組間隔，2為n值，n值減少時(shí)，移動(dòng)的趟數(shù)和數(shù)據(jù)增多			$temp=NULL;			$j=0;			for($i=$d;$i < $len;$i+=$d)		{			if($array[$i] < $array[$i-$d])			{				$temp=$array[$i];								$j=$i-$d;								while(($j >=0) && $temp < $array[$j])				{					$array[$j+$d]=$array[$j];										$j = $j - $d;				}								$array[$j+$d]=$temp;			}		}	}	return $array;}$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);print_r(shell_sort($array));?>

選擇排序

【基本原理】

每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法。

【代碼實(shí)現(xiàn)】

實(shí)現(xiàn)：兩次循環(huán)，全部比較找出最小元素的key(數(shù)組中的索引)，判斷當(dāng)前數(shù)與最小值key，不相等即交換值

<?php/*** 數(shù)據(jù)結(jié)構(gòu)中選擇排序PHP實(shí)現(xiàn) ** 時(shí)間復(fù)雜度為 O(n2)*/function select_sort($array){	if(!is_array($array))	{		return false;	}		$len=count($array);		for($i=0;$i < $len;$i++)	{		$k=$i;				for($j=$i+1;$j < $len;$j++)		{			if($array[$k] > $array[$j])			{				$k=$j;			}		}		if($i!=$k){			$temp = $array[$i];        	$array[$i] = $array[$k];        	$array[$k] = $temp;		}	}	return $array;}$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);print_r(select_sort($array));?>

文章來(lái)源：http://meego123.net/?post=126

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)