PHP implements sorting algorithm in data structure_PHP tutorial

Bubble sort

【Basic Principles】

Compare two adjacent numbers in order, put the decimal in front and the large number in the back. At the end of the first trip, the largest number was put to the end. At the end of the second pass, the largest number was placed second to last. Continue in sequence until the sorting is finally completed.

Bubble sorting only needs to be implemented using two loops, and the time complexity is O(n*n).

【Code Implementation】

Implementation: pairwise comparison, put the smaller number in front

<?php
function 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)//本趟排序没有值交换，则提前终止程序
  			return $array;
	}
}
//调用实现
$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);
print_r(bubble_sort($array));
?>

Hill sort

【Basic Principles】

First take an integer d1 less than n as the first increment, and divide all the records in the file into d1 groups. All distances are d1

Records that are multiples of

are placed in the same group. First perform direct insertion sorting within each group; then, take the second increment d2

The above grouping and sorting are performed until the increment dt=1 (dt

Direct insertion sorting.

【Code Implementation】

Implementation: Compare with the numbers at incremental intervals until the larger number is placed at the end

<?php
/**
* 数据结构中希尔排序PHP实现 
*
* 时间复杂度为 O(N*(logN)2)
*/

function shell_sort($array)
{
	if(!is_array($array))
	{
		return false;
	}
	
	$len=count($array);
	
	$d=$len;//随机增量，初始值为数组长度，以不断除2取值
	
	while($d >1)
	{
		$d=intval($d / 2);//分组间隔，2为n值，n值减少时，移动的趟数和数据增多
	
		$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));
?>

Select sort

【Basic Principles】

In each pass, the smallest (or largest) element is selected from the data elements to be sorted, and the order is placed at the end of the sorted sequence until all the data elements to be sorted are arranged. Selection sort is an unstable sorting method.

【Code Implementation】

Implementation: Two loops, compare all to find the key of the smallest element (index in the array), judge the current number and the minimum key, if they are not equal, exchange the values ​​

<?php
/**
* 数据结构中选择排序PHP实现 
*
* 时间复杂度为 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));
?>

Article source: http://meego123.net/?post=126

http://www.bkjia.com/PHPjc/363845.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/363845.htmlTechArticleBubble sorting [Basic principle] Compare two adjacent numbers in sequence, put the decimal in front and the large number in front later. At the end of the first trip, the largest number was put to the end. At the end of the second trip, the maximum...