前些天学习了程序栈空间的大小是会有上限的。看来递归的算法永远无法应用到大规模的数据上，毕竟栈空间有限。这几天写了点算法题目，刚好涉及到如何广度优先搜索。想起自己学数据结构的时候就想快排能否以非递归式方式实现。于是自己就写了个非递归的快排算法，以供学习。

　　我搜了一下网上的快排非递归算法，几乎都是使用栈来模拟的。但其实完全不必使用栈，队列一样可以。一开始觉得栈可能消耗最大空间比队列少一点，但其实如果队列条件设置好了也可以减少到差不多的大小。所以就自己写了一个，总体思路就是将需要排序的开始和结束位置放入队列的每个节点中，然后不断的，取出和放入。

这个算法写了我半天。。。原来准备弄个大数据测试效率，结果发现自己写的算法原来存在缺陷。。

我的算法思路是把中间值当key值。从左边开始找比key大的值，然后从右边开始找比key小的值，然后交换两个值，直到两个指针相等。

但是当我开始用大数据测试的时候就发现会陷入到死循环中。a[left]==key&&key==a[right]的话就无法更新指针了，一直死循环了。。

主体如下：

       while(first<end)//快排主体 
       {
           while(first<end && needsort[first]<key)
                           first++;
           while(first<end && needsort[end]>key)
                           end--;
           if(first<end)
           {     int t=needsort[first];
                 needsort[first]=needsort[end];
                 needsort[end]=t;
           } 
       }

为图简单一直这么写。。没想到有错误。。。。还交给老师当上机作业了。。看来老师不够负责啊！！

至于为什么，我想是这样的：

如果在first那里加上=号，那么当key刚好是最大值的时候什么排序都没有了。first一直加到end处。

如果在end那里加上=号，那么当key刚好是最小值的时候同上，end一直减到first处。排序什么的就没有了。。

都加等号的情况等于第一种。

还好今天自己又写了一遍。。以后记住就行了。

下面是成功了的代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<ctime>

using namespace std;

typedef struct nn//队列中的结点 
{
        int a;
        int b;
        struct nn* next;
}qnode;

typedef struct h//队列的控制结构 
{
      qnode *head;
      qnode *tail;  
      int cnt;
}qctrl;

qctrl* qinit(int ,int);
void qinsert(qctrl**,int ,int );
qnode* qget(qctrl **);

#define MAX 30000

int needsort[MAX];
int main()
{
    srand(time(NULL));
    for(int i=0;i<MAX;i++)
        needsort[i]=rand();
        
    qctrl *ctrl=qinit(0,MAX-1);
    int cnt=0;
    while(ctrl->cnt)
    {
       qnode *temp=qget(&ctrl);//得到排序范围 
       if(temp->a>=temp->b)
       { 
           free(temp);
           continue;
       }
       int first,middle,end;
       first=temp->a;
       end=temp->b;
       while(first<end)//快排主体 
       {
           while(first<end && needsort[first]<=needsort[end])//这里是为了让，所有相等的全部包含在右边 
                           end--;         
           if(first<end)
           {     int t=needsort[first];
                 needsort[first]=needsort[end];
                 needsort[end]=t;
           }                                             
           while(first<end && needsort[first]<needsort[end])
                           first++;

           if(first<end)
           {     int t=needsort[first];
                 needsort[first]=needsort[end];
                 needsort[end]=t;
           } 
       }
       qinsert(&ctrl,temp->a,first);//插入两边下次需要排序的范围 
       qinsert(&ctrl,first+1,temp->b);
       free(temp);	  
    }
    for(int i=1;i<MAX;i++)//显示排序结果
    {      
		if(needsort[i-1]>needsort[i])
		{	cout<<endl<<needsort[i]<<"error"<<endl;
		  break;
        }
        else
		{	
			if(i%10==0)
				cout<<endl;
			else
				cout<<needsort[i-1]<<" ";
		}
     }
    	free(ctrl);
  	fflush(stdin);
   	getchar();
	return 0;
}


qctrl *qinit(int a,int b)
{
      qnode * temp;
      qctrl * cc=(qctrl *)malloc(sizeof(qctrl));
      temp=(qnode *)malloc(sizeof(qnode));
      temp->a=a;
      temp->b=b;
      temp->next=NULL;
      cc->head=temp;
      cc->tail=cc->head;
      cc->cnt=1;
      return cc;
}

void qinsert(qctrl **c,int a,int b)
{
	qctrl *cc=*c;
	if(cc->cnt==0)
	{
		cc->head=(qnode *)malloc(sizeof(qnode));
		cc->tail=cc->head;
	}
	else
	{
		cc->tail->next=(qnode *)malloc(sizeof(qnode));
		cc->tail=cc->tail->next;
	}  
	 cc->tail->a=a;
     cc->tail->b=b;
     cc->tail->next=NULL;
     cc->cnt++;
	
}

qnode *qget(qctrl **c)
{
	  qctrl *cc=*c;
      qnode* t=cc->head;
      cc->head=cc->head->next;
      cc->cnt--;
	  if(cc->cnt==0)
	  {
		  cc->head=NULL;
		  cc->tail=NULL;
	  }
      return t;
}

虽说用的cpp文件，但除了输出基本都是用的c语法。应该能让更多人能看懂吧。

快速排序的非递归算法（使用队列）