# 排序算法
快速排序
選擇一個基準元素,通常選擇第一個元素或者最后一個元素。通過一趟掃描,將待排序列分成兩部分,一部分比基準元素小,一部分大于等于基準元素。此時基準元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分。
```
<pre class="calibre14">```
<span class="token5">function</span> <span class="token1">quicksort</span><span class="token2">(</span>$arr<span class="token2">)</span>
<span class="token2">{</span>
<span class="token6">//判斷參數是否是一個數組</span>
<span class="token5">if</span><span class="token2">(</span><span class="token">!</span><span class="token1">is_array</span><span class="token2">(</span>$arr<span class="token2">)</span><span class="token2">)</span> <span class="token5">return</span> <span class="token3">false</span><span class="token2">;</span>
<span class="token6">//遞歸出口:數組長度為1,直接返回數組</span>
$length <span class="token">=</span> <span class="token1">count</span><span class="token2">(</span>$arr<span class="token2">)</span><span class="token2">;</span>
<span class="token5">if</span><span class="token2">(</span>$length<span class="token"><=</span><span class="token3">1</span><span class="token2">)</span> <span class="token5">return</span> $arr<span class="token2">;</span>
<span class="token6">//數組元素有多個,則定義兩個空數組</span>
$left <span class="token">=</span> $right <span class="token">=</span> <span class="token1">array</span><span class="token2">(</span><span class="token2">)</span><span class="token2">;</span>
<span class="token6">//使用for循環進行遍歷,把第一個元素當做比較的對象</span>
<span class="token5">for</span><span class="token2">(</span>$i<span class="token">=</span><span class="token3">1</span><span class="token2">;</span> $i<span class="token"><</span>$length<span class="token2">;</span> $i<span class="token">++</span><span class="token2">)</span>
<span class="token2">{</span>
<span class="token6">//判斷當前元素的大小</span>
<span class="token5">if</span><span class="token2">(</span>$arr<span class="token2">[</span>$i<span class="token2">]</span><span class="token"><</span>$arr<span class="token2">[</span><span class="token3">0</span><span class="token2">]</span><span class="token2">)</span><span class="token2">{</span>
$left<span class="token2">[</span><span class="token2">]</span><span class="token">=</span>$arr<span class="token2">[</span>$i<span class="token2">]</span><span class="token2">;</span>
<span class="token2">}</span><span class="token5">else</span><span class="token2">{</span>
$right<span class="token2">[</span><span class="token2">]</span><span class="token">=</span>$arr<span class="token2">[</span>$i<span class="token2">]</span><span class="token2">;</span>
<span class="token2">}</span>
<span class="token2">}</span>
<span class="token6">//遞歸調用</span>
$left<span class="token">=</span><span class="token1">quicksort</span><span class="token2">(</span>$left<span class="token2">)</span><span class="token2">;</span>
$right<span class="token">=</span><span class="token1">quicksort</span><span class="token2">(</span>$right<span class="token2">)</span><span class="token2">;</span>
<span class="token6">//將所有的結果合并</span>
<span class="token5">return</span> <span class="token1">array_merge</span><span class="token2">(</span>$left<span class="token2">,</span><span class="token1">array</span><span class="token2">(</span>$arr<span class="token2">[</span><span class="token3">0</span><span class="token2">]</span><span class="token2">)</span><span class="token2">,</span>$right<span class="token2">)</span><span class="token2">;</span>
<span class="token2">}</span>
```
```
插入排序
在要排序的一組數中,假設前面的數已經是排好順序的,現在要把第n個數插到前面的有序數中,使得這n個數也是排好順序的。如此反復循環,直到全部排好順序。
```
<pre class="calibre14">```
<span class="token5">function</span> <span class="token1">insertsort</span><span class="token2">(</span>$arr<span class="token2">)</span>
<span class="token2">{</span>
$len<span class="token">=</span><span class="token1">count</span><span class="token2">(</span>$arr<span class="token2">)</span><span class="token2">;</span>
<span class="token5">for</span><span class="token2">(</span>$i<span class="token">=</span><span class="token3">1</span><span class="token2">;</span> $i<span class="token"><</span>$len<span class="token2">;</span> $i<span class="token">++</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//獲得當前需要比較的元素值。</span>
$tmp <span class="token">=</span> $arr<span class="token2">[</span>$i<span class="token2">]</span><span class="token2">;</span>
<span class="token6">//內層循環控制 比較 并 插入</span>
<span class="token5">for</span><span class="token2">(</span>$j<span class="token">=</span>$i<span class="token">-</span><span class="token3">1</span><span class="token2">;</span> $j<span class="token">>=</span><span class="token3">0</span><span class="token2">;</span> $j<span class="token">--</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//$arr[$i];//需要插入的元素; $arr[$j];//需要比較的元素</span>
<span class="token5">if</span><span class="token2">(</span>$tmp <span class="token"><</span> $arr<span class="token2">[</span>$j<span class="token2">]</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//發現插入的元素要小,交換位置</span>
<span class="token6">//將后邊的元素與前面的元素互換</span>
$arr<span class="token2">[</span>$j<span class="token">+</span><span class="token3">1</span><span class="token2">]</span> <span class="token">=</span> $arr<span class="token2">[</span>$j<span class="token2">]</span><span class="token2">;</span>
<span class="token6">//將前面的數設置為 當前需要交換的數</span>
$arr<span class="token2">[</span>$j<span class="token2">]</span> <span class="token">=</span> $tmp<span class="token2">;</span>
<span class="token2">}</span> <span class="token5">else</span> <span class="token2">{</span>
<span class="token6">//如果碰到不需要移動的元素</span>
<span class="token6">//由于是已經排序好是數組,則前面的就不需要再次比較了。</span>
<span class="token5">break</span><span class="token2">;</span>
<span class="token2">}</span>
<span class="token2">}</span>
<span class="token2">}</span>
<span class="token6">//將這個元素 插入到已經排序好的序列內。</span>
<span class="token6">//返回</span>
<span class="token5">return</span> $arr<span class="token2">;</span>
<span class="token2">}</span>
```
```
選擇排序
在要排序的一組數中,選出最小的一個數與第一個位置的數交換。然后在剩下的數當中再找最小的與第二個位置的數交換,如此循環到倒數第二個數和最后一個數比較為止。
```
<pre class="calibre14">```
<span class="token5">function</span> <span class="token1">selectsort</span><span class="token2">(</span>$arr<span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//$i 當前最小值的位置, 需要參與比較的元素</span>
<span class="token5">for</span><span class="token2">(</span>$i<span class="token">=</span><span class="token3">0</span><span class="token2">,</span> $len<span class="token">=</span><span class="token1">count</span><span class="token2">(</span>$arr<span class="token2">)</span><span class="token2">;</span> $i<span class="token"><</span>$len<span class="token">-</span><span class="token3">1</span><span class="token2">;</span> $i<span class="token">++</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//先假設最小的值的位置</span>
$p <span class="token">=</span> $i<span class="token2">;</span>
<span class="token6">//$j 當前都需要和哪些元素比較,$i 后邊的。</span>
<span class="token5">for</span><span class="token2">(</span>$j<span class="token">=</span>$i<span class="token">+</span><span class="token3">1</span><span class="token2">;</span> $j<span class="token"><</span>$len<span class="token2">;</span> $j<span class="token">++</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//$arr[$p] 是 當前已知的最小值</span>
<span class="token5">if</span><span class="token2">(</span>$arr<span class="token2">[</span>$p<span class="token2">]</span> <span class="token">></span> $arr<span class="token2">[</span>$j<span class="token2">]</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//比較,發現更小的,記錄下最小值的位置;并且在下次比較時,應該采用已知的最小值進行比較。</span>
$p <span class="token">=</span> $j<span class="token2">;</span>
<span class="token2">}</span>
<span class="token2">}</span>
<span class="token6">//已經確定了當前的最小值的位置,保存到$p中。</span>
<span class="token6">//如果發現 最小值的位置與當前假設的位置$i不同,則位置互換即可</span>
<span class="token5">if</span><span class="token2">(</span>$p <span class="token">!=</span> $i<span class="token2">)</span> <span class="token2">{</span>
$tmp <span class="token">=</span> $arr<span class="token2">[</span>$p<span class="token2">]</span><span class="token2">;</span>
$arr<span class="token2">[</span>$p<span class="token2">]</span> <span class="token">=</span> $arr<span class="token2">[</span>$i<span class="token2">]</span><span class="token2">;</span>
$arr<span class="token2">[</span>$i<span class="token2">]</span> <span class="token">=</span> $tmp<span class="token2">;</span>
<span class="token2">}</span>
<span class="token2">}</span>
<span class="token6">//返回最終結果</span>
<span class="token5">return</span> $arr<span class="token2">;</span>
<span class="token2">}</span>
```
```
冒泡排序
在要排序的一組數中,對當前還未排好的序列,從前往后對相鄰的兩個數依次進行比較和調整,讓較大的數往下沉,較小的往上冒。即,每當兩相鄰的數比較后發現它們的排序與排序要求相反時,就將它們互換
```
<pre class="calibre14">```
<span class="token5">function</span> bubbleSort <span class="token2">(</span>$arr<span class="token2">)</span>
<span class="token2">{</span>
$len <span class="token">=</span> <span class="token1">count</span><span class="token2">(</span>$arr<span class="token2">)</span><span class="token2">;</span>
<span class="token6">//該層循環控制 需要冒泡的輪數</span>
<span class="token5">for</span> <span class="token2">(</span>$i<span class="token">=</span><span class="token3">1</span><span class="token2">;</span> $i<span class="token"><</span>$len<span class="token2">;</span> $i<span class="token">++</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token6">//該層循環用來控制每輪 冒出一個數 需要比較的次數</span>
<span class="token5">for</span> <span class="token2">(</span>$k<span class="token">=</span><span class="token3">0</span><span class="token2">;</span> $k<span class="token"><</span>$len<span class="token">-</span>$i<span class="token2">;</span> $k<span class="token">++</span><span class="token2">)</span> <span class="token2">{</span>
<span class="token5">if</span><span class="token2">(</span>$arr<span class="token2">[</span>$k<span class="token2">]</span> <span class="token">></span> $arr<span class="token2">[</span>$k<span class="token">+</span><span class="token3">1</span><span class="token2">]</span><span class="token2">)</span> <span class="token2">{</span>
$tmp <span class="token">=</span> $arr<span class="token2">[</span>$k<span class="token">+</span><span class="token3">1</span><span class="token2">]</span><span class="token2">;</span> <span class="token6">// 聲明一個臨時變量</span>
$arr<span class="token2">[</span>$k<span class="token">+</span><span class="token3">1</span><span class="token2">]</span> <span class="token">=</span> $arr<span class="token2">[</span>$k<span class="token2">]</span><span class="token2">;</span>
$arr<span class="token2">[</span>$k<span class="token2">]</span> <span class="token">=</span> $tmp<span class="token2">;</span>
<span class="token2">}</span>
<span class="token2">}</span>
<span class="token2">}</span>
<span class="token5">return</span> $arr<span class="token2">;</span>
<span class="token2">}</span>
```
```
思路分析:希爾排序是基于插入排序的,區別在于插入排序是相鄰的一個個比較(類似于希爾中h=1的情形),
而希爾排序是距離h的比較和替換。
希爾排序中一個常數因子n,原數組被分成各個小組,每個小組由h個元素組成,很可能會有多余的元素。
當然每次循環的時候,h也是遞減的(h=h/n)。第一次循環就是從下標為h開始。
希爾排序的一個思想就是,分成小組去排序
```
<pre class="calibre16">```
<span class="token5">function</span> <span class="token1">shellsort</span><span class="token2">(</span>array $arr<span class="token2">)</span><span class="token2">{</span>
<span class="token6">// 將$arr按升序排列</span>
$len <span class="token">=</span> <span class="token1">count</span><span class="token2">(</span>$arr<span class="token2">)</span><span class="token2">;</span>
$f <span class="token">=</span> <span class="token3">3</span><span class="token2">;</span><span class="token6">// 定義因子</span>
$h <span class="token">=</span> <span class="token3">1</span><span class="token2">;</span><span class="token6">// 最小為1</span>
<span class="token5">while</span> <span class="token2">(</span>$h <span class="token"><</span> $len<span class="token">/</span>$f<span class="token2">)</span><span class="token2">{</span>
$h <span class="token">=</span> $f<span class="token">*</span>$h <span class="token">+</span> <span class="token3">1</span><span class="token2">;</span> <span class="token6">// 1, 4, 13, 40, 121, 364, 1093, ...</span>
<span class="token2">}</span>
<span class="token5">while</span> <span class="token2">(</span>$h <span class="token">>=</span> <span class="token3">1</span><span class="token2">)</span><span class="token2">{</span> <span class="token6">// 將數組變為h有序</span>
<span class="token5">for</span> <span class="token2">(</span>$i <span class="token">=</span> $h<span class="token2">;</span> $i <span class="token"><</span> $len<span class="token2">;</span> $i<span class="token">++</span><span class="token2">)</span><span class="token2">{</span> <span class="token6">// 將a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 (算法的關鍵)</span>
<span class="token5">for</span> <span class="token2">(</span>$j <span class="token">=</span> $i<span class="token2">;</span> $j <span class="token">>=</span> $h<span class="token2">;</span> $j <span class="token">-</span><span class="token">=</span> $h<span class="token2">)</span><span class="token2">{</span>
<span class="token5">if</span> <span class="token2">(</span>$arr<span class="token2">[</span>$j<span class="token2">]</span> <span class="token"><</span> $arr<span class="token2">[</span>$j<span class="token">-</span>$h<span class="token2">]</span><span class="token2">)</span><span class="token2">{</span>
$temp <span class="token">=</span> $arr<span class="token2">[</span>$j<span class="token2">]</span><span class="token2">;</span>
$arr<span class="token2">[</span>$j<span class="token2">]</span> <span class="token">=</span> $arr<span class="token2">[</span>$j<span class="token">-</span>$h<span class="token2">]</span><span class="token2">;</span>
$arr<span class="token2">[</span>$j<span class="token">-</span>$h<span class="token2">]</span> <span class="token">=</span> $temp<span class="token2">;</span>
<span class="token2">}</span>
<span class="token6">//print_r($arr);echo '<br/>'; // 打開這行注釋,可以看到每一步被替換的情形</span>
<span class="token2">}</span>
<span class="token2">}</span>
$h <span class="token">=</span> <span class="token1">intval</span><span class="token2">(</span>$h<span class="token">/</span>$f<span class="token2">)</span><span class="token2">;</span>
<span class="token2">}</span>
<span class="token5">return</span> $arr<span class="token2">;</span>
<span class="token2">}</span>
```
```
- 簡介
- 第一章 數據庫
- Mysql/mariadb
- 函數
- 基礎
- 增刪改索引
- 標準查詢
- 高級查詢
- TIDB集群mysql解決方案
- Redis
- 語言基礎
- 5種數據類型
- 其他類型
- Sqlite
- 語言基礎
- 常用查詢
- 第二章 PHP
- 語言基礎
- 第一課 流程控制和運算
- 第二課 數組
- 第三課 日期時間
- 第四課 常用函數
- 第五課 字符串
- 第六課 文件操作
- 第七課 面向對象
- 第八課 正則表達式
- 第九課 圖片處理生成
- 第十課 curl/memche
- 第十一課 mysql和pdo
- 第十三課 cookie和session
- 第十四課 xml操作
- 第十五課 php5.3+新特性
- 第十六課 php7+
- 第十七課 密碼安全
- 廢棄函數
- php命令行
- redis應用
- 算法
- 排序算法
- 基礎算法
- 無限級分類
- 自定義函數Fn
- 查找算法
- 自定義函數數據函數fn
- laravel
- 路由
- 常用語句
- 數據庫
- dingo/api
- Yii2
- 控制器
- 常用類
- 數據庫
- redis
- thinkphp6
- TP6文檔
- TP6插件
- dedecms
- 織夢標簽大全
- 數據庫操作
- 內置函數和定義函數
- 織夢核心改動
- 織夢插件/底層標簽開發
- PHP相關工具
- composer
- php開發環境phpenv
- Phpstorm使用
- windows編譯php擴展
- PHP開源庫
- 開源項目管理禪道
- sns_auth
- php-casbin權限控制
- php-jwt
- 微信SDKeasywechat
- querylist采集庫
- workerman
- Box/Spout處理excel和csv
- dll擴展
- redis/memche/xdebug
- redis
- Lua
- php_xlswriter
- event
- swoole
- 常用代碼庫
- 微擎框架
- 第一課全局變量
- 第二課常用函數
- 第三課自定義微擎獨有函數
- 第四課數據庫操作
- 第五課微信端回復
- 第六課微擎高級操作
- 第八課global函數列表
- mainfest.xml詳解
- js方法
- 人人商城
- 第一課model解讀
- 第二課常用語句解讀
- 第三課常用js解讀
- 第四課附錄常見問題
- 第五課附錄處理報表|支付
- 常用JSON狀態碼
- 第三章 JavaScript
- js基礎
- 瀏覽器對象
- 語言基礎
- html5接口
- ES6新語法
- vue
- 基礎語法
- 京東vueUI組件
- uniapp
- 組件開發規范
- nodejs
- 基礎知識
- 安裝node
- nvm不同版本node切換
- js常用標準庫
- zepto/jquery
- weui
- js圖標庫
- elementUI
- validator表單驗證
- layer彈出層
- requirejs
- wow動畫
- 動畫animate
- swiper4
- 百度編輯器
- flyio/axios/qs
- jquery.form
- bootstrap3
- clipboard復制
- slideout側滑
- imagehover.css圖片懸停動畫
- webpack打包
- Bulma UI框架
- store 客戶端存儲
- lottie動畫創建庫
- sweetalert
- js自定義函數
- 常見JSSDK
- 微信公眾號JSSDK
- 騰訊地圖jssdk
- 微信小程序
- 第四章 編程語言
- markdown語言
- Dart語言
- Dart語言基礎
- Flutter框架
- Lua語言
- 字符串,數組,表
- 自定義方法
- go語言
- 第1.1語言基本語法
- 第1.2流程控制
- 第1.3函數
- 第1.4結構體
- 第1.5接口
- 第1.6包
- go語言框架Gin
- CSS3語言
- CSS與CSS3
- 選擇符
- 屬性
- css3
- loading動畫
- HTML5語言
- less
- sass
- C#
- 基礎知識
- 函數
- 第五章 開發工具
- git
- nginx/apache服務器
- Linux常用操作
- crontab定時任務
- 注冊表與cmd
- 阿里云ECS
- frp穿透和ssl續期
- 寶塔安裝
- 樹莓派
- 瀏覽器模擬
- 火狐/chrome常用插件
- WSL安裝使用
- mac brew和終端命令
- win10相關