TopCode之手撕快排

題目鏈接

912. 排序數組 - 力扣(LeetCode)

題目解析

算法原理

使用數組分三塊的思想

i用來遍歷整個數組

left用來標記<key的邊界

right用來標記>key的邊界

然后i進行遍歷,數組就分成了四塊

[l,left]<key

[left+1,i-1]==key

[i,right-1]未知

[right,r]>key

最后劃分完后就是[l,left]<key,[left+1,right-1]=key,[right,r]>key

分類討論

代碼編寫

class Solution {//交換void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}void quickSort(int[] nums, int l, int r) {if (r <= l) {//遞歸出口return;}int left = l - 1;int right = r + 1;int key = nums[(right + left) / 2];int i = l;while (i < right) {// 此時數組分成四塊[l,left]<key,[left+1,i]==key,[i+1,right-1]未知,[right,r]>keyif (nums[i] < key) {// 去左邊swap(nums, i++, ++left);} else if (nums[i] == key) {i++;} else {// 去右邊swap(nums, i, --right);}}// 處理左邊quickSort(nums, l, left);// 處理右邊quickSort(nums, right, r);}public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length - 1);return nums;}
}

注意

1> 必須有出口: l>=r

2> 去右邊不讓i++的原因是,right-1的位置是未知的,所有交換完后i下標的數是未知的,還沒有進行判斷

二刷

class Solution {void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}void quickSort(int[] nums, int l, int r) {// 處理遞歸出口if (l >= r) {return;}// left,right標記邊界int left = l - 1;int right = r + 1;// 中間值int key = nums[(right + left) / 2];// 遍歷int i = l;// 數組分成四塊[l,left]<key,[left+1,i-1]==key,[i,right-1]未知,[right,r]>keywhile (i < right) {if (nums[i] < key) {// 去左邊swap(nums, i++, ++left);} else if (nums[i] == key) {// 直接往后走i++;} else {// 去右邊swap(nums, i, --right);}}// 處理key的左邊quickSort(nums, l, left);// 處理key的右邊quickSort(nums, right, r);}public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length - 1);return nums;}
}

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

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

相關文章

bi軟件是什么?bi軟件是做什么用的?

目錄 一、BI 軟件是什么 1. 基本概念 2. 工作原理 二、BI 軟件是做什么用的&#xff1f; 1. 精準洞察市場趨勢 2. 優化企業戰略規劃 3. 輔助投資決策 三、如何選擇合適的 BI 軟件 1.功能匹配度 2.易用性和可擴展性 3.數據安全和穩定性 4.技術支持和服務 總結 生產…

11.14 LangGraph檢查點系統實戰:AI Agent會話恢復率提升287%的企業級方案

使用 LangGraph 構建生產級 AI Agent:LangGraph 持久化與記憶的"檢查點系統的實現" 關鍵詞:LangGraph 檢查點系統,多回合記憶,狀態持久化,會話恢復,AI Agent 容錯機制 1. 檢查點系統的核心價值 在復雜對話場景中,AI Agent 需要處理長達數十輪甚至數百輪的交…

鴻蒙完整項目-仿盒馬App(一)首頁靜態頁面

跟著鴻蒙小林博主&#xff0c;練習下項目~記錄下首頁的搭建,后續繼續完善和整體項目完成會進行布局修改&#xff0c;先按照博主的跟做&#xff0c;后續在改 1.分為底部整體框架搭建 2.首頁布局&#xff08;頂部搜索、新人專享、金剛區&#xff08;兩個不同集合數據&#xff09…

LINUX安裝運行jeelowcode后端項目(idea啟動)

參考 LINUX安裝運行jeelowcode后端項目&#xff08;命令行&#xff09;-CSDN博客 IntelliJ IDEA下載地址&#xff08;社區版、付費版&#xff09;-CSDN博客 軟件已安裝好&#xff0c;數據庫也初始化完畢。 步驟1&#xff1a;打開項目目錄步驟2&#xff1a;配置JDK步驟3&…

Web Vitals 核心指標快速掌握指南

Next.js 內置了對測量和報告性能指標的支持,我們可以通過 useReportWebVitals 鉤子自行管理報告。它會在應用的前端代碼開始之前運行,用于對應用進行全局分析、錯誤跟蹤以及性能監控。 本篇內容主要詳細介紹 6 個性能分析的指標,幫助我們更好的進行性能優化。 1. TTFB 定…

專業課復習筆記 10

感覺專業課就是考研的幾個科目里面難度最高的科目&#xff0c;我要好好加油&#xff0c;爭取拿下一百二十分。這個要是過不了線&#xff0c;考研基本廢完了。我感覺專業課練習題沒有說像是數學那么多練習題&#xff0c;反而是需要自己仔細去理解里面的知識&#xff0c;記住知識…

C語言 文件操作(2)

目錄 1.文件的順序讀寫 2.文件的隨機讀寫 3.文件讀取結束的判定 4.文件的緩沖區 1.文件的讀取順序 1.1 順序讀寫函數介紹 上面說的適用于所有輸入流一般指適用于標準輸入流和其他輸入流&#xff08;如文件輸入流&#xff09;&#xff1b;所有輸出流 一般指適用于標準輸出…

QGIS新手教程2:線圖層與多邊形圖層基礎操作指南(點線互轉、中心點提取與WKT導出)

QGIS新手教程&#xff1a;線圖層與多邊形圖層基礎操作指南&#xff08;點線互轉、中心點提取與WKT導出&#xff09; 目錄 QGIS新手教程&#xff1a;線圖層與多邊形圖層基礎操作指南&#xff08;點線互轉、中心點提取與WKT導出&#xff09;&#x1f4cc; 引言第一部分&#xff1…

Netty 框架介紹

1. Netty 框架介紹 Netty 是一個基于 Java NIO&#xff08;Non-blocking I/O&#xff09;的異步事件驅動網絡應用框架&#xff0c;旨在快速開發高性能、高可靠性的網絡服務器和客戶端。它簡化了 TCP/UDP 等協議的編程&#xff0c;并提供了高度可定制的組件&#xff0c;適用于高…

Eclipse 插件開發 5.2 編輯器 獲取當前編輯器

Eclipse 插件開發 5.2 編輯器 獲取當前編輯器 1 獲取活躍編輯器2 獲取全部編輯器 Manifest-Version: 1.0 Bundle-ManifestVersion: 2 Bundle-Name: Click1 Bundle-SymbolicName: com.xu.click1;singleton:true Bundle-Version: 1.0.0 Bundle-Activator: com.xu.click1.Activato…

完成LRU頁面調度算法的模擬

目錄 1.上代碼 2.實現思路 1.上代碼 #include<iostream> using namespace std; //內存塊類 class memory { public:void init();void alter(int a, int b);int check_full();int check_old();int check_exist(int a);void run();void refresh();friend int manage(me…

Three.js 直線拐角自動圓角化(圓弧轉彎)

目錄 前言 計算圓心坐標 計算兩條直線的角平分線 計算dir1 dir2的夾角 計算圓心到直線交點的距離 計算圓心 計算從正X軸算起曲線開始、終止的角度 計算垂足與兩直線交點距離 計算垂足 計算垂線 計算兩垂線與x軸的夾角 ?編輯 計算圓弧是否按照順時針方向來繪制 成功…

【MYSQL】mysql單表億級數據查詢優化處理

1、實踐表明mysql單表數據超過一億后&#xff0c;數據進行交并差效率會非常慢&#xff0c;所以這時候就要進行表的優化。 我這里主要是使用索引。 2、表字段精量精簡 查索引&#xff0c;建索引&#xff0c;刪索引語法 --查看索引 -- SHOW INDEX FROM 表名; -- 刪除索引 --AL…

C++基礎:模擬實現vector(有存在深層次的淺拷貝問題)

目錄 引言 一、vector的基本框架 二、尾插push_back、reserve擴容、任意位置插入insert&#xff08;增&#xff09; 1.reserve擴容 2.push_back尾插 3.深層次的淺拷貝問題 4. 任意位置插入數據insert(會使迭代器失效) 三、構造、析構、拷貝構造函數 1.構造函數 1.1無…

【力扣】關于鏈表索引

怎么才能走到目標節點呢&#xff1f; 從9走到2&#xff0c;需要2步&#xff0c;他們的索引分別是&#xff1a;0&#xff0c;2 在for循環里&#xff1a;int i 0; i < 2; i i的范圍是【0&#xff0c;2&#xff09; 有&#xff1a;2 2 - 0 如果從虛擬頭節點開始走到2&#x…

C++ ODB框架詳解:現代C++對象關系映射解決方案

目錄 框架簡介安裝與配置基礎概念實體映射數據庫操作查詢操作高級功能性能優化最佳實踐 框架簡介 ODB&#xff08;Object-Relational Database&#xff09;是一個專為C設計的對象關系映射&#xff08;ORM&#xff09;框架&#xff0c;由CodeSynthesis公司開發。它提供了一種…

Ai書簽管理工具開發全記錄(一):項目總覽與技術藍圖

文章目錄 Ai書簽管理工具開發全記錄&#xff08;一&#xff09;&#xff1a;項目總覽與技術藍圖 ?1. 項目背景與核心價值 &#x1f4a1;1.1. 核心特點 2. 技術架構分析 &#x1f3d7;?功能架構全景圖典型工作流 3. 核心技術棧選擇 &#x1f6e0;?4. 預期使用功能說明 &#…

GUI 編程——python

GUI 編程核心概念 GUI&#xff08;圖形用戶界面&#xff0c;Graphical User Interface&#xff09; 是一種通過圖形元素&#xff08;窗口、按鈕、菜單等&#xff09;與用戶交互的應用程序形式&#xff0c;相比命令行界面更直觀易用。以下是學習 GUI 編程的基礎概念和流程&…

【Doris基礎】Apache Doris 基本架構深度解析:從存儲到查詢的完整技術演進

目錄 1 引言 2 Doris 架構全景圖 2 核心組件技術解析 2.1 Frontend 層&#xff08;FE&#xff09; 2.2 Backend 層&#xff08;BE&#xff09; 3 數據存儲與復制機制 3.1 存儲架構演進 3.2 副本復制策略 4 查詢處理全流程解析 4.1 查詢生命周期 5 高可用設計 5.1 F…

光電賦能低空場景,靈途科技助力無人機持續升級

2025 UASE 主題為“步入低空經濟新時代”的“2025第九屆世界無人機大會暨國際低空經濟與無人系統博覽會/第十屆深圳國際無人機展覽會”5月23日在深圳會展中心隆重開幕。本屆展會匯聚了全球800余家企業參展&#xff0c;展示5000多款無人機及系統設備&#xff0c;全面呈現低空經…