一,插入排序
用文字簡單的描述,比如說$arr = array(4,2,4,6,3,6,1,7,9); 這樣的一組數字進行順序排序:
那麼,首先,拿數組的第二個元素和第一元素比較,假如第一個元素大於第二元素,那麼就讓兩者位置互換,接下來,拿數組的第三個元素,分別和第二個,第一個元素比較,假如第三個元素小,那麼就互換。依次類推。這就是插入排序,它的時間頻度是:1+2+...+(n-1)=(n^2)/2。則它的時間複雜度為O(n^2).
php實作碼如下:
Php代碼
=0&&$arr[$j]<$arr[$i]){ $arr[$i] = $arr[$j]; $arr[$j] = $tmp; $j--; } } return $arr; } ?>
二,選擇排序= array(4,3,5,2,1);
首先,拿第一個和後面所有的比,找出最小的那個數字,然後和第一個數組互換(當然,如果是第一個最小,那就不用互換了),接著循環,即:拿第二個和後面的比較,找出最小的數字,然後和第二個數字互換,依次類推,也就是說每次都是找出剩餘最小的值。 可得到:第一次,時間頻度是n, (第一個和後面的n-1個比較,找到最小的,再看是不是第一個,不是第一個的話進行互換) 在往後,依序是減一。它的時間複雜度,也是O(n^2);
php實作碼如下:
Php代碼
$arr[$j]){ $min = $j; //找到最小的那个元素的下标 } } if($min!=$i){//如果下标不是$i 则互换。 $tmp= $arr[$i]; $arr[$i] = $arr[$min]; $arr[$min] = $tmp; } } return $arr; } ?>
三,冒泡無明顯差別。都是找到最小的,放到最左端。依序循環解決問題。差異在於冒泡排序的交換位置的次數較多,而選擇排序則是找到最小的元素的下標,然後直接和最左端的交換位置。
php實作程式碼如下:
Php程式碼
$arr[$j]){ $tmp= $arr[$i]; $arr[$i] = $arr[$i]; $arr[$i] = $tmp; } } } return $arr; } ?>
快速排序,用語言來形容的話,從陣列中選擇一個值$a,然後和其餘元素進行比較,比$a大的放到數組right中,反之,放到數組left中。然後將left right 分別進行遞歸調用,即:再細分left right ,最後進行數組的合併。
php快速排序:
Php代碼
=$arr[$i]){ $left[] = $arr[$i]; }else{ $right[] = $arr[$i]; } } $left = mySort($left); $right = mySort($right); $result = array_merge($left,$right); return $result; } ?>
Php代碼
$right[0] ? array_shift($right) : array_shift($left); //进行比较,小的移除,并且放入到数组$m中。 } return arr_merge($m,$left,$right);//进行合并(由于不知道left right 哪个会为空,所以进行统一合并) } ?>