1.1 插入排序

基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止.

<?php
/*
示例:
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
*/

function insert_sort($arr)
{
$count = count($arr);
//i=1 是从第二个开始与第一个比较
for ($i = 1; $i < $count; $i++) {
$tmp = $array[$i];
$j = $i - 1;
while ($array[$j] > $tmp) {
//前面的值大于后面的值时,互调位置,
//直到满足:$array[$j] > $tmp
$array[$j + 1] = $array[$j];
$array[$j] = $tmp;
$j--;
}
}
return $arr;
}

1.2 选择排序

基本思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

<?php
/*
初始关键字] [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97
*/

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,然后索引 $k 与 $i 值比较,
$k = $j;
}
}
//当最小值索引 $k与$i不同时, 索引$k与$i值互换位置,
if ($k != $i) {
$tmp = $arr[$i];
$arr[$i] = $arr[$k];
$arr[$k] = $tmp;
}
}
return $arr;
}

1.3 冒泡排序

基本思想:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。 排序过程:设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则(正序), 从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上”漂浮”,如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。

<?php
/*
示例:

49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
*/

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
/*
初始关键字 [49 38 65 97 76 13 27 49]
第一次交换后 [27 38 65 97 76 13 49 49]
第二次交换后 [27 38 49 97 76 13 65 49]
J向左扫描,位置不变,第三次交换后 [27 38 13 97 76 49 65 49]
I向右扫描,位置不变,第四次交换后 [27 38 13 49 76 97 65 49]
J向左扫描 [27 38 13 49 76 97 65 49]
(一次划分过程)
初始关键字 [49 38 65 97 76 13 27 49]
一趟排序之后 [27 38 13] 49 [76 97 65 49]
二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]
三趟排序之后 13 27 38 49 49 [65]76 97
最后的排序结果 13 27 38 49 49 65 76 97
*/

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;
}
}
}
}

.