数据结构——排序(php代码实现)
<?php/***BubbleSort0($arr):冒泡排序*BubbleSort1($arr):冒泡排序——优化*BubbleSort2($arr):冒泡排序——另一种实现方法*SelectSort($arr):选择排序*InsertSort($arr):插入排序*ShellSort($arr):希尔排序*/classSort{/***冒泡排序:指的是两两相邻的数据直接进行的比较交换排序*@param$arr要进行排序的数组*/publicstaticfunctionBubbleSort0($arr){for($i=0;$i<count($arr)-1;$i++){for($j=1;$j<count($arr);$j++){if($arr[$j-1]<$arr[$j]){//从大到小排序$temp=$arr[$j-1];$arr[$j-1]=$arr[$j];$arr[$j]=$temp;}}}return$arr;}//此算法是对上面算法的优化//避免了对已经有序的数据进行的比较publicstaticfunctionBubbleSort1($arr){$flag=true;for($i=0;$i<count($arr)-1&&$flag;$i++){$flag=false;for($j=1;$j<count($arr);$j++){if($arr[$j-1]<$arr[$j]){//从大到小排序$temp=$arr[$j-1];$arr[$j-1]=$arr[$j];$arr[$j]=$temp;$flag=true;}}}}//此算法,前面的一个数据依次与后面的所有数据进行比较,更加大小再进行交换。严格意义上不算是冒泡排序publicstaticfunctionBubbleSort2($arr){for($i=0;$i<count($arr)-1;$i++){for($j=$i+1;$j<count($arr);$j++){if($arr[$i]<$arr[$j]){$temp=$arr[$i];$arr[$i]=$arr[$j];$arr[$j]=$temp;}}}return$arr;}/***简单选择排序:就是先取出第一个(每次循环的第一个),假设其下标所在的数据时最小的,然后再依次与后面的数据比较找出最小的数据元素的下标,最后在进行交换。*@param$arr*/publicstaticfunctionSelectSort($arr){for($i=0;$i<count($arr)-1;$i++){$min=$i;//表示数组中最小值的下标for($j=$i+1;$j<count($arr);$j++){if($arr[$min]>$arr[$j]){//从小到大排列$min=$j;}}if($min!=$i){$temp=$arr[$min];$arr[$min]=$arr[$i];$arr[$i]=$temp;}}}/***直接插入排序:就是在一个有序的数据集合中,通过与集合中的元素进行比较,然后插入数据。*@param$arr*/publicstaticfunctionInsertSort($arr){for($i=1;$i<count($arr);$i++){$inserted=$arr[$i];//先假设数组只有一个元素并且默认它已经是有序的(因为只有一个嘛),然后取出第二个元素作为插入的元素//$j=$i-1:要插入元素的前一个数据元素下标//$j>=0&&$inserted<$arr[$j]:将当前要插入的元素依次与其前面的元素进行比较,若要插入的元素比其前面的元素小,那么其前面的元素就要往后移动一位,以为要插入的元素腾出位置for($j=$i-1;$j>=0&&$inserted<$arr[$j];$j--){$arr[$j+1]=$arr[$j];}$arr[$j+1]=$inserted;//表示要插入元素的位置下标为$j+1,因为for循环最后又执行了一次$j--,所以要把减去的1加上}return$arr;}/***希尔排序:将一个待排序的数组,分成若干子序列,然后分别对其进行排序,使其先部分有序,如此循环,最后得到有序数组。*它是对直接插入排序的一种改进。*@param$arr*@returnmixed*/publicstaticfunctionShellSort($arr){$count=count($arr);for($inc=floor($count/3);$inc>0;$inc=floor($inc/3)){for($i=$inc;$i<$count;$i++){$instered=$arr[$i];for($j=$i-$inc;$j>=0&&$instered<$arr[$j];$j-=$inc){$arr[$j+$inc]=$arr[$j];}$arr[$j+$inc]=$instered;}}return$arr;}}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。