1.1 插入排序
基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止.
<?php
function insert_sort($arr) { $count = count($arr); for ($i = 1; $i < $count; $i++) { $tmp = $array[$i]; $j = $i - 1; while ($array[$j] > $tmp) { $array[$j + 1] = $array[$j]; $array[$j] = $tmp; $j--; } } return $arr; }
|
1.2 选择排序
基本思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
<?php
function select_sort($arr) {
$count = count($arr); for ($i = 0; $i < $count; $i++) { $k = $i; for ($j = $i + 1; $j < $count; $j++) { if ($arr[$k] > $arr[$j]) { $k = $j; } } if ($k != $i) { $tmp = $arr[$i]; $arr[$i] = $arr[$k]; $arr[$k] = $tmp; } } return $arr; }
|
1.3 冒泡排序
基本思想:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。 排序过程:设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则(正序), 从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上”漂浮”,如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。
<?php
function bubble_sort($array){ $count = count($array); if ($count <= 0) return false; for($i=0; $i<$count; $i++){ for($j=$count-1; $j>$i; $j--){ if ($array[$j]<$array[$j-1]){ $tmp = $array[$j]; $array[$j] = $array[$j-1]; $array[$j-1] = $tmp; } } } return $array; }
|
1.4 快速排序
基本思想:在当前无序区R[1..H]中任取一个数据元素作为比较的”基准”(不妨记为X), 用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]和R[I 1..H],且左边的无序子区中数据元素均小于等于基准元素, 右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即R[1..I-1]≤X.Key≤RI 1..H, 当 R[1..I-1]和R[I 1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。
<?php
function quick_sort(&$array) { if (count($array) > 1) { $standard = $array[0]; $left = []; $right = []; $_size = count($array); for ($i = 1; $i < $_size; $i++) { if ($array[$i] <= $standard) { $left[] = $array[$i]; } elseif ($array[$i] > $standard) { $right[] = $array[$i]; } } $left = $this->quick_sort($left); $right = $this->quick_sort($right); return array_merge($left, array($standard), $right); } return $array;
}
|
1.5 希尔排序
基本思想:希尔排序是将待排序的数组元素 按下标的一定增量分组 ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序;然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。
<?php function shell_sort(&$arr){ if(!is_array($arr))return;$n=count($arr); for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){ for($i=$gap;$i<$n;++$i){ for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){ $temp=$arr[$j]; $arr[$j]=$arr[$j+$gap]; $arr[$j+$gap]=$temp; } } } }
|
.