如何在C語言中實(shí)現(xiàn)快速排序？相信很多沒有經(jīng)驗(yàn)的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。
創(chuàng)新互聯(lián)主營朝陽網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,成都App定制開發(fā),朝陽h5微信小程序搭建,朝陽網(wǎng)站營銷推廣歡迎朝陽等地區(qū)企業(yè)咨詢
快速排序的遞歸算法
#include#include #include #include #include #include using namespace std; #define OK 1 #define ERROR -1 #define TRUE 1 #define FALSE 0 typedef int Status; //輸出函數(shù) void Print(int a[], int l, int r) { int i; for(i = l; i <= r; i++) { printf("%d ", a[i]); } printf("\n"); } //劃分函數(shù) int partion(int a[], int left, int right) { //取最右邊的元素作劃分元素 int temp = a[right]; //記錄 i = left, j = right int i = left, j = right-1; //循環(huán)直到左右指針相遇 while(true) { //從左邊開始掃描,當(dāng)出現(xiàn)比劃分元素大的元素,掃描停止 while(temp > a[i]) { i++; } //從右邊進(jìn)行掃描,當(dāng)出現(xiàn)比劃分元素小的元素,掃描停止 while(temp < a[j] && j >= left) { j--; } //如果 i >= j, 循環(huán)截止,下面的交換不執(zhí)行 if(i >= j) break; //交換停止時(shí)的元素 swap(a[i], a[j]); } //交換該元素與劃分元素 swap(a[i], a[right]); Print(a, 0, 6); //printf("i = %d", i); //劃分過程結(jié)束 return i; } //快速排序 void qsort(int a[], int left, int right) { //排序完成,循環(huán)截止 if(right <= left) return; //做劃分 int i = partion(a, left, right); //對左部分排序 if(left < (i-1)) printf("對%d~%d排序\n", left, i-1), qsort(a, left, i-1); //對右部分排序 if(right > (i+1)) printf("對%d~%d排序\n", i+1, right), qsort(a, i+1, right); } int main() { int a[7] = {2, 5, 3, 7, 6, 1, 4}; //快速排序 printf("對0~6排序\n"); qsort(a, 0, 6); Print(a, 0, 6); return 0; }
非遞歸快速排序
快速排序的非遞歸實(shí)現(xiàn)使用了一個顯式的下推棧,使用向棧中壓入?yún)?shù)和過程調(diào)用/退出不斷地從棧中彈出參數(shù)來替代遞歸調(diào)用,這個過程繼續(xù)直到棧為空.我們把兩個子數(shù)組中的較大者壓入棧中來確保最大棧的深度為lgN,如果對N個元素進(jìn)行排序.
重慶分公司
重慶分公司
void qsort(int a[], int left, int right)
{
int i;
//定義棧s
stack s;
//先判斷棧是否為空
while(!s.empty())
{
//若棧不為空,將棧中元素移出
s.pop();
}
//將right入棧
s.push(right);
//將left入棧
s.push(left);
//while循環(huán),當(dāng)棧為空時(shí),循環(huán)結(jié)束
while(!s.empty())
{
//元素left出棧
left = s.top(), s.pop();
//元素right出棧
right = s.top(), s.pop();
//判斷l(xiāng)eft與right的關(guān)系,如果left>=right,continue
if(left >= right)
{
continue;
}
//作劃分
i = partion(a, left, right);
//比較兩個子數(shù)組的大小
//將子數(shù)組中的較大者壓入棧
if((i-1-left) > (right-i-1))
{
s.push(i-1);
s.push(left);
s.push(i+1);
s.push(right);
}
else
{
s.push(i+1);
s.push(right);
s.push(i-1);
s.push(left);
}
}
} 看完上述內(nèi)容，你們掌握如何在C語言中實(shí)現(xiàn)快速排序的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！
