C++ 中快排的遞歸和非遞歸實現(xiàn)
更新時間：2017年06月15日 08:42:48 投稿：lqh
這篇文章主要介紹了C++ 中快排的遞歸和非遞歸實現(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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
這篇文章主要介紹了C語言實現(xiàn)基于最大堆和最小堆的堆排序算法示例,分別是基于最大堆的升序排序和基于最小堆的降序排序?qū)嵗?需要的朋友可以參考下2016-06-06
這篇文章主要為大家詳細介紹了C語言實現(xiàn)折半查找法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
本文主要為大家詳細介紹了在QT中實現(xiàn)貪吃蛇游戲的詳細教程，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
windows自帶的游戲《掃雷》是陪伴了無數(shù)人的經(jīng)典游戲，本文將利用C語言實現(xiàn)這一經(jīng)典的游戲，文中的示例代碼講解詳細，感興趣的可以學習一下2022-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)計算器的兩種方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
編譯錯誤error: stray ‘\343’in program的解決方法
以下是對編譯錯誤error: stray ‘\343’in program的解決方法進行了詳細的分析介紹，如遇此問題的朋友們可以過來參考下2013-07-07
黃金礦工作為經(jīng)典的單機小游戲，一直深受大家的喜愛。本文將用Matlab制作這一款經(jīng)典的游戲，文中的實現(xiàn)步驟講解詳細，感興趣的可以了解一下2022-03-03
這篇文章主要為大家分享了C語言學生管理系統(tǒng)的源碼，幫助大家學習結(jié)構(gòu)體，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-03-03
linux安裝mysql和使用c語言操作數(shù)據(jù)庫的方法 c語言連接mysql
Linux下使用C語言操作數(shù)據(jù)庫的方法，我將從MySQL環(huán)境的搭建，MySQL命令的使用到使用C接口來操作MySQL等過程詳細的介紹在Linux下管理MySQL數(shù)據(jù)庫的方法2014-01-01
下面小編就為大家?guī)硪黄獪\談C++中派生類對象的內(nèi)存布局。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12