色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

以非遞歸的形式來寫快速排序

算法與數據結構 ? 來源:碼農的荒島求生 ? 作者:陸小風 ? 2022-11-08 17:01 ? 次閱讀

今天給大家講解一道非常有趣的算法面試題,以非遞歸的形式來寫快速排序

其實這也可以衍生出更多同類問題,非遞歸二叉樹的前序、中序、后序遍歷等等,這些問題的背后的思想是一致的,那就是用棧來手動模擬遞歸調用

道理很簡單有沒有,一句話就能說清楚,但問題是你真的理解了嗎?該怎樣用棧來手動模擬遞歸調用呢?你的大腦在面對這個問題時有一個清晰的思路嗎?

別著急,我們先從最簡單的快排開始。

快排,quick sort

快速排序想必大家都知道,我們以數組中的某個數字為基準,通常是數組的第一個或者最后一個(當然也可以是其它選擇方式),這里假設以數組的最后一個元素為基準:

7091ae22-5f3e-11ed-8abf-dac502259ad0.png

然后將數組中小于該基準的數字放在左邊、將大于該數字的放在右邊:

70afb958-5f3e-11ed-8abf-dac502259ad0.png

經過這一次處理后base就被放到了最終的位置上并得到了兩個子數組:base左邊的數組和base右邊的數組,以同樣的方式處理這兩個子數組即可。

用代碼表示就是這樣:

voidquick_sort(vector&arr,intb,inte){
if(b>=e)return;
inti=b-1;
for(intk=b;k

其中參數中的b和e表示begin和end,也就是范圍

可以看到,最終使用遞歸的方式編寫的代碼非常簡潔,也很容易理解,遞歸是計算機科學中一個極其重要的概念,遞歸對于理解編譯原理、編程語言、分而治之算法思想、排序以及動態規劃等等有重要的意義

遞歸版本很簡單有沒有,如果讓你用非遞歸的方式來實現呢

非遞歸手寫快速排序

想一想這個問題!如果你真正理解遞歸的話那么就應該能寫出來。

我們再來看看這個遞歸寫法。

首先會得到一個問題quick_sort(arr, b, e),我們利用base進行一次劃分后得到兩個子問題:

quick_sort(arr, b, i - 1)

quick_sort(arr, i + 1, e)

在遞歸版本中這兩個子問題的狀態(所謂的狀態就是要解決哪個子問題,這里用參數中的begin和end來界定)是隨著函數的調用自動保存在棧幀中的,而我們需要用棧這種數據結構來模擬這個過程。

接下來,我們用變量task來表示要處理的子問題,也就是說入棧出棧的都是task,task可以這樣定義:

pair

表示要對哪一段數組進行排序,因此使用了pair來記錄這段數組的開始和結尾。

由于需要使用棧來追蹤問題的解決順序,因此我們最終這樣定義棧:

stack>tasks;

一切準備就緒,是時候創建些任務了,任務的起源是什么呢?很簡單,就是數組本身:

intsize=arr.size();
tasks.push(pair(0,size-1));

接下來就是最重要的部分了:

while(!tasks.empty()){
//取出棧頂元素
//處理
//是否有新的子任務需要push到棧中
}

整體的框架就是這樣,接下來的三個問題就是:

取出棧頂元素

處理

是否有新的子任務需要push到棧中,如果有則push到棧中

第一個問題很簡單,沒什么可說的;第二個問題是說我們該怎樣處理一個子問題,其實也很簡單,就是用base將數組劃分為兩個子數組。

第三個問題是重點,我們該怎么知道接下來是否有新的子任務需要push到棧中呢?

想一想這個問題。。。

如果用base對數組進行劃分后發現數組已經是有序的那么就沒有必要創建子任務了,因為當前的數組已經有序了嘛!否則我們就需要創建子任務。

因此我們必須知道對數組進行劃分后數組是不是已經排好序。

基于上述討論,我們可以這樣實現劃分函數partition:

intpartition(vector&arr,intb,inte,bool*sorted){
if(b>e||b==e)return-1;

inti=b-1;
for(intj=b;j

這其實和開始遞歸版本中quick_sort函數里的劃分部分代碼沒什么區別,變化的部分僅在于我們將一次劃分后base所在的下標以及判斷一次劃分后數組是否有序記錄在參數sorted中

一次劃分后如果sorted的值為true也就是數組已經有序那么我們無需再創建新的子問題,一次劃分后我們得到兩個新的更小的子問題,即:

boolsorted=true;
intp=partition(arr,top.first,top.second,&sorted);

if(sorted){
continue;
}else{
tasks.push(pair(p+1,top.second));
tasks.push(pair(top.first,p-1));
}

所有問題分析完畢,完整的代碼為:

voidquick_sort(vector&arr){
intsize=arr.size();
if(size==0||size==1)return;
stack>tasks;
tasks.push(pair(0,size-1));

intb=0;

while(!tasks.empty()){
autotop=tasks.top();
tasks.pop();

boolsorted=true;
intp=partition(arr,top.first,top.second,&sorted);

if(sorted){
continue;
}else{
tasks.push(pair(p+1,top.second));
tasks.push(pair(top.first,p-1));
}
}
}

運行一下,it works like magic,有沒有!

這段代碼是怎樣運行的?

No,其實一點都不magic,接下來我們仔細看看這段代碼是怎么運行的。

假設當前棧頂元素為(2,9),我們獲取棧頂元素,并將其從中pop掉:

70f63d60-5f3e-11ed-8abf-dac502259ad0.png

此時我們要對數組下標2到9的元素進行排序,把末尾的base作為基準進行劃分:

71187c36-5f3e-11ed-8abf-dac502259ad0.png

假設劃分后base放到了下標為5的位置,這樣我們得到了兩個子問題(2,3)以及(4,9):

713b77c2-5f3e-11ed-8abf-dac502259ad0.png

由于經過base的劃分后我們判斷出該數組不是有序的(partition函數中sorted參數的作用),因此我們需要將兩個子問題(2,3)以及(4,9)放到棧中:

715f5ade-5f3e-11ed-8abf-dac502259ad0.png

就這樣,我們解決了子任務(2,9),并得到了兩個更小的子問題(2,3)以及(4,9),接著while循環繼續從棧中彈出任務并重復上述過程,當棧為空時我們一定能確信數據已經有序了。

這個過程“完全”模擬了上述遞歸函數的調用,這里之所以加了引號,是因為我們的迭代快排版本進行了一點點小小的優化,這個優化是什么呢?

尾遞歸

依然假設遞歸調用到函數quick_sort(2,9),此時的函數棧幀為:

717f73e6-5f3e-11ed-8abf-dac502259ad0.png

基于base劃分后依然得到:

713b77c2-5f3e-11ed-8abf-dac502259ad0.png

根據遞歸版本的quick_sort實現接著我們需要調用quick_sort(2,3),此時的棧幀為:

71bb9722-5f3e-11ed-8abf-dac502259ad0.png

看到非遞歸版本與遞歸版本的不同了吧:

728a3cbc-5f3e-11ed-8abf-dac502259ad0.png

在非遞歸版本下,對處理子任務(2,9)時會將該任務從棧中pop出來,而遞歸版本則不會pop出quick_sort(2,9)的棧幀,函數quick_sort(2,3)執行完后還會再次回到函數quick_sort(2,9),然后接著調用函數quick_sort(4,9)。

而之所以非遞歸實現可以提前將子任務(2,9)從棧中彈出是因為遞歸版本下所有遞歸調用都位于函數的末尾,這就是所謂的“尾遞歸”。

尾遞歸是一種比較常見的現象,二叉樹的前序遍歷遞歸實現也是這樣:

voidtree_travel(Tree*t){
if(t){
print(t->value);
tree_travel(t->left);
tree_travel(t->right);
}
}

你可以使用和本文一樣的套路將上述遞歸代碼轉為非遞歸代碼,但是如果是二叉樹的中序遍歷或者后序遍歷呢?

voidtree_travel(Tree*t){
if(t){
tree_travel(t->left);
print(t->value);
tree_travel(t->right);
}
}

此時,本文中講解的套路就失效了,因此我們需要一種更加通用的方法將此類非尾遞歸代碼轉為遞歸代碼,這種通用的方法是什么呢





審核編輯:劉清

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 算法
    +關注

    關注

    23

    文章

    4607

    瀏覽量

    92840

原文標題:字節一面:非遞歸手寫快速排序

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    FPGA排序-冒泡排序介紹

    排序算法是圖像處理中經常使用一種算法,常見的排序算法有插入排序、希爾排序、選擇排序、冒泡排序、歸
    發表于 07-17 10:12 ?1082次閱讀
    FPGA<b class='flag-5'>排序</b>-冒泡<b class='flag-5'>排序</b>介紹

    matlab實現快速排序法(原創)

    使用快速排序法進行排序,本以為很簡單就可以實現,但搜索了一下help文檔,只有C中的qsort存在,況且調用比較麻煩,其實在數據結構中,快速排序
    發表于 08-15 11:33

    matlab快速排序算法實現

    只有C中的qsort存在,調用比較麻煩,其實在數據結構中,快速排序法是經典排序之一,上網搜了一下簡介,把對應的VC程序改了一下,做成了下面的matlab代碼:%快速
    發表于 02-29 15:58

    快速排序

    // 快速排序package algorithmsimport "fmt"http:// 第一種寫法func quickSort(values []int, left, right int
    發表于 10-17 19:05

    簡述計算機排序

    不用交換,低指針指向的小于樞軸的元素不用交換。直到高低指針指向小于等于或者大于等于的元素后直接交換元素。一趟過后,在低子分區和高子分區中繼續進行遞歸快速排序方式。(一種優化方法是三位選中,第二種是在最后高低分區中,high –
    發表于 12-26 23:07

    《C Primer Plus》讀書筆記——遞歸

    必須包含可以終止遞歸調用的語句(如if)。尾遞歸最簡單的遞歸形式。把遞歸調用語句放在函數結尾(return語句之前)。舉個栗子: 計算n的階
    發表于 02-05 20:06

    數組快速排序及索引vi

    分享一個數組快速排序及索引的vi,lv里面的某些集成功能vi還是比較好用的,善于調用的話可以節約大家的編寫時間。
    發表于 05-06 09:11

    C#實現快速排序

    快速排序法是對冒泡排序的一種改進。它的基本思想是,通過一趟排序將待排序記錄分割成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分記錄的關鍵字
    發表于 08-09 17:57 ?16次下載

    快速排序是一種交換排序

    快速排序在每次分割的過程中,需要 1 個空間存儲基準值。而快速排序的大概需要 Nlog2N次的分割處理,所以占用空間也是 Nlog2N 個。
    的頭像 發表于 07-27 14:49 ?2911次閱讀
    <b class='flag-5'>快速</b><b class='flag-5'>排序</b>是一種交換<b class='flag-5'>排序</b>

    C語言排序快速排序的技巧

    快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下,排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較,但這種狀況并不常見。事實上,
    的頭像 發表于 07-29 15:14 ?2478次閱讀
    C語言<b class='flag-5'>排序</b>中<b class='flag-5'>快速</b><b class='flag-5'>排序</b>的技巧

    所有遞歸代碼都可以轉為遞歸代碼

    之所以所有的遞歸都能轉為迭代算法是因為遞歸借助函數調用,函數調用本身就是基于調用棧這種結構實現的,只不過這一切都是自動完成的,我們當然也可以用代碼手動模擬出來。
    的頭像 發表于 04-19 15:02 ?2083次閱讀

    遞歸代碼都轉為遞歸可以嗎

    之所以所有的遞歸都能轉為迭代算法是因為遞歸借助函數調用,函數調用本身就是基于調用棧這種結構實現的,只不過這一切都是自動完成的,我們當然也可以用代碼手動模擬出來。
    的頭像 發表于 02-17 14:35 ?744次閱讀
    <b class='flag-5'>遞歸</b>代碼都轉為<b class='flag-5'>非</b><b class='flag-5'>遞歸</b>可以嗎

    2分鐘看懂快速排序的算法

    之前有同學提出想要復習一下排序算法,那我們今天就挑一個難度中等的,快速排序
    的頭像 發表于 02-25 09:32 ?816次閱讀

    排序算法有哪些

    1. 歸并排序遞歸版) 歸并排序(MERGE-SORT)是利用歸并的思想實現的排序方法,該算法采用經典的分治策略,即分為兩步:分與治。 分:先遞歸
    的頭像 發表于 10-11 15:49 ?605次閱讀
    <b class='flag-5'>排序</b>算法有哪些

    遞歸神經網絡結構形式主要分為

    遞歸神經網絡(Recurrent Neural Networks,簡稱RNN)是一種具有時間序列處理能力的神經網絡,其結構形式多樣,可以根據不同的需求進行選擇和設計。本文將介紹遞歸神經網絡的幾種主要
    的頭像 發表于 07-05 09:32 ?518次閱讀
    主站蜘蛛池模板: jzz大全18| 香港成人社区| 99爱在线观看精品视频| 韩国电影久久| 亚洲精品不卡视频| 国产一区二区三区四区五在线观看| 色狠狠一区二区| qvod 艺术片| 日本福利片午夜免费观着| 3dbdsm变态videos高清| 久色视频网| 最新国产亚洲亚洲精品视频| 久久久久久天天夜夜天天| 伊人久久艹| 快播可乐网| 97午夜精品| 农村脱精光一级| jizz非洲| 乳女教师欲乱动漫无修版动画 | 亚洲免费无码av线观看| 国产最新地址| 又硬又粗又大一区二区三区视频| 久久精品国产亚洲AV忘忧草蜜臀| 又紧又大又爽精品一区二区| 久久丫线这里只精品| 99国产精品成人免费视频| 琪琪伦伦影院理论片| 国产AV电影区二区三区曰曰骚网| 天津相声广播在线收听| 韩国精品无码少妇在线观看网站| 依人在线观看| 女教师の诱惑| 国产精品久久久久久久久免费下载| 亚洲日韩欧美国产专区| 久久这里只精品国产99re66| 99久久久精品| 婷婷开心激情综合五月天| 国产在线观看黄| 最新国产在线视频| 日日啪在线影院百度| 花蝴蝶在线观看免费8 |