?文章來源地址http://www.zghlxwxcb.cn/news/detail-415992.html
目錄
一.前言
二.非遞歸實(shí)現(xiàn)
一.前言
如果數(shù)據(jù)量過大的話，不斷遞歸就會(huì)出現(xiàn)棧溢出的現(xiàn)象，這個(gè)時(shí)候你的代碼是沒問題的，但就是跑不起來，這個(gè)時(shí)候就要把遞歸改成非遞歸。
一般有兩種改法：
1.直接改，利用循環(huán)等；
2.借助棧的輔助。
而快速排序的非遞歸實(shí)現(xiàn)方法就需要借助棧的輔助。
二.非遞歸實(shí)現(xiàn)
通過觀察我們發(fā)現(xiàn)，每次遞歸調(diào)用傳過去的是一個(gè)數(shù)組和一個(gè)區(qū)間，數(shù)組自不用說，這個(gè)區(qū)間就是我們的突破點(diǎn)；
也就是說我們只要想辦法在循環(huán)的時(shí)候拿到本次要排序的區(qū)間就行了，那要怎么做呢？
借助數(shù)據(jù)結(jié)構(gòu)：棧，棧具有后進(jìn)先出的特性，借助這個(gè)就能很好的解決問題。
1.首先要先把 left 和 right 入棧，這樣棧此時(shí)就不為空，然后開始循環(huán)。
2.取出棧頂?shù)膬蓚€(gè)數(shù)據(jù)，分別賦給 begin 和 end ，注意在這之后要pop掉取出的數(shù)據(jù)；
3.然后就是快排的邏輯，有三種方法，哪種都可以；
? ?如果不清楚這三種方法的話，請(qǐng)點(diǎn)擊：快速排序的三種實(shí)現(xiàn)方法
? ?走完一趟后就得到了 keyi；
4.然后數(shù)組就被 keyi 分成了兩個(gè)子區(qū)間，分別是：
? ? ?左區(qū)間：[begin，keyi-1]
? ? ?右區(qū)間：[keyi+1，end]
?分別將左區(qū)間和右區(qū)間入棧，注意這里要判斷：
? ? ? ?a.keyi+1<end
? ? ? ?b.keyi-1>begin
否則會(huì)出現(xiàn)數(shù)組訪問越界或是死循環(huán)的情況。
5.因?yàn)闂Ｊ呛筮M(jìn)先出，所以要是想先排左區(qū)間的話，就要先入右區(qū)間進(jìn)棧，反之；
6.循環(huán)結(jié)束后，銷毀棧。
void QuickSortNonR(Sdatatype* arr, int left, int right)
{
ST st;
Stackinit(&st);
Stackpush(&st, right);
Stackpush(&st, left);
while (!Stackempty(&st)) //棧為空時(shí)就結(jié)束循環(huán)
{
int begin = Stacktop(&st); //出一個(gè)就要pop掉一個(gè)數(shù)據(jù)
Stackpop(&st);
int end = Stacktop(&st);
Stackpop(&st);
int keyi = begin; //以下為快速排序的邏輯，這里用的是前后指針法實(shí)現(xiàn)
int mid = GetMid(arr, begin, end);
if (mid != keyi)
Swap(&arr[mid], &arr[keyi]);
int prev = begin, cur = begin + 1;
while (cur <= end)
{
if (arr[cur] < arr[keyi])
{
prev++;
Swap(&arr[cur], &arr[prev]);
cur++;
}
else
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
if (keyi + 1 < end) //不要忘記判斷
{
Stackpush(&st, end); //這里是先入的右區(qū)間，所以是先排序左區(qū)間
Stackpush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
Stackpush(&st, keyi - 1);
Stackpush(&st, begin);
}
}
Stackdestroy(&st); //銷毀棧
}
????本篇文章到此就結(jié)束了，若有錯(cuò)誤或是建議的話，歡迎小伙伴們指出；?????
????希望小伙伴們能支持支持博主啊，你們的支持對(duì)我很重要哦；????
????謝謝你的閱讀。????
文章來源：http://www.zghlxwxcb.cn/news/detail-415992.html
?
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】快速排序的非遞歸實(shí)現(xiàn)方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu) -- 手撕排序算法第六篇] 遞歸實(shí)現(xiàn)快速排序（集霍爾版本，挖坑法，前后指針法為一篇的實(shí)現(xiàn)方法，很能打）](https://imgs.yssmx.com/Uploads/2024/02/589845-1.png)
![[數(shù)據(jù)結(jié)構(gòu) -- 手撕排序算法第七篇] 遞歸實(shí)現(xiàn)歸并排序](https://imgs.yssmx.com/Uploads/2024/02/573259-1.png)
