❶ 求快速排序的非遞歸實現代碼。
bool exchange(int array[], int begin, int end, int &pos)
{
int pos_end = end;
int pos_begin = begin;
pos = begin;
if (begin >= end)
return false;
while(pos_begin < pos_end);
{
while (array[pos_end] < array[pos]) pos_end--;
if (pos_end > pos)
{
array[pos_end] = array[pos] + array[pos_end];
array[pos] = array[pos_end] - array[pos];
array[pos_end] = array[pos_end] - array[pos];
pos = pos_end;
}
while (array[pos_begin] > array[pos]) pos_begin++;
if (pos_begin < pos)
{
array[pos_begin] = array[pos] + array[pos_begin];
array[pos] = array[pos_begin] - array[pos];
array[pos_begin] = array[pos_begin] - array[pos];
pos = pos_begin;
}
}
return true;
}
struct Queue {
int begin;
int end;
struct Queue *next;
};
void QSort(int array[], int length)
{
struct Queue *head = (struct Queue *)malloc(sizeof(struct Queue));
struct Queue *tail = head;
int begin;
int end;
int pos;
head->begin = begin;
head->end = length - 1;
while (head != NULL)
{
struct Queue *tmp = head;
begin = head->begin;
end = head->end;
head->next = NULL;
if (exchange(array[], begin, end, pos))
{
tmp = (struct Queue *)malloc(sizeof(struct Queue));
tmp->begin = begin;
tmp->end = pos - 1;
tmp->next = NULL;
tail->next = tmp;
tail = tail->next;
tmp = (struct Queue *)malloc(sizeof(struct Queue));
tmp->begin = pos + 1;
tmp->end = end;
tmp->next = NULL;
tail->next = tmp;
tail = tail->next;
tmp = head;
head = tmp->next;
free(tmp);
}
}
}
❷ 快速排序的非遞歸實現 #include"stdio.h" #define Maxsize 100
是的，程序用人工棧實現了快排，是非遞歸的。
只是程序當中多了一行「1/13」
❸ 編寫 快速排序的非遞歸演算法
終於編寫出來了，我寫了兩種，你看看：下面是代碼：
/*非遞歸演算法1
遞歸演算法的開銷很大，所以在下編了一個非遞歸的，演算法描述如下：
A non-recursive version of quick sort using stack:
There are 2 stacks, namely one which stores the start of
a subarray and the other which stores the end of the
subarray.
STEP 1: while the subarray contains more than one element
,i.e. from Do {
SUBSTEP 1. pivot=Partion(subarray);
SUBSTEP 2. keep track of the right half of the current
subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo
SUBSTEP 3. go on to deal with the left half of
the current subarray i.e. to=pivot-1
}
STEP 2: if(neither of the stacks is empty)
Get a new subarray to deal with from the stacks.
i.e. start=pop(stackFrom); to=pop(stackTo);
STEP 3: both stacks are empty, and array has
been sorted. The program ends.
*/*/
void UnrecQuicksort(int q[],int low,int high)
{stack s1;<br/>stacks2;<br/> s1.push(low);<br/> s2.push(high);<br/> int tl,th,p;<br/> while(!s1.empty() && !s2.empty())<br/> {tl=s1.top();th=s2.top();<br/> s1.pop();s2.pop();<br/> if(tl>=th) continue;<br/> p=partition(q,tl,th);<br/> s1.push(tl);s1.push(p+1);<br/> s2.push(p-1);s2.push(th);<br/> }
}
/*非遞歸演算法2
要把遞歸演算法改寫成非遞歸演算法，可引進一個棧，這個棧的大小取決於遞歸調用的深度，最
多不會超過n，如果每次都選較大的部分進棧，處理較短的部分，遞歸深度最多不超過log2n
，也就是說快速排序需要的附加存儲開銷為O（log2n）。
*/
void UnrecQuicksort2(int q[],int low,int high)
{int *a;<br/> int top=0,i,j,p;<br/> a=new int[high-low+1];<br/> if(a==NULL) return;<br/> a[top++]=low;<br/> a[top++]=high;<br/> while(top>0)<br/> {i=a[--top];<br/> j=a[--top];<br/> while(j {p=partition(q,j,i);<br/> if(p-j {//先分割前部,後部進棧<br/>a[top++]=p+1;<br/> a[top++]=i;<br/> i=p-1;<br/> }
else
{//先分割後部,前部進棧
a[top++]=j;
a[top++]=p-1;
j=p+1;
}
}
}
}
/*列印輸出*/
void display(int p[],int len)
{for(int i=0;i cout<}
/*測試*/
int _tmain(int argc, _TCHAR* argv[])
{int a[]={49,65,97,12,23,41,56,14};
quicksort(a,0,7);
//UnrecQuicksort(a,0,7);
//UnrecQuicksort2(a,0,7);
display(a,8);
return 0;
}
❹ 快速排序的非遞歸實現
快速排序簡單的說就是選擇一個基準，將比起大的數放在一邊，小的數放到另一邊。對這個數的兩邊再遞歸上述方法。
如本題
66 13 51 76 81 26 57 69 23，以66為基準，升序排序的話，比66小的放左邊，比66大的放右邊， 類似這種情況 13 。。。 66。。。69
具體快速排序的規則一般如下：
從右邊開始查找比66小的數，找到的時候先等一下，再從左邊開始找比66大的數，將這兩個數藉助66互換一下位置，繼續這個過程直到兩次查找過程碰頭。
例子中：
66 13 51 76 81 26 57 69 23
從右邊找到23比66小，互換
23 13 51 76 81 26 57 69 66
從左邊找到76比66大，互換
23 13 51 66 81 26 57 69 76
繼續從右邊找到57比66小，互換
23 13 51 57 81 26 66 69 76
從左邊查找，81比66大，互換
23 13 51 57 66 26 81 69 76
從右邊開始查找26比66小，互換
23 13 51 57 26 66 81 69 76
從左邊開始查找，發現已經跟右邊查找碰頭了，結束，第一堂排序結束
下面排序C語言的排序快速代碼，參考一下
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左邊索引大於或者等於右邊的索引就代表已經整理完成一個組了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在當組內尋找一遍*/
{
while(i < j && key <= a[j])
/*而尋找結束的條件就是，1，找到一個小於或者大於key的數（大於或小於取決於你想升
序還是降序）2，沒有符合條件1的，並且i與j的大小沒有反轉*/
{
j--;/*向前尋找*/
}
a[i] = a[j];
/*找到一個這樣的數後就把它賦給前面的被拿走的i的值（如果第一次循環且key是
a[left]，那麼就是給key）*/
while(i < j && key >= a[i])
/*這是i在當組內向前尋找，同上，不過注意與key的大小關系停止循環和上面相反，
因為排序思想是把數往兩邊扔，所以左右兩邊的數大小與key的關系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*當在當組內找完一遍以後就把中間數key回歸*/
sort(a, left, i - 1);/*最後用同樣的方式對分出來的左邊的小組進行同上的做法*/
sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/
/*當然最後可能會出現很多分左右，直到每一組的i = j 為止*/
}
❺ 用一個棧可將遞歸式的「快速排序演算法」轉變成非遞歸的迭代形式。轉變的策略是
S:(6,10),(2,4),出棧,(3,4),出棧,(18,18)不進,，(6,10)出棧,(8,10),出棧,完成
❻ 把快速排序遞歸演算法改成非遞歸
可以用棧把那些要排的東西記下來如，起始位置，結束位置，基準位置，再一個一個的排，直到棧為空
／／還有很多沒有寫你自己去填上
struct qq{
int frist;
int last;
}QQ[MAXSIZE];
int a[max];
struct qq dd,ff;
while(!empty(QQ)){
dd=pop(QQ);//不為空就出棧
qkOne(a[],dd->frist,dd->last);//把這一部分排好；
if(dd->frist<i){ ff->frist=dd-frist;ff->last=i-1;push(ff,QQ);}//這里改為入棧就可以了，下同
if(i<dd->last){ff->frist=i+1;ff->last=dd->last;push(ff,QQ);}
｝
}
void qkOne(int a[],int frist,int last)；//frist為起始位置，last為終止位置
{ int x,i,j;
i=frist;
j=last;
x=a[i];//將第一個值保存在x中,做基準值。
while(i!=j)
{
while(i<j && a[j]>=x)
; /*自右向左掃描*/
if(i<j)
{
;
i++;
}
while(i<j&&a[i]<=x)
i++; /*自左向右掃描*/
if(i<j)
{ a[j]=a[i];
;
}
}
;