C++ 中快排的遞歸和非遞歸實現(xiàn)
更新時間：2017年06月15日 08:42:48 投稿：lqh
這篇文章主要介紹了C++ 中快排的遞歸和非遞歸實現(xià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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關文章
這篇文章主要介紹了C++模擬實現(xiàn)stack和Queue的操作示例,文中通過代碼示例給大家介紹的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2024-06-06
這篇文章主要為大家詳細介紹了C++實現(xiàn)銀行排隊系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-07-07
單值二叉樹你可能之前沒見過，如果二叉樹每個節(jié)點都具有相同的值，那么該二叉樹就是單值二叉樹，讓我們通過一個真題來深刻了解它吧2022-04-04
這篇文章主要給大家介紹了關于C++/GoLang如何實現(xiàn)自底向上的歸并排序的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
從下面表中的數(shù)據(jù)來看寫入用時vector和deque很快，因為他們內存分配次數(shù)少，關聯(lián)容器和list都是一個一個分配的，一個一個分配也會造成內存碎片，內存利用率低2013-09-09
這篇文章主要介紹了希爾排序算法的C語言實現(xiàn)示例,希爾排序可以看作為一種高級的插入排序,需要的朋友可以參考下2016-04-04
這篇文章主要為大家詳細介紹了如何通過C++實現(xiàn)H264文件以及一段H264碼流解析,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-10-10
這篇文章主要介紹了使用VS Code進行Qt開發(fā)的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-10-10
C++?OpenCV實現(xiàn)之實現(xiàn)紅綠燈識別
本文以實現(xiàn)行車過程當中的紅綠燈識別為目標，核心的內容包括：OpenCV輪廓識別原理以及OpenCV紅綠燈識別的實現(xiàn)具體步驟，感興趣的可以了解一下2022-08-08
C++標準庫沒有提供所謂的日期類型,C++繼承了C語言用于日期和時間操作的結構和函數(shù),這篇文章主要給大家介紹了關于C++日期類實現(xiàn)的完整操作,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-06-06