❶ 求快速排序的非递归实现代码。
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];
;
}
}
;