VMware安裝Ubuntu實戰分享大綱

深入解析快速排序

一、分治策略分解
  1. 分解階段

    • 選擇基準元素 $pivot$
    • 將數組劃分為三個子集: $$ left = {x | x < pivot} $$ $$ equal = {x | x = pivot} $$ $$ right = {x | x > pivot} $$
  2. 遞歸排序

    • 對 left 和 right 子集遞歸調用快速排序
    • 遞歸終止條件:當子集長度 $\leq 1$ 時直接返回
  3. 合并結果: $$ sorted_arr = quick_sort(left) + equal + quick_sort(right) $$

二、時間復雜度分析
情況時間復雜度發生條件
最優$O(n \log n)$每次劃分完全平衡
最差$O(n^2)$輸入已排序+固定基準選擇
平均$O(n \log n)$隨機化基準選擇

數學推導(平均情況): $$ T(n) = 2T(\frac{n}{2}) + O(n) $$ 應用主定理可得 $T(n) = O(n \log n)$

三、基準選擇優化
  1. 隨機選擇法

    import random
    pivot_index = random.randint(0, len(arr)-1)
    arr[0], arr[pivot_index] = arr[pivot_index], arr[0]  # 交換到首位
    

  2. 三數取中法

    • 取首、中、尾三個元素
    • 選擇中間值作為基準
  3. 中位數法

    • 每9個元素為一組取中位數
    • 遞歸求取近似中位數
四、分區算法對比

Lomuto分區法

def partition(arr, low, high):pivot = arr[high]i = lowfor j in range(low, high):if arr[j] < pivot:arr[i], arr[j] = arr[j], arr[i]i += 1arr[i], arr[high] = arr[high], arr[i]return i

Hoare分區法(效率更高):

def partition(arr, low, high):pivot = arr[(low + high) // 2]i = low - 1j = high + 1while True:i += 1while arr[i] < pivot: i += 1j -= 1while arr[j] > pivot: j -= 1if i >= j: return jarr[i], arr[j] = arr[j], arr[i]

五、工程優化技巧
  1. 混合排序:當子數組長度 < 15 時切換為插入排序
  2. 尾遞歸優化:減少遞歸調用棧深度
  3. 重復元素處理:三向切分法(Dijkstra提出的荷蘭國旗問題解法)
    def quick_sort_3way(arr, low, high):if low >= high: returnlt, i, gt = low, low, highpivot = arr[low]while i <= gt:if arr[i] < pivot:arr[lt], arr[i] = arr[i], arr[lt]lt += 1i += 1elif arr[i] > pivot:arr[i], arr[gt] = arr[gt], arr[i]gt -= 1else:i += 1quick_sort_3way(arr, low, lt-1)quick_sort_3way(arr, gt+1, high)
    

六、空間復雜度分析
  • 最優情況:$O(\log n)$ (遞歸棧深度)
  • 最差情況:$O(n)$
  • 通過尾遞歸優化可將空間復雜度穩定在 $O(\log n)$
七、實際應用場景
  1. 內置排序算法實現(如Java的Arrays.sort())
  2. 大數據排序(結合外排序技術)
  3. 需要原地排序的場合(內存受限環境)
  4. 快速選擇算法(Top K問題)的基礎
八、穩定性分析

快速排序是不穩定的排序算法,改進方法:

def stable_quick_sort(arr):if len(arr) <= 1: return arrpivot = arr[0]return (stable_quick_sort([x for x in arr if x < pivot]) +[x for x in arr if x == pivot] +stable_quick_sort([x for x in arr if x > pivot]))

注:這種方法會破壞原地排序特性,但能保持穩定性

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/82797.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/82797.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/82797.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

AI 讓無人機跟蹤更精準——從視覺感知到智能預測

AI 讓無人機跟蹤更精準——從視覺感知到智能預測 無人機跟蹤技術正在經歷一場前所未有的變革。曾經,我們只能依靠 GPS 或簡單的視覺識別來跟蹤無人機,但如今,人工智能(AI)結合深度學習和高級視覺算法,正讓無人機的跟蹤變得更加智能化、精準化。 尤其是在自動駕駛、安防監…

GATED DELTA NETWORKS : IMPROVING MAMBA 2 WITH DELTA RULE

TL;DR 2024 年 Nvidia MIT 提出的線性Transformer 方法 Gated DeltaNet&#xff0c;融合了自適應內存控制的門控機制&#xff08;gating&#xff09;和用于精確內存修改的delta更新規則&#xff08;delta update rule&#xff09;&#xff0c;在多個基準測試中始終超越了現有…

Laravel單元測試使用示例

Date: 2025-05-28 17:35:46 author: lijianzhan 在 Laravel 框架中&#xff0c;單元測試是一種常用的測試方法&#xff0c;它是允許你測試應用程序中的最小可測試單元&#xff0c;通常是方法或函數。Laravel 提供了內置的測試工具PHPUnit&#xff0c;實踐中進行單元測試是保障代…

【FastAPI】--3.進階教程(二)

【FastAPI】--進階教程1-CSDN博客 【FastAPI】--基礎教程-CSDN博客 目錄 1.FastAPI - CORS ?2.FastAPI - CRUD 操作 2.1.Create 2.2.Read 2.3.Update 2.4.Delete 3.FastAPI - 使用 GraphQL 4.FastAPI - Websockets 5.FastAPI - 事件處理程序 6.FastAPI - 安裝 Fla…

FEMFAT許可的更新與升級流程

隨著工程仿真技術的不斷發展&#xff0c;FEMFAT作為一款領先的疲勞分析軟件&#xff0c;持續為用戶提供卓越的性能和創新的功能。為了保持軟件的最新性和高效性&#xff0c;了解FEMFAT許可的更新與升級流程至關重要。本文將為您詳細介紹FEMFAT許可的更新與升級流程&#xff0c;…

麒麟v10,arm64架構,編譯安裝Qt5.12.8

Window和麒麟x86_64架構&#xff0c;官網提供安裝包&#xff0c;麒麟arm64架構的&#xff0c;只能自己用編碼編譯安裝。 注意&#xff0c;“桌面”路徑是中文&#xff0c;所以不要把源碼放在桌面上編譯。 1. 下載源碼 從官網下載源碼&#xff1a;https://download.qt.io/arc…

20250528-C#知識:結構體

C#知識&#xff1a;結構體 結構體是一種自定義數據類型&#xff0c;用戶可以根據自身需求設計自己的結構體用來表示某種數據集合。結構體是一種值類型&#xff0c;結合了值類型的優點&#xff0c;避免了引用類型的缺點。本文簡單介紹并探究一下C#中的結構體。 結構體一般寫在命…

CRM系統的功能模塊劃分

基礎管理模塊 用戶管理 用戶注冊與登錄角色權限管理部門組織架構用戶信息管理 系統設置 基礎參數配置系統日志管理數據字典管理系統監控 客戶管理模塊 客戶信息管理 客戶基本信息客戶分類管理客戶標簽管理客戶關系圖譜 聯系人管理 聯系人信息聯系記錄溝通歷史重要日期提醒 …

Python中的跨域資源共享(CORS)處理

在Web開發中&#xff0c;跨域資源共享&#xff08;CORS&#xff09;是瀏覽器強制執行的安全機制&#xff0c;用于控制不同源&#xff08;協議域名端口&#xff09;之間的資源交互。下面我將通過Python示例詳細講解CORS的實現。 原生Python實現CORS Flask框架手動實現CORS fr…

Kruskal算法剖析與py/cpp/Java語言實現

Kruskal算法剖析與py/cpp/Java語言實現 一、Kruskal算法的基本概念1.1 最小生成樹1.2 Kruskal算法核心思想 二、Kruskal算法的執行流程三、Kruskal算法的代碼實現3.1 Python實現3.2 C實現3.3 Java實現 四、算法復雜度分析4.1 時間復雜度4.2 空間復雜度 五、Kruskal算法應用場景…

微信小程序返回上一頁監聽

本文實現的是微信小程序在返回上一頁時獲取通知并自定義業務。 最簡單的實現&#xff1a; 使用 wx.enableAlertBeforeUnload() 優點&#xff1a;快速接入 缺點&#xff1a;手勢不能識別、無法自定義彈窗內容&#xff08;僅詢問&#xff09; 方法二&#xff1a; page-conta…

Excel 統計某個字符串在指定區域出現的次數

【本文概要】 Excel 統計某個字符串在指定區域出現的次數&#xff1a; 1、Excel 統計一個單元格內的某字符串的出現次數 2、Excel 統計某一列所有單元格內的某字符串的出現次數 3、Excel 統計某一區域所有單元格內的某字符串的出現次數 1、Excel 統計一個單元格內的某字符串的出…

生物化學:藥品藥物 營養和補充劑信息 第三方認證信息 常見誤區 匯總

常見維生素和礦物質成分表 成分名稱好處副作用&#xff08;超量或敏感情況&#xff09;運作方式推薦日劑量&#xff08;成人&#xff09;劑量說明維生素A&#xff08;視黃醇&#xff09;視力、免疫、皮膚健康過量可致肝損傷、頭痛、脫發調節視網膜功能、細胞分化700–900 g RA…

mock庫知識筆記(持續更新)

文章目錄 mock簡介導入方式參數簡介使用場景&#xff08;待更新&#xff09;常見問題總結&#xff08;待更新&#xff09;Python代碼官網 mock簡介 mock是一個模擬對象庫&#xff0c;具有模擬其他python對象的功能&#xff0c;還能指定模擬對象的返回值和設置模擬對象的屬性。…

扇形 圓形 面積公式

? 一、圓的面積公式 全圓面積&#xff1a; A circle π r 2 A_{\text{circle}} \pi r^2 Acircle?πr2 ? 二、扇形的面積公式&#xff08;兩種制式&#xff09; 弧度制&#xff1a; A sector 1 2 r 2 θ A_{\text{sector}} \frac{1}{2} r^2 \theta Asector?21?r2θ …

怎樣將win11+ubuntu雙系統的ubuntu從機械硬盤遷移至固態硬盤(1)

將 Ubuntu 從機械硬盤遷移到固態硬盤是一個涉及多個步驟的過程。以下是一個基本的遷移指南&#xff1a; 1. 前期準備 1.1 備份數據&#xff1a; 確保你已備份數據&#xff0c;以防止在遷移過程中出現意外導致任何數據丟失。 1.2 固態硬盤安裝&#xff1a; 確保固態硬盤正確…

js中common.js和ECMAScript.js區別

以下是關于 CommonJS 和 ECMAScript Modules&#xff08;ESM&#xff09;的詳細對比分析&#xff0c;包含底層原理和示例說明&#xff1a; &#x1f9e9; 核心差異對比表 特性CommonJSES Modules來源Node.js 社區規范ECMAScript 語言標準加載方式動態加載&#xff08;運行時解…

玻纖效應的時序偏差

隨著比特率繼續飆升&#xff0c;光纖編織效應時序偏移正成為一個越來越嚴重的問題。對于 5GB/s 及以上的信號傳輸速率&#xff0c;它實際上會毀了您的一天。例如&#xff0c;左圖顯示由于 12.7 英寸的纖維編織效果&#xff0c;5GB/s 的接收眼完全閉合。使用 Agilent ADS 軟件進…

異步上傳石墨文件進度條前端展示記錄(采用Redis中String數據結構實現)

事件起因是客戶現場需要從石墨文檔中獲取文件信息&#xff0c;文件信息存在存在多個&#xff0c;進行批量上傳。為了用戶的友好型體驗&#xff0c;需要做進行條展示的方式&#xff0c;具體實現見下文… 上傳流程介紹 石墨文檔支持從鏈接&#x1f517;方式獲取文件信息&#xf…

3D建模的全景圖譜:從55個工具到元宇宙的數字革命

3D建模已從專業工程師的工具箱演變為全民創作的數字語言。從代碼驅動的精確建模到AI自動生成紋理&#xff0c;從開源協作到程序化生成城市&#xff0c;技術正重塑我們創造虛擬世界的方式。本文將系統解析55個核心3D建模工具/插件&#xff0c;涵蓋在線編輯器、開源軟件、程序化生…