快速排序算法

int quicksort(int p[],int n); extern int insertsort(int p[], int n); static int partition(int p[],int n,int *m); int quickSort(int p[],int n); static int quick_sort(int p[],int n); /* * 快速排序算法在 1962 年由 C. Hoare 发明。 * 不稳定，需要与 lg(n) 成比例的辅助空间。 */ static struct stackframe { /* 栈帧 */    int * list;    int length; }; static struct stackframe sp[64]; /* 栈指针 */ static unsigned int    randx; /* 伪随机数 */ #define M 16 int quicksort(int p[],int n) {    int op=0;    int i,k;    int *h,l;    int m; /* 基准值的位置 */    struct stackframe *fp; /* 帧指针*/    struct stackframe *stp; /* 栈顶指针 */    if (n<=16)        return insertsort(p,n);    randx=p[0]%7875;    for (i=0,k=n; k>0; k>>=1,i++); /* i=[lg(n)] */    stp=sp+i;    fp=sp;    fp->list=p;    fp->length=n;    while (fp>=sp) {        h=fp->list;        l=fp->length;        /* 采用 D. Musser 的限定划分深度的建议 */        while (l>M && fp<=stp) {            op+=partition(h,l,&m);            fp->list=h+m+1;            fp->length=l-m-1;            fp++;            l=m;        }        fp–;    }    op+=insertsort(p,n);    return op; } /* * 基准值选择采用 C. Hoare 建议的随机选择策略。 */ static int partition(int p[],int n,               int *m )    /* 返回的基准值的位置 */ {    int i=0; /* 头指针 */    int j=n-1; /* 尾指针 */    int pivot; /* 基准值 */    int k;    if (n<=1)        return 0;    randx=(randx*421+1663)%7875; /* 线性同余伪随机数 */    k=randx%n;    /* 随机选择某个位置的元素作为基准值并保存它，     * 接着把头指针指向的元素复制到这个位置上 */    pivot=p[k];    p[k]=p;    /* p 已被交换到 p[k]，可以覆盖 */    while (i<j) { /* 头指针先于尾指针 */        while (i<j && p[j]>=pivot) /* 尾指针指向的元素大于基准值 */            j–;    /* 前移尾指针 */        if (i<j)            p[i++]=p[j]; /* 替换当前p内容为p[j]的内容, 后移头指针 */            /* p[j] 已被交换可以覆盖 */        while (i<j && p<=pivot) /* 头指针指向的元素小于基准值 */            i++; /* 后移头指针 */        if (i<j)            p[j--]=p; /* 替换当前p[j]内容为p的内容, 前移尾指针 */            /* p 已被交换可以覆盖 */    }    /* 如果最后一次交换的是 p[j]，则 i 指针会移动成 i=j */    p=pivot; /* 把保存的基准值保存到当前位置上 */    *m=i; /* 返回基准值当前的位置 */    return n; } /**************************************/ /*   下面是递归原型实现，留做参考   */ /**************************************/ int quickSort(int p[],int n) {    if (n<=16)        return insertsort(p,n);    randx=p[0]%7875;    return quick_sort(p,n); } static int quick_sort(int p[],int n) {    int op=0;    int m;      if (n>1) {        op+=partition(p,n,&m);        op+=quick_sort(p,m);        op+=quick_sort(p+m+1,n-m-1);    }    return op; }