【數據結構】對快速排序原理的理解(圖解,通俗易懂)

學習數據結構時,書本上直接給出了快速排序的過程以及代碼,對其原理解釋的不夠詳細,琢磨代碼后,發現其原理其實十分簡單,簡述如下:

(1)在待排序列中找一個“中樞元素”(書本上默認取序列第一個元素)。
(2)通過操作,把比中樞元素大的數扔到中樞元素左邊,小的扔到右邊(假設要按降序排序)。
(3)將中樞元素左、右兩邊的子序列重復1,2過程。
(4)所有子序列長度為1時,排序結束。

那么怎么實現(2)中的“操作”呢?圖解如下:
假設序列為23,11,49,35,6,19.
在這里插入圖片描述
我們用low和high分別指向第一個元素和最后一個元素,同時我們取第一個數23為“中樞元素”,將它“挖”出來,如下:
在這里插入圖片描述
將23挖出來以后,最左邊就留下了一個“坑”,根據我們之前所說的,我們要把比中樞元素(23)大的扔到左邊,所以我們就要用high來找比23大的值,將它扔到之前在左邊挖好的坑里。現在,19比23小,19就不用動,因為我們本來就是要把比23小的數留在右邊。那么將high左移一位繼續,6也比23小,high再左移一位,發現35比23大,那么就把它填進左邊的坑里,如下:
在這里插入圖片描述
此時high所指的位置也留下了一個坑,那么我們就用low在序列頭部開始找比23小的數來扔到右邊,35比23大,low右移一位,發現11比23小,所以將11填到右邊的坑里,如下:
在這里插入圖片描述
繼續從high開始,往左找比23大的數,找到49,往左邊填坑,如下:
在這里插入圖片描述
繼續從low開始,往右邊找,發現此時 low與high相遇了,那么這個地方就是中樞元素“歸位”的位置,如下:
在這里插入圖片描述
好了,通過以上過程,我們已經將比23小的數扔到了右邊,大的數扔到了左邊。
此后,將以23為分界線的左右兩個子序列繼續重復此過程,直到所有子序列僅有一個元素為止,排序完成。

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

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

相關文章

【離散數學】圖論基礎知識

文章目錄1 圖的基本概念2 圖的連通性3 圖的矩陣表示4 幾種特殊的圖4.1 二部圖4.2 歐拉圖4.3 哈密頓圖4.4 平面圖5 無向樹6 生成樹1 圖的基本概念 無向圖: 簡而言之,邊不帶方向的圖就是無向圖。 有向圖: 簡而言之,邊帶方向的圖就…

【操作系統】信號量解決經典同步問題

文章目錄1. 基本結構2. P,V操作3. 信號量的應用3.1 信號量實現進程互斥3.2 信號量實現前驅關系4. 用信號量解經典同步問題4.1 生產者消費者問題4.2 讀者寫者問題4.3 狒狒過橋問題4.4 理發師理發問題4.5 哲學家進餐問題信號量機制是Dijkstra提出的一種卓有成效的進程同步工具。信…

【運籌與優化】單純形法解線性規劃問題(matlab實現)

文章目錄單純形法步驟:1.將線性規劃問題化為標準形式2.列出單純形表3.進行最優性檢驗4.從一個基可行解轉換到另一個目標值更大的基可行解,列出新的單純形表5.重復3、4直到計算結束為止舉例單純形法matlab實現單純形法是一種解線性規劃問題的算法&#xf…

【Linux系統編程學習】 GCC編譯器

此為牛客網Linux C課程1.2&1.3的課程筆記。 0. 簡介 1. gcc和g的安裝 sudo apt install gcc g2. gcc常用參數選項 3. gcc工作流程 首先是預處理器對源代碼進行預處理(后綴名.i),主要做以下事情: 把頭文件加入到源代碼當中刪…

Spring5底層原理之BeanFactory與ApplicationContext

目錄 BeanFactory與ApplicationContext BeanFactory ApplicationContext 容器實現 BeanFactory實現 ApplicationContext實現 ClassPathXmlApplicationContext的實現 AnnotationConfigApplicationContext的實現 AnnotationConfigServletWebServerApplicationContext的實…

【Linux系統編程學習】 靜態庫的制作與使用

此為牛客網Linux C課程 1.4&1.5 的課程筆記。 0. 關于靜態庫與動態庫 庫就是封裝好的、可服用的代碼,而靜態和動態是指鏈接。 這節課講的是靜態庫,是指在鏈接階段,會將匯編生成的目標文件.o與引用到的庫一起鏈接打包到可執行文件中&…

【Linux系統編程學習】 動態庫的制作與使用

此為牛客網Linux C課程1.6&1.7 的課程筆記。 1. 動態庫命名規則 2. 動態庫的制作 第一步,用gcc編譯生成.o目標文件,注意要用-fpic參數生成與位置無關的代碼; 第二步,用gcc的-shared參數生成動態庫。 涉及到的兩個參數之前學過…

【Linux系統編程學習】 靜態庫與動態庫的對比與總結

此為牛客網Linux C課程 1.9 的課程筆記。 1. 前幾節課知識總結 程序編譯成為可執行文件的過程: 靜態庫制作過程: 動態庫制作過程: 2. 靜態庫的優缺點: 3. 動態庫的優缺點: 更多可參考:吳秦&#xff1…

【Linux系統編程學習】 Makefile簡單入門

此為牛客網Linux C課程1.10&1.11&1.12 的課程筆記。 0. Makefile介紹 1. Makefile文件命名與規則 示例: 使用vim編寫如下名為Makefile的文件: app:sub.o add.o mult.o div.o main.ogcc sub.o add.o mult.o div.o main.o -o appsub.o:sub.cgcc …

【Linux系統編程學習】 GDB調試器的簡單使用

此為牛客網Linux C課程 1.13&1.14&1.15&1.16 的課程筆記。 0. GDB簡介 1. 準備工作 想要使用gdb調試,首先需要用gcc的-g參數生成可執行文件,這樣才能在可執行文件中加入源代碼信息以便調試,但是注意這并不是將源文件嵌入到可執行…

【Linux系統編程學習】C庫IO函數與系統IO函數的關系

此為黑馬Linux課程筆記。 1. C標準IO函數工作流程 如圖,以C庫函數的fopen為例,其返回類型是FILE類型的指針,FILE類型包含很多內容,主要包含三個內容:文件描述符、文件讀寫指針的位置和I/O緩沖區的地址。 文件描述符&…

【Linux系統編程學習】 文件描述符

此為牛客網Linux C課程1.19課程筆記。 1. 文件描述符表 如圖,我們知道每個進程都有其虛擬地址空間(0~4G),其中3 ~ 4G部分為內核區。進程的進程控制塊保存就在內核區,而PCB中維護一個打開文件描述符表,每個…

【Linux系統編程學習】Linux系統IO函數(open、read、write、lseek)

此為牛客網Linux C課程1.20課程筆記。 1.open函數 open函數有兩種&#xff0c;分別是打開一個已經存在的文件和創建并打開一個不存在的文件。 #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h>// 打開一個已經存在的文件 int open(const…

【Linux系統編程學習】Linux進程控制原語(fork、exec函數族、wait)

此為牛客Linux C和黑馬Linux系統編程課程筆記。 1. fork函數 1.1 fork創建單個子進程 #include<unistd.h> pid_t fork(void);作用&#xff1a;創建一個子進程。 pid_t類型表示進程ID&#xff0c;但為了表示-1&#xff0c;它是有符號整型。(0不是有效進程ID&#xff0…

【Linux系統編程學習】匿名管道pipe與有名管道fifo

此為牛客Linux C和黑馬Linux系統編程課程筆記。 0. 關于進程通信 Linux環境下&#xff0c;進程地址空間相互獨立&#xff0c;每個進程各自有不同的用戶地址空間。任何一個進程的全局變量在另一個進程中都看不到&#xff0c;所以進程和進程之間不能相互訪問&#xff0c;要交換…

【Linux系統編程學習】信號、信號集以其相關函數

此為牛客Linux C和黑馬Linux系統編程課程筆記。 文章目錄0. 信號的概念1. Linux信號一覽表2. 信號相關函數3. kill函數4. raise函數5. abort函數6. alarm函數7. setitimer函數8. signal函數9. 信號集10. 自定義信號集相關函數11. sigprocmask函數12. sigpending函數13. sigacti…

【Linux系統編程學習】父進程捕獲SIGCHLD信號以處理僵尸進程

配合之前說過的sigaction函數和waitpid函數&#xff0c;我們可以解決子進程變成僵尸進程的問題。 先看如下示例程序&#xff1a; #include <sys/time.h> #include <sys/types.h> #include <stdio.h> #include <stdlib.h> #include <signal.h> …

【Linux系統編程學習】Linux線程控制原語

此為牛客Linux C課程筆記。 0. 關于線程 注意&#xff1a;LWP號和線程id不同&#xff0c; LWP號是CPU分配時間片的依據&#xff0c;線程id是用于在進程內部區分線程的。 1. 線程與進程的區別 對于進程來說&#xff0c;相同的地址(同一個虛擬地址)在不同的進程中&#xff0c;反…

【Linux網絡編程學習】預備知識(網絡字節序、IP地址轉換函數、sockaddr數據結構)

此為牛客Linux C課程和黑馬Linux系統編程筆記。 1. 網絡字節序 我們已經知道&#xff0c;內存中的多字節數據相對于內存地址有大端和小端之分。 磁盤文件中的多字節數據相對于文件中的偏移地址也有大端小端之分。網絡數據流同樣有大端小端之分&#xff0c;那么如何定義網絡數…

【Linux網絡編程學習】socket API(socket、bind、listen、accept、connect)及簡單應用

此為牛客Linux C課程和黑馬Linux系統編程筆記。 1. 什么是socket 所謂 socket&#xff08;套接字&#xff09;&#xff0c;就是對網絡中不同主機上的應用進程之間進行雙向通信的端點的抽象。 一個套接字就是網絡上進程通信的一端&#xff0c;提供了應用層進程利用網絡協議交換…