㈠ 谁能在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),出栈,完成