導航:首頁 > 編程語言 > java非遞歸快速排序

java非遞歸快速排序

發布時間:2022-07-01 09:53:28

㈠ l遞歸快排非遞歸快排區別

兩者的功能沒有什麼區別,差別只是在於實現機制:
遞歸演算法是通過遞歸來利用系統棧保存每次分割後左右序列的起始和終止位置
非遞歸演算法則是用戶自行編程用棧或者隊列來保存每次分割後左右序列的起始和終止位置
如果是用棧,則非遞歸演算法的嚴格執行過程也基本與遞歸演算法一致

㈡ 快速排序的非遞歸實現 #include"stdio.h" #define Maxsize 100

是的,程序用人工棧實現了快排,是非遞歸的。
只是程序當中多了一行「1/13」

㈢ 快速排序的非遞歸實現

快速排序簡單的說就是選擇一個基準,將比起大的數放在一邊,小的數放到另一邊。對這個數的兩邊再遞歸上述方法。

如本題

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 為止*/
}

㈣ 用java語言把abcd的全排列演算法(遞歸),改成非遞歸求全排列,遞歸演算法如下: public

最快能想到的就是用四重循環實現。

㈤ 請大神幫我看一下 這個非遞歸快速排序 為什麼在排待排數組含相同元素的時候會出錯

左右比較的時候都沒有把相當的情況考慮進去,當出現相等的時候,你的代碼就會陷入死循環

㈥ 我的字典序全排列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的話是得不到正確的結果的,不過我改寫的竟然可以得到正確的結果,真是奇怪

㈦ java排序演算法中,快速排序慢好多,還容易爆棧,求指教

㈧ 求快速排序的非遞歸實現代碼。

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);

}

}

}

㈨ 編寫 快速排序的非遞歸演算法

終於編寫出來了,我寫了兩種,你看看:下面是代碼:

/*非遞歸演算法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;
}

㈩ 誰能在10分鍾之內在自己的筆記本中用java或c++非遞歸實現的快速排序

快速排序本來就不是用遞歸實現的

閱讀全文

與java非遞歸快速排序相關的資料

熱點內容
加密貨幣市場活躍 瀏覽:334
最便宜的雲盤伺服器架設傳奇 瀏覽:790
java反向工程 瀏覽:110
pdf文檔轉換excel 瀏覽:8
主角叫楚天的都市小說 瀏覽:754
程序員三重境界 瀏覽:871
菜雞方舟上怎麼開伺服器 瀏覽:727
馬林固件編譯錯誤 瀏覽:910
市場營銷案例pdf 瀏覽:770
魔爪閱讀網 瀏覽:19
app地推業績統計在哪裡 瀏覽:993
維語電影網站大全 瀏覽:958
程序員骨腫瘤上熱搜 瀏覽:847
聚優電影 瀏覽:45
國企保底工資演算法 瀏覽:730
視聽說伺服器地址是什麼意思 瀏覽:657
一部男主叫大志的電影叫 瀏覽:650
安卓反編譯後編譯不回來 瀏覽:195
快穿肉文推薦 瀏覽:263
lol新手推薦什麼伺服器 瀏覽:283