前言
首先我們玩的是比較經典的選擇排序
選擇排序也是我們本系列的第一個O(n^2)演算法
很多人認為最優的演算法是O(n log n)級別的演算法
這樣就衍生出了一個問題
為什么要學習 O(n^2) 級別的演算法？
基礎：
O(n^2) 相對而言比較基礎，由簡入難，很多時候我們做專案，或者是做其他業務的時候，我們可能找不到最優的解決辦法，但是我們肯定會一種最簡單的辦法，我們先將功能實作，再進行優化，可能相對而言，會有一些性能上面的問題，但是隨著我們慢慢優化，我們也會慢慢找到新的，更優秀的方式
容易實作：
有些情況下，我們借用演算法的思想去做專案的時候，因為本身達不到 O(n log n) 級別，那么這個時候，我們可以選擇相對簡單，和容易實作的級別，如： O(n^2)
簡單有效：
某些特殊情況下，簡潔有效
由簡入難：
簡單的排序演算法思想，可以衍生出復雜的排序演算法，這也是我寫這個系列的原因，可能很多人，做了好幾年的業務，也不一定用到演算法，但是你的某些行為可能恰恰就是演算法思想
廢話不多說，直接開始了
插入排序，先簡單了解一下思路
首先我們有這么一段資料，我們需要將他們重新整合有序
| 7 | 2 | 1 | 5 | 4 | 6 | 9 | 3 | 8 |
第一次排序
- 用選擇排序的思路就是先找到，最小數
1
| 7 | 2 |1| 5 | 4 | 6 | 9 | 3 | 8 |
然后將現在的坐標 1 的數值進行一次交換
7進行交換位置1
經過此次交換后，得到以下資料，并且 1 也是最終位置
| 1 | 2 | 7 | 5 | 4 | 6 | 9 | 3 | 8 |
第二次排序
- 然后我們再找到此時的最小數
2
| 1 |2| 7 | 5 | 4 | 6 | 9 | 3 | 8 | - 我們發現
2, 就在最終位置，我們可以簡單一點，直接不動 - 經過此次交換后，得到以下資料，并且
2也是最終位置
| 1 |2| 7 | 5 | 4 | 6 | 9 | 3 | 8 |
第三次排序
- 然后我們繼續在當前資料中繼續尋找第三個，最小數
3，當前位置第一是7
| 1 | 2 |7| 5 | 4 | 6 | 9 |3| 8 | - 然后將現在的坐標
3的數值進行一次交換7進行交換位置3 - 此時資料是這樣的
| 1 | 2 |3| 5 | 4 | 6 | 9 |7| 8 |
第四次排序
- 然后我們繼續在當前資料中繼續尋找第四個，最小數
4，當前位置第一是5 5進行交換位置4- 此時資料是這樣的
| 1 | 2 | 3 |4|5| 6 | 9 |7| 8 |
此后一直以此類推，直至到底
實作一下代碼，第一步#
- 生成陣列，同時把生成陣列的耗時記錄一下
/** 記錄開始時間 */
$timeStart = millisecond();
/** 生成一個 100 的隨機陣列，從 1 開始到 100 */
$sort = generateSort($num,1,$num);
/** 記錄結束時間 */
$timeEnd = millisecond();
/** 結束時間 - 開始時間，以后不再申明 */
var_dump('生成陣列需要時間：'. ($timeEnd - $timeStart) . " / ms");
第二步
- 進行排序，同時把排序性能耗時記錄一下
tips： 在php當中，while要比for快一丟丟 - 至于為什么這里用
for，可能是博主不會用while吧
/**
* 選擇排序操作方法 - for
* @param $sort
* @param $n
* @return mixed
*/
function get_select_sort_for($sort,$n){
/** 將資料回圈一次 */
for($i = 0;$i < $n;$i++){
/** 尋找資料中的最小值，同時跨過第一個元素 */
for($j = $i + 1;$j < $n;$j++){
/** 通過回圈對比得到最小值 */
if($sort[$i] > $sort[$j]){
/**
* 將最小值和當前的第一個元素進行位置交換
* php 沒有位置交換的函式，所以簡單一點，先取出，再覆寫
*/
$item = $sort[$i];
$sort[$i] = $sort[$j];
$sort[$j] = $item;
}
}
}
return $sort;
}
while
/**
* 選擇排序操作方法 - while
* @param $sort
* @param $n
* @return mixed
*/
function get_select_sort_while($sort,$n){
$i = 0;
while($i < $n){
$j = $i + 1;
while($j < $n){
if($sort[$i] > $sort[$j]){
$item = $sort[$i];
$sort[$i] = $sort[$j];
$sort[$j] = $item;
}
$j++;
}
$i++;
}
return $sort;
}
第三步
- 驗證陣列是否正確，記錄時間
/** 記錄排序開始時間 */
$sortStart = millisecond();
/** 呼叫上面的排序方法 */
$result = get_select_sort_for($sort,$num);
/** 記錄排序結束時間 */
$sortEnd = millisecond();
var_dump('排序耗時：'. ($sortEnd - $sortStart) . " / ms");
/** 驗證是否有序 */
$msg = isSort($result) ? 'Yes':'No';
var_dump('排序是否正確 ? ：' . $msg);
var_dump('本次排序大小：'. $num);
第四步
- 基本就是這樣，簡簡單單的完成了，
- 如果有疑問，或者寫錯的地方，請在下面評論留言
- 大家加油
更多學習內容請訪問：
騰訊T3-T4標準精品PHP架構師教程目錄大全，只要你看完保證薪資上升一個臺階（持續更新）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/45107.html
標籤：PHP
下一篇：PHP7的Yaconf使用教程