C++ 中快排的遞歸和非遞歸實(shí)現(xiàn)
更新時(shí)間：2017年06月15日 08:42:48 投稿：lqh
這篇文章主要介紹了C++ 中快排的遞歸和非遞歸實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下
快排的遞歸
void quickSort1(int* root,int low,int high)
{
int pat=root[low];
if(low<high)
{
int i=low,j=high;
while(i<j)
{
while(i<j&&root[j]>pat)
j--;
root[i]=root[j];
while(i<j&&root[i]<pat)
i++;
root[j]=root[i];
}
root[i]=pat;
quickSort1(root,low,i-1);
quickSort1(root,i+1,high);
}
}
快排的非遞歸
int partion(int* root,int low,int high)
{
int part=root[low];
while(low<high)
{
while(low<high&&root[high]>part) high--;
root[low]=root[high];
while(low<high&&root[low]<part) low++;
root[high]=root[low];
}
root[low]=part;
return low;
}
void quickSort2(int* root,int low,int high)
{
stack<int> st;
int k;
if(low<high)
{
st.push(low);
st.push(high);
while(!st.empty())
{
int j=st.top();st.pop();
int i=st.top();st.pop();
k=partion(root,i,j);
if(i<k-1)
{
st.push(i);
st.push(k-1);
}
if(k+1<j)
{
st.push(k+1);
st.push(j);
}
}
}
}
int main()
{
int a[8]={4,2,6,7,9,5,1,3};
quickSort1(a,0,7);
//quickSort2(a,0,7);
int i;
for(i=0;i<8;i++)
cout<<a[i]<<" ";
cout<<endl;
getchar();
return 0;
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
C++模擬實(shí)現(xiàn)stack和Queue的操作示例
這篇文章主要介紹了C++模擬實(shí)現(xiàn)stack和Queue的操作示例,文中通過(guò)代碼示例給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-06-06
C++實(shí)現(xiàn)銀行排隊(duì)系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)銀行排隊(duì)系統(tǒng)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-07-07
單值二叉樹(shù)你可能之前沒(méi)見(jiàn)過(guò)，如果二叉樹(shù)每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹(shù)就是單值二叉樹(shù)，讓我們通過(guò)一個(gè)真題來(lái)深刻了解它吧2022-04-04
C++/GoLang如何實(shí)現(xiàn)自底向上的歸并排序
這篇文章主要給大家介紹了關(guān)于C++/GoLang如何實(shí)現(xiàn)自底向上的歸并排序的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
從下面表中的數(shù)據(jù)來(lái)看寫(xiě)入用時(shí)vector和deque很快，因?yàn)樗麄儍?nèi)存分配次數(shù)少，關(guān)聯(lián)容器和list都是一個(gè)一個(gè)分配的，一個(gè)一個(gè)分配也會(huì)造成內(nèi)存碎片，內(nèi)存利用率低2013-09-09
這篇文章主要介紹了希爾排序算法的C語(yǔ)言實(shí)現(xiàn)示例,希爾排序可以看作為一種高級(jí)的插入排序,需要的朋友可以參考下2016-04-04
這篇文章主要為大家詳細(xì)介紹了如何通過(guò)C++實(shí)現(xiàn)H264文件以及一段H264碼流解析,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-10-10
使用VS Code進(jìn)行Qt開(kāi)發(fā)的實(shí)現(xiàn)
這篇文章主要介紹了使用VS Code進(jìn)行Qt開(kāi)發(fā)的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
C++?OpenCV實(shí)現(xiàn)之實(shí)現(xiàn)紅綠燈識(shí)別
本文以實(shí)現(xiàn)行車過(guò)程當(dāng)中的紅綠燈識(shí)別為目標(biāo)，核心的內(nèi)容包括：OpenCV輪廓識(shí)別原理以及OpenCV紅綠燈識(shí)別的實(shí)現(xiàn)具體步驟，感興趣的可以了解一下2022-08-08
C++標(biāo)準(zhǔn)庫(kù)沒(méi)有提供所謂的日期類型,C++繼承了C語(yǔ)言用于日期和時(shí)間操作的結(jié)構(gòu)和函數(shù),這篇文章主要給大家介紹了關(guān)于C++日期類實(shí)現(xiàn)的完整操作,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-06-06