#include <iostream>
using namespace std;
#include <iostream>
using namespace std;
typedef int KeyType;
struct LElemType               
{
	KeyType key;
};
struct SElemType 
{          
	int a;
	int b;
};
struct SList
{
    LElemType *r;
	int length;
};

const int StackInitSize=10;
const int StackInc=15;

struct SStack
{
    SElemType *base,*top;
	int stacksize;
};

bool StackInit (SStack &S);//构造栈
bool Push(SStack &S,SElemType &e);//入栈
bool Pop(SStack &S,SElemType &e);//出栈
bool StackEmpty(SStack &S);//空栈
bool ListCreate(SList &L,int n,LElemType a[]);//创建顺序表
void Listshow(SList &L);//显示表
void quicksort(SList &L);//非递归的快速排序
void InsertSort(SList &L) ;
int Partition(SList &L, int a, int b);
int main()
{
	const int i=13;
	LElemType a[i]={3,7,1,5,9,6,4,10,15,12,14,19,16};
	SList L;
	ListCreate(L,i,a);
	cout<<"待排序的元素序列为"<<endl;
	Listshow(L);
	quicksort(L);
    cout<<endl<<"非递归的快速排序后元素序列为"<<endl;
	Listshow(L);
    cout<<endl;
	return 0;
}
bool ListCreate(SList &L,int n,LElemType a[])
{
	int i;
	L.r=new LElemType[n];
	if(!L.r)			return false;	
	L.length=n;
	for(i=0;i<n;i++)
	{
		L.r[i]=a[i];
	}
	return true;
}
void Listshow(SList &L)
{
	int i=L.length;
	for(int j=0;j<i;j++)
	{
		cout<<L.r[j].key<<"  ";
	}
}
bool StackInit (SStack &S)
{
	S.base=new SElemType[StackInitSize];
	if(!S.base) return false;
	S.top=S.base;
	S.stacksize=StackInc;
	return true;
}
bool StackEmpty(SStack &S)
{
	return S.top==S.base;
}
bool Push(SStack &S,SElemType &e)
{
	SElemType *base;
	if(S.top-S.base==S.stacksize)
	{
		base=(SElemType*)realloc(S.base,(S.stacksize+StackInc)*sizeof(SElemType));
		if(!base) return false;
		S.base=base;
		S.top=S.base+S.stacksize;
		S.stacksize+=StackInc;
	}
	*S.top=e;
	S.top++;
	return true;
}
bool Pop(SStack &S,SElemType &e)
{
	if(S.top==S.base) return false;
	S.top--;
	e=*S.top;
	return true;
}
int Partition(SList &L, int a, int b) 
{
	LElemType x = L.r[a];
	while (a < b) {
		while (a < b && L.r[b].key >= x.key) {
			b--;
		}
		L.r[a] = L.r[b];
		while (a < b && L.r[a].key <= x.key) {
			a++;
		}
		L.r[b] = L.r[a];
	}
	L.r[a] = x; return a;
}
void quicksort(SList &L)
{
		SStack S; StackInit(S);
	SElemType e, p; 
	e.a = 0; e.b = L.length-1;
	Push(S, e); int t;
	while (Pop(S, e)) {
		if (e.b-e.a<7) { 
			continue;
		}
		t = Partition(L, e.a, e.b);
		p.a = e.a; p.b = t - 1;
		Push(S, p);
		p.a = t + 1; p.b = e.b;
		Push(S, p);
	}
	InsertSort(L);

}
void InsertSort(SList &L) 
{            
	int i, j; LElemType x;
	for (i = 1; i < L.length; i++) {
		for (x = L.r[i], j = i - 1; j >= 0 && x.key < L.r[j].key; j--) {
			L.r[j + 1] = L.r[j];
		}
		L.r[j + 1] = x;
	}
}