快速排序的非递归实现.docVIP

快速排序的非递归实现 #includestdio.h#define Maxsize 100void quicksort(int a[],int n){ int i,j,low,high,temp,top=-1; struct node { int low,high; }st[Maxsize]; top++; st[top].low=0;st[top].high=n-1; while(top-1) { low=st[top].low;high=st[top].high; top--; i=low;j=high; if(lowhigh) { temp=a[low]; while(i!=j) { while(ija[j]temp)j--; if(ij){a[i]=a[j];i++;} while(ija[i]temp)i++; if(ij){a[j]=a[i];j--;} } a[i]=temp; top++;st[top].low=low;st[top].high=i-1; top++;st[top].low=i+1;st[top].high=high; } }}int main(){ int a[10]={189,987,654,321,548,254,658,845,125,489}; int i,n=10; quicksort(a,n); for(i=0;i10;i++)printf(%d ,a[i]);printf(\n);} 快速排序非递归算法　　快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。　　在下用C++实现了快速排序的递归算法和非递归算法，下面挂出了程序^_^(多多指教)：　　＃i nclude stdafx.h　　＃i nclude math.h　　＃i nclude 　　using namespace std;　　/*产生中枢的位置*/　　int partition(int q[],int low,int high)　　{int i=low;　　int j=high+1;　　 int p=i;　　 while(1){　　 while(q[++i]　　 while(q[--j]q[p]);　　 if(i=j) break; 　　 swap(q[i],q[j]);}　　 swap(q[j],q[p]);　　 return j;　　 } 　　　　/*递归算法*/　　void quicksort(int q[],int low,int high)　　{ if(low　　{int p=partition2(q,low,high);　　 quicksort(q,low,p-1);　　 quicksort(q,p+1,high);}　　}　　　　/*非递归算法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