常用的快排都是用递归写的,因为比较简单,但是可以用栈来实现非递归的快排。


第一种是递归的快排

#include<stdio.h>#include<stdlib.h>#include<time.h>intquick(inta[],inti,intj){inttmp=0,key,b=0;intim,jm;im=i;jm=j;key=a[i];if(i>j)return;while(i<j){while(a[j]>key&&i<j)j--;a[i]=a[j];while(a[i]<=key&&i<j)i++;a[j]=a[i];}//这块和非递归是不同的,这里用的是覆盖。a[i]=key;quick(a,im,i-1);quick(a,i+1,jm);return0;}int*rand_list(int*nums,intlen,intrange)//产生随机数{srand(time(NULL));inti=0;for(i=0;i<len;i++)nums[i]=rand()%range;returnnums;}intmain(){inta[100];rand_list(a,100,100);inti=0;quick(a,0,99);for(i=0;i<100;i++)printf("%d",a[i]);printf("\n");}


第二种是非递归

#include<stdio.h>#definemax20intsl[max];intsr[max];inttop=0;voidpush(inta,intb){sl[top]=a;sr[top]=b;top++;}voidpop(int*p1,int*p2){top--;*p1=sl[top];*p2=sr[top];}voidquick(int*a,intl,intr){intal,ar,point,tmp;push(l,r);while(top){pop(&l,&r);al=l;ar=r;point=a[(al+ar)/2];while(al<ar){while(a[al]<point&&al<ar)al++;while(a[ar]>point&&al<ar)ar--;if(al<=ar){tmp=a[al];a[al]=a[ar];a[ar]=tmp;al++;ar--;}}if(l<ar)//这块和递归是不同的,要注意,这里用的是相互交换push(l,ar);if(al<r)push(al,r);}}intmain(){inta[10]={2,4,1,8,3,5,9,7,6,0};quick(a,0,9);inti;for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");return0;}