㈠ 誰能在10分鍾之內在自己的筆記本中用java或c++非遞歸實現的快速排序
快速排序本來就不是用遞歸實現的
㈡ 快速排序的非遞歸實現
快速排序簡單的說就是選擇一個基準，將比起大的數放在一邊，小的數放到另一邊。對這個數的兩邊再遞歸上述方法。
如本題
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 為止*/
}
㈢ 快速排序的非遞歸實現 #include"stdio.h" #define Maxsize 100
是的，程序用人工棧實現了快排，是非遞歸的。
只是程序當中多了一行「1/13」
㈣ 求快速排序的非遞歸實現代碼。
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);
}
}
}
㈤ 我的字典序全排列java程序，怎麼改成非遞歸演算法
packageLianxi.yong2;
importjava.util.LinkedList;
importjava.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[]args){
Aa=newA();
}
}
classA{
Scannercin=newScanner(System.in);
intn;
chara[];
publicA(){
n=cin.nextInt();
a=newchar[n];
for(inti=0;i<n;i++){
a[i]=(char)(i+49);
}
next();
}
privatevoidnext(){
//TODOAuto-generatedmethodstub
for(chari:a){
System.out.print(i+"");
}
System.out.println();
LinkedList<Integer>is=newLinkedList<Integer>();
LinkedList<Integer>js=newLinkedList<Integer>();
is.add(n-1);
js.add(n-1);
//假設我們不模擬遞歸的情況，就模擬多重循環(這比較簡單，先做簡單的事情)
//但是事實就是其實只要模擬一個多重循環就可以把問題解決了
while(!is.isEmpty()&&is.getLast()>0){
while(!js.isEmpty()&&js.getLast()>=is.getLast()){
intj=js.getLast();
inti=is.getLast();
js.removeLast();
js.addLast(j-1);
if(a[j]>a[i-1]){
swap(j,i-1);
xu(i);
for(charc:a){
System.out.print(c+"");
}
System.out.println();
is.add(n-1);
js.add(n-1);
}
}
js.removeLast();
js.addLast(n-1);
is.addLast(is.removeLast()-1);
}
}
privatevoidxu(inti){
//TODOAuto-generatedmethodstub
intj=n-1;
for(inti2=0;i+i2<j-i2;i2++){
if(i+i2<j-i2)
swap(i+i2,j-i2);
}
}
privatevoidswap(inti,intj){
//TODOAuto-generatedmethodstub
chartemp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
我不知道你的演算法是否正確，但是如果8 9的話是得不到正確的結果的，不過我改寫的竟然可以得到正確的結果，真是奇怪
㈥ 編寫 快速排序的非遞歸演算法
終於編寫出來了，我寫了兩種，你看看：下面是代碼：
/*非遞歸演算法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;
??}
??
㈦ java排序演算法中，快速排序慢好多，還容易爆棧，求指教
代碼沒問題
我今天也遇到一樣的問題
猜測是因為快排遞歸創建了很多棧，當數據量過大時就棧溢出
我的解決方法是自己也寫了一個快速排序非遞歸的方法
但是實際耗費的時間仍然不如其他演算法
㈧ l遞歸快排非遞歸快排區別
兩者的功能沒有什麼區別，差別只是在於實現機制：
遞歸演算法是通過遞歸來利用系統棧保存每次分割後左右序列的起始和終止位置
非遞歸演算法則是用戶自行編程用棧或者隊列來保存每次分割後左右序列的起始和終止位置
如果是用棧，則非遞歸演算法的嚴格執行過程也基本與遞歸演算法一致
㈨ 把快速排序遞歸演算法改成非遞歸
可以用棧把那些要排的東西記下來如，起始位置，結束位置，基準位置，再一個一個的排，直到棧為空
／／還有很多沒有寫你自己去填上
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];
;
}
}
;
㈩ 用一個棧可將遞歸式的「快速排序演算法」轉變成非遞歸的迭代形式。轉變的策略是
S:(6,10),(2,4),出棧,(3,4),出棧,(18,18)不進,，(6,10)出棧,(8,10),出棧,完成