# 【一】.冒泡排序
思路分析:
> 想象一個大水池里有N多還未排好的序列的氫氣球,較大的先冒出來,然后依次是較小的往上冒。即,每次比較相鄰的兩個數,小的在前大的在后,否則進行位置互換。
代碼實現:(舉例幾種寫法,注意循環體的判斷條件)建議使用第一、二種。
~~~
/**
* 交換方法
* @param array $arr 目標數組
* @param $a 索引a
* @param $b 索引b
* @param bool $flag 交換標志
* @return bool
*/
function swap(array &$arr,$a,$b,$flag = false){
// 遍歷i后面的元素,只要該元素小于當前元素,就把較小的往前冒泡
if($arr[$a] > $arr[$b]){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
$flag = true;
}
return $flag;
}
/**
* 第一種寫法
* @param $arr 所要排序的數組
* @return mixed 返回的數組
*/
function bubbleSort($arr) {
$len = count($arr);
if ($len <= 1) {return $arr;}
//該層循環控制 需要冒泡的輪數
for ($i = 0; $i < $len-1; $i++) {
//該層循環用來控制每輪 冒出一個數 需要比較的次數
for ($j = $i + 1; $j < $len; $j++) {
// 或者 $this->swap($arr,$j,$j+1);
$this->swap($arr,$i,$j);
}
}
return $arr;
}
//第二種寫法
public function BubbleSort2($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
for ($i = 0;$i < $len-1;$i++){
//TODO 本趟排序開始前,交換標志應為假
$flag = false;
for ($j = 0;$j <= $len-2;$j++){
$flag = $this->swap($arr,$j,$j+1,$flag);
}
if(!$flag) return $arr;
}
return $arr;
}
//第三種寫法
function BubbleSort3(array &$arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
for($i = 0;$i < $len-1;$i++){
//從后往前逐層上浮小的元素 $j >= 0
for($j = $len - 2;$j >= $i ;$j --){
$this->swap($arr,$j,$j+1);
}
}
return $arr;
}
//第四種寫法
function bubbleSort4($arr)
{
$len = count($arr);
if ($len <= 1) {return $arr;}
for($i = 0;$i < $len-1;$i++) {
for($j = 0;$j < $len-$i-1;$j++) {
$this->swap($arr,$j,$j+1);
}
}
return $arr;
}
~~~
小結:
> 時間復雜度:O(n^2)
> 補充:可使用PHP內置函數 sort()或rsort().
> 上述函數對索引數組按照鍵值進行排序,為 array 中的單元賦予新的鍵名,這將刪除原有的鍵名而不僅是重新排序。如果成功則返回 TRUE,否則返回 FALSE
# 【二】.選擇排序
思路分析:
> 每一次從待排序的數據元素中選出最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的數據元素排完
代碼實現
~~~
/*
* @param 選擇排序法
* 每一次從待排序的數據元素中選出最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的數據元素排完
* */
function selectSort($arr){
//雙重循環完成,外層控制輪數,內層控制比較次數
$len = count($arr);
if ($len <= 1) {return $arr;}
for ($i = 0; $i < $len-1; $i++) {
$minIndex = $i;
// 找出i后面最小的元素與當前元素交換
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$minIndex] > $arr[$j]){
$minIndex = $j;
}
}
if ($minIndex != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
return $arr;
}
~~~
小結:
> 時間復雜度:O(n^2)
> 不穩定的排序方法(比如序列[5, 5, 3]第一次就將第一個[5]與[3]交換,導致第一個5挪動到第二個5后面)。
> 在一趟選擇,如果一個元素比當前元素小,而該小的元素又出現在一個和當前元素相等的元素后面,那么交換后穩定性就被破壞了
> 最好情況是,已經有序,交換0次;最壞情況交換n-1次,逆序交換n/2次。交換次數比冒泡排序少多了,由于交換所需CPU時間比比較所需的CPU時間多,n值較小時,選擇排序比冒泡排序快
>
# 【三】.插入排序
思路分析:
> 每步將一個待排序的紀錄,按其關鍵碼值的大小插入前面已經排序的文件中適當位置上,直到全部插入完為止。(從而得到一個新的、個數加一的有序數據)
描述:
⒈ 從第一個元素開始,該元素可以認為已經被排序
⒉ 取出下一個元素,在已經排序的元素序列中從后向前掃描
⒊ 如果該元素(已排序)大于新元素,將該元素移到下一位置
⒋ 重復步驟3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復步驟 2~5

代碼實現
~~~
/*
* 插入排序法
* 每步將一個待排序的記錄,按其關鍵碼值的大小插入前面已經排序的文件中適當位置上,直到全部插入完為止。
* */
function insertSort($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默認$array[0],已經有序,是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是準備插入的數
$insertIndex = $i - 1; //有序表中準備比較的數的下標
while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){
$arr[$insertIndex + 1] = $arr[$insertIndex]; //將數組往后挪
$insertIndex--; //將下標往前挪,準備與前一個進行比較
}
if($insertIndex + 1 !== $i){
$arr[$insertIndex + 1] = $insertVal;
}
}
}
return $arr;
}
function insertSort2($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默認$array[0],已經有序,是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是準備插入的數
//$j 有序表中準備比較的數的下標
//$j-- 將下標往前挪,準備與前一個進行比較
for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){
$arr[$j+1]= $arr[$j];//將數組往后挪
}
$arr[$j + 1] = $insertVal;
}
}
return $arr;
}
~~~
小結:
> 時間復雜度:O(n^2)
> 空間復雜度:O(1) (用于記錄需要插入的數據)
> 穩定的排序方法
> 算法適用于少量數據的排序
> 如果比較操作的代價比交換操作大的話,可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種,稱為二分查找排序。
>
# 【四】.快速排序
思路分析:
> 通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,
> 然后再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列
>
代碼實現
~~~
/**
* @param $arr 目標數組
* @param int $l 左起坐標
* @param $r 右起坐標 初始化傳入數組時,$r = count($arr)-1
* @return mixed
*/
public function quick_sort(&$arr, $l=0, $r)
{
$length = count($arr);
//先判斷是否需要繼續進行 遞歸出口:數組長度為1,直接返回數組
if(!is_array($arr)||$length <= 1) {return $arr;}
if ($l < $r)
{
$i = $l;
$j = $r;
$baseVal = $arr[$l];
while ($i < $j)
{
// 從右向左找第一個小于$baseVal的數
while($i < $j && $arr[$j] >= $baseVal)
$j--;
if($i < $j)
$arr[$i++] = $arr[$j];
// 從左向右找第一個大于等于$baseVal的數
while($i < $j && $arr[$i] < $baseVal)
$i++;
if($i < $j)
$arr[$j--] = $arr[$i];
}
$arr[$i] = $baseVal;
$this->quick_sort($arr, $l, $i - 1); // 遞歸調用
$this->quick_sort($arr, $i + 1, $r);
return $arr;
}
}
/*
* 快速排序法
* */
public function quick_sort2($arr) {
$length = count($arr);
//先判斷是否需要繼續進行 遞歸出口:數組長度為1,直接返回數組
if(!is_array($arr)||$length <= 1) {return $arr;}
//選擇第一個元素作為基準
$baseValue = $arr[0];
//遍歷除了標尺外的所有元素,按照大小關系放入兩個數組內
//初始化兩個數組
$leftArr = array(); //小于基準的
$rightArr = array(); //大于基準的
//使用for循環進行遍歷,把選定的基準當做比較的對象
for($i = 1; $i<$length; $i++) {
if( $arr[$i] < $baseValue) {
//放入左邊數組
$leftArr[] = $arr[$i];
} else {
//放入右邊數組
$rightArr[] = $arr[$i];
}
}
//再分別對左邊和右邊的數組進行相同的排序處理方式遞歸調用這個函數
$leftArr = $this->quick_sort2($leftArr);
$rightArr = $this->quick_sort2($rightArr);
//合并 左邊 標尺 右邊, 注意:array($baseValue),關聯著重復數據
return array_merge($leftArr, array($baseValue), $rightArr);
}
~~~
小結:
> 既不浪費空間又可以快一點的排序算法
> 最差時間復雜度O(N^2),平均時間復雜度為O(NlogN)
>
# 【五】.計數排序
思路分析
> 計數排序使用一個額外的數組C,其中第i個元素是待排序數組A中值等于i的元素的個數。然后根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序
算法描述:
找出待排序的數組中最大和最小的元素;
統計數組中每個值為i的元素出現的次數,存入數組C的第i項;
對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加);
反向填充目標數組:將每個元素i放在新數組的第C(i)項,每放一個元素就將C(i)減去1

代碼實現
~~~
/**
* 計數排序
* @param $arr
* @return array
*/
function countingSort($arr)
{
$len = count( $arr );
if( $len <= 1 ) return $arr;
// 找出待排序的數組中最大值和最小值
$min = min($arr);
$max = max($arr);
// 計算待排序的數組中每個元素的個數
$countArr = array();
for($i = $min; $i <= $max; $i++)
{
$countArr[$i] = 0;
}
foreach($arr as $v)
{
$countArr[$v] += 1;
}
$resArr = array();
foreach ($countArr as $k=>$c) {
for($i = 0; $i < $c; $i++)
{
$resArr[] = $k;
}
}
return $resArr;
}
~~~
小結:
> 計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。
> 作為一種線性時間復雜度的排序,計數排序要求輸入的數據必須是有確定范圍的整數。
> 計數排序不是比較排序,排序的速度快于任何比較排序算法
> 最佳情況:T(n) = O(n+k)
> 最差情況:T(n) = O(n+k)
> 平均情況:T(n) = O(n+k)
>
# 【六】.桶排序
思路分析
> 假設輸入數據服從均勻分布,將數據分到有限數量的桶里,每個桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排)
算法描述
設置一個定量的數組當作空桶;
遍歷輸入數據,并且把數據一個一個放到對應的桶里去;
對每個不是空的桶進行排序;
從不是空的桶里把排好序的數據拼接起來。
代碼實現
~~~
/**
* 木桶排序設計
* @param $arr 目標數組
* @param int $bucketCount 分配的木桶數目(整數)
* @return array
*/
public function bucketSort($arr,$bucketCount = 10)
{
$len = count($arr);
$max = max($arr)+1;
if ($len <= 1) {return $arr;}
//填充木桶
$arrFill = array_fill(0, $bucketCount, []);
//開始標示木桶
for($i = 0; $i < $len ; $i++)
{
$key = intval($arr[$i]/($max/$bucketCount));
array_push($arrFill[$key] , $arr[$i]);
//TODO 測試發現:如果此處調用,耗時翻倍
/*if(count($arrFill[$key])){
$arrFill[$key] = $this->insertSort($arrFill[$key]);
}*/
}
//對每個不是空的桶進行排序
foreach ($arrFill as $key=>$f){
if (count($f)){
$arrFill[$key] = $this->insertSort($f);
}
}
//開始從木桶中拿出數據
for($i = 0; $i < count($arrFill); $i ++)
{
if($arrFill[$i]){
for($j = 0; $j <= count($arrFill[$i]); $j++)
{ //這一行主要用來控制輸出多個數字
if ($arrFill[$i][$j]){
$arrBucket[] = $arrFill[$i][$j];
}
}
};
}
return $arrBucket;
}
~~~
> 上述代碼是我根據對木桶排序的定義進行的設計,因為網上多數的PHP代碼感覺不合規范,其中的insertSort()為借用的文中所寫的插入排序
> 通過測試發現,此方法耗時比countingSort()要長好多,此處僅做參考不做推薦。
>
總結:
> 當輸入的元素是n 個0到k之間的整數時,它的運行時間是 O(n + k)。計數排序不是比較排序,排序的速度快于任何比較排序算法。由于用來計數的數組C的長度取決于待排序數組中數據的范圍(等于待排序數組的最大值與最小值的差加上1),這使得計數排序對于數據范圍很大的數組,需要大量時間和內存。
> 穩定的排序方法
> 桶排序是計數排序的升級版
> 最佳情況:T(n) = O(n+k)
> 最差情況:T(n) = O(n^2)
> 平均情況:T(n) = O(n+k)
- 序言
- 基礎知識
- thinkphp基礎知識
- Thinkphp5CURD
- 數據庫創建
- 數據庫刪除
- 數據庫更新
- 數據庫查詢
- thinkphp5控制器
- 空操作空控制器
- 控制器基類
- 請求信息
- 行為和鉤子
- thinkphp5路由設置
- 變量路由
- 常用方法清單
- 環境搭建
- lnmp
- 升級php
- window環境
- Thinkphp小案例
- 分類管理
- 數據庫設計
- 模型
- 控制器
- 視圖
- 文件上傳
- 上傳接口
- 視圖
- 表單提交
- 視圖設計
- 控制器
- 權限控制
- 案例解釋說明
- 登錄驗證
- Laravel5.3登錄模式
- redis使用
- 一鍵安裝
- 程序設計與實現
- 頁面設計
- 功能設計
- 安裝功能實際
- 函數庫
- 配置文件
- 清除緩存
- 狀態值修改
- 數據庫備份還原
- controller.php
- common.php
- index.html
- importlist.html
- 完整的增刪查改
- 查詢語句
- 多語言支持
- JpGraph圖表類庫
- 微信支付
- payBase.php
- Order.php
- Oauth.php
- Jspay.php
- 下載遠程地址中的圖片
- URL重寫隱藏入口文件
- 圖片水印
- 整合百度編輯器
- Ueditor
- ueditor完整配置項
- 配置信息常見的方式
- HTTP 斷點續傳(PHP實現)
- layui.upload上傳文件或圖片
- QQ微信域名防封 預防域名封禁 強制跳轉至瀏覽器
- 蜘蛛篇
- 超簡單實現php谷歌驗證
- 采集金山詞霸每日一句
- think-swoole
- 原生PHP小案例
- 查詢修改數據庫
- mysql支付回調源碼
- pdo連接微信退款
- 前端小案例
- html快捷查詢
- layui經驗總結
- layui 表單增強插件
- Vue列表Ajax實戰教程
- PHP基礎
- 類的自動載入
- php基礎函數- 字符串函數
- php基礎函數-數學函數
- php基礎函數-數組函數
- PHP常見排序算法學習
- 請求第三方
- 從網絡下載文件
- 檢查網站是否宕機
- file_get_contents
- 算法
- php 抽獎算法(適合九宮格和大轉盤)
- 自己動手豐衣足食
- 入口文件
- start.php
- app.php
- load.php
- route.php
- JqHttp
- Jqfile
- Jqutil
- pdo連接數據庫類
- 常見的php類
- php數據接口類
- 生成多層樹狀下拉選框的工具模型
- 上傳下載類
- 微信用戶相關類
- Zip壓縮類
- 列表樹生成工具類
- 日期時間操作類
- 文件及文件夾處理類
- 字符串處理類
- php守護進程類
- RSA算法類
- php支持中英文的加密解密類
- CURL多線程請求
- 通用數據庫操作類
- 緩存類
- cookie類
- 常見的驗證方法
- 隨機密鑰
- 日志Log
- php-redis 操作類 封裝
- OpensslRsa 加密、解密、簽名、驗簽類
- 模板輸出類
- 發送郵件
- 封裝的mysqli類
- PHP時間段分割類庫
- PHP apk解包識版本號信息和ipa包信息
- 訪問客戶端信息
- http請求
- PHP 無數據庫讀寫配置文件
- 自己動手寫一個jwt類
- php實現對圖片對稱加解密(適用身份證加密等場景)
- 常見php函數
- 無限分類
- 獲取文章圖片
- 加密解密
- JSON數據輸出(適合在tp中)
- 刪除目錄和文件
- 判斷是否為手機訪問
- 獲取客戶端真實IP
- 隨機生成ip地址
- 字符串與二進制進行轉換
- 對數組進行排序
- 格式化字節大小
- 時間戳格式化
- 獲取數據的所有子孫數據的id值
- 取得視頻文件的縮略圖
- 圖片裁剪函數
- 按照每過0:00算一天
- 下載文件
- PHP隨機密碼生成
- 判斷數字大小
- 報文組成
- 通過ip定位城市
- PDO方式連接MySQL數據庫
- 數組與xml
- php字符串處理函數
- 判斷是否ajax提交
- 生成概率,用于抽獎
- 斷點續傳
- PHP使用星號替代用戶名手機和郵箱
- 獲取毫秒級別的時間戳
- php日志函數
- 隨機顏色生成器
- 時間差異計算函數
- 黑名單過濾
- 常見PHP 正則表達式
- php獲取瀏覽器類型
- 郵件發送
- 獲取qq昵稱
- 正則獲取手機號歸屬地
- 判斷是否是移動客戶端 移動設備
- gbk和utf8編碼自動識別方法
- 人性化時間顯示
- 請求API接口
- 數據庫備份
- PHP并發下安全讀寫文件函數
- PHP讀取exe軟件版本號
- PHP為任意頁面設置訪問密碼
- PHP利用百度當圖床
- 秒/分鐘/小時前
- 常見的js函數
- 短信驗證函數
- 上下收縮菜單
- jQuery 樹插件zTree
- 頁面刷新跳轉
- jquery導出報表
- js實現定時效果
- 獲取當前經緯度
- JQuery實現圖片大小自適應
- 網站運行時間
- 判斷瀏覽器類型
- 百度推送
- js對指定數據進行排序
- 常見工具方法
- JSPinyin
- 技術相關文章
- 高級PHP工程師所應該具備哪些技能
- 最簡潔的PHP程序員學習路線及建議
- 優化PHP代碼的一些建議
- TP5性能優化建議
- 程序猿專用代碼注釋:佛祖保佑,永無BUG
- 一組匹配中國大陸手機號碼的正則表達式
- Apache/Nginx/PHP服務器反爬蟲代碼大全
- 番外
- 配置shadowsocks服務端
- python
- go
- 如何在1分鐘內黑掉任何網站!
- 百度貼吧敏感詞
- 貼吧手工養號發帖教程
- 搞笑的注釋代碼
- Heroku