PHP實現數據結構中的排序算法

 　　冒泡排序

　　【基本原理】

　　相鄰兩數依次比較，將小數放在前面，大數放在後面。第一趟結束，將最大的數放到了最後。第二趟結束，將最大的數放到了倒數第二。依次一直下去，直至最終完成排序。

　　冒泡排序，只需要使用兩重循環實現，時間復雜度為O(n*n)。

　　【代碼實現】

　　實現：兩兩比較，把小的數放在前面

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

　　?>

　　希爾排序

　　【基本原理】

　　先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1

　　的倍數的記錄放在同一個組中。先在各組內進行直接插入排序;然後，取第二個增量d2

　　上述的分組和排序，直至所取的增量dt=1(dt

　　直接插入排序為止。

　　【代碼實現】

　　實現：與增量間隔的數比較，直到把大的數放到最後

　　/**

　　* 數據結構中希爾排序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));

　　?>

　　選擇排序

　　【基本原理】

　　每一趟從待排序的數據元素中選出最小(或最大)的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

　　【代碼實現】

　　實現：兩次循環，全部比較找出最小元素的key(數組中的索引)，判斷當前數與最小值key，不相等即交換值

　　/**

　　* 數據結構中選擇排序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));

　　?>