@TOC
排序算法
常見的排序算法可以分為兩類：
- 比較類算法：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破 O(nlogn) 框仔，因此也稱為非線性時間比較類排比。
- 非比較類算法：不通過比較來決定元素間的相對次序鲫惶，它可以突破基于比較排序的時間下界习瑰，以線性時間運行，因此也稱為線性時間非比較類排序抡笼。
參考鏈接: O(1), O(n), O(logn), O(nlogn) 的區(qū)別
1.冒泡排序
冒泡算法是一種簡單的排序算法苏揣，通過不斷的相臨兩個元素的比較，每輪可以比較出最大的元素推姻，較小的元素慢慢移到前面平匈。
1.1 算法描述
- 相鄰元素比較，較大的元素后移藏古，繼續(xù)和后一個元素比較
- 每輪比較吐出一個最大的元素增炭，不參與下一輪比較
- 下一輪元素比較會比上一次少一次比較
- 最后一輪只剩兩個元素比較，完成排序
1.2 動圖演示
Alt
1.3 代碼實現(xiàn)
$arr = [2,22,3,88,5,333,88,90];
$count = count($arr);
for($i=0;$i<$count-1;$i++) { // 外層控制進行幾輪比較
for($j=0;$j<$count-$i-1;$i++){ // 內(nèi)層控制冒出來的元素要經(jīng)過幾輪比較
if($arr[$j]>$arr[$j+1]){
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}
}
}
2. 插入排序
插入排序是比較典型的高低個排隊拧晕，每次拿一個元素和前面的元素比較隙姿，插到合適的位置。
2.1 算法描述
- 取出第二個元素
- 跟前面的元素比較厂捞，直到找到比前面元素大的位置插入進去
- 繼續(xù)下一個元素输玷，直到最后一個元素找到插入位置，排序結(jié)束
2.2 動圖演示
Alt
2.3 代碼實現(xiàn)
$arr = [2,22,3,88,5,333,88,90];
$count = count($arr);
for($i=1;$i<$count;$i++){
$current = $arr[$i];
$preIndex = $i-1;
while($preIndex>=0 && $arrp[$preIndex]>$current) {
$arr[$preIndex+1] = $arr[$preIndex];
$preIndex--;
}
$arr[$preIndex+1] = $current;
}
3. 選擇排序
選擇排序就是尋找最小或者最大的數(shù)靡馁，假設第一個位置放最小的元素欲鹏，通過比較找到最小元素，和當前位置元素換位臭墨，依次執(zhí)行下去赔嚎。
3.1 算法描述
- 指定第一個位置存放最小元素
- 尋找最小元素所在的位置,和第一個位置的元素交換位置
- 繼續(xù)下一個最小元素選擇，
- 持續(xù)確定每一個位置的元素胧弛，到倒數(shù)第二個位置尤误，排序結(jié)束
3.2 動圖演示
Alt
3.3 代碼實現(xiàn)
$arr = [2,22,3,88,5,333,88,90];
$count = count($arr);
for($i=0;$i<$count-1;$i++) {
$minIndex = $i;
for($j=$i+1;$j<$count;$j++) {
if($arr[$i]<$arr[$minIndex]){
$minIndex = $i;
}
}
if($minIndex !== $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp
}
}
