PHP排序之插排、选排、冒泡、快排

直接插入排序:从数组中依次选取一个数与其所在位置前面的所有数比较(每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。)

直接选择排序:从数组中依次选取一个数与其所在位置后面的所有数比较(每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。)

冒泡排序:根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上”飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。

快速排序:采用分治法递归的将一个串行分为两个子串行。是对冒泡算法的一个改进。递归的操作:选择一个基准,将所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。

排序的稳定性:当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。在待排序的文件中,若存在多个关键字相同的记录, 经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不 稳定的。

时间复杂度:直接插入、直接选择和冒泡排序均为O(n2);快排为O(nlgn)。

PHP代码如下:



$list = array(3,4,7,6,44,1,2);

echo '待排序数组:';

print_r($list);

echo '';

//插入排序;

function insertSort($list){

	$count = count($list);

	if($count < 2) return $list;

	for($i = 1; $i < $count; $i++){

		$temp = $list[$i];

		for($j=$i-1;$j>-1;$j--){

			if($list[$j] > $temp){

				$list[$j+1] = $list[$j];

				$list[$j] = $temp;

			}

		}

	}

	return $list;

}

echo '插入排序:';

var_dump(insertSort($list));

//选择排序;

function selectSort($list){

	$count = count($list);

	if($count < 2) return $list;

	for($i=0; $i<$count; $i++){

		$k = $i;

		for($j=$i+1; $j<$count; $j++){

			if($list[$k] > $list[$j])

				$k = $j;

			if($k != $i){

				$temp = $list[$i];

				$list[$i] = $list[$k];

				$list[$k] = $temp;

				$k = $i;

			}

		}

	}

	return $list;

}

echo '选择排序:';

var_dump(selectSort($list));

//冒泡排序;

function bubbleSort($list){

	$count = count($list);

	if($count < 2) return $list;

	for($i=0; $i<$count; $i++){

		for($j=$count-1; $j>$i; $j--){

			if($list[$j] < $list[$j-1]){

				$temp = $list[$j];

				$list[$j] = $list[$j-1];

				$list[$j-1] = $temp;

			}

		}

	}

	return $list;

}

echo '冒泡排序:';

var_dump(bubbleSort($list));

//快速排序;

function quickSort($list){

	$count = count($list);

	if($count < 2) return $list;

	$key = $list[0];

	$left_list = array();

	$right_list = array();

	for($i=1; $i<$count; $i++){

		if($list[$i] < $key)

			$left_list[] = $list[$i];

		else

			$right_list[] = $list[$i];

	}

	$left_list = quickSort($left_list);

	$right_list = quickSort($right_list);

	return array_merge($left_list,array($key),$right_list);

}

echo '快速排序:';

var_dump(quickSort($list));

About 智足者富

http://chenpeng.info

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>