首页 > C/C++语言 > C/C++数据结构 > 快速排序算法
2006
05-28

快速排序算法

👤 📁 C/C++数据结构 💬 发表评论






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;
}

固定链接: https://www.vcgood.com/archives/731

声明: 2006年05月28日 发表于 C语言帝国

标签:

相关文章推荐

留下一个回复