數(shù)據(jù)結(jié)構(gòu)_排序_快速排序

github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%8E%92%E5%BA%8F_%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.md

數(shù)據(jù)結(jié)構(gòu)_排序_快速排序

定義

  • 將任務(wù)進(jìn)行分割，然后各個(gè)擊破
  • 在某種特定的情況下，是最快的算法
  • 基本原理：
    • 設(shè)定一個(gè)基準(zhǔn)值（也就是軸）
    • 將比軸小的值，移到軸的左邊，形成左子數(shù)列
    • 將比軸大的值，移到軸的右邊，形成右子數(shù)列
    • 分別對(duì)左子數(shù)列和右子數(shù)列做上述三個(gè)步驟(遞歸)，直到左子數(shù)列或右子數(shù)列只剩一個(gè)值或沒有數(shù)值
  • 快速排序的效率：選擇的基準(zhǔn)值越接近數(shù)列平均值越好
  • 基準(zhǔn)值（軸）的選擇方式：
    • 固定位置：第一位，或者最后一位
    • 隨機(jī)選擇一位
    • 隨機(jī)取三個(gè)值，然后取中間值
  • 不穩(wěn)定算法

算法實(shí)現(xiàn)

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_fast_1.png" width="500" />

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_fast_2.png" width="500" />

代碼中，Partition函數(shù)實(shí)現(xiàn)了排序和形成左右子數(shù)列，是快速排序的關(guān)鍵，下圖展示了該函數(shù)第一次執(zhí)行的過程，便于大家理解快速排序

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_fast.png" width="400" />

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容