快速排序qsort

来自计算机程序设计常见问题集
跳转至: 导航搜索

在头文件<stdlib.h>中,提供了一个快速排序函数qsort。在使用中,他的代码量并没有下降,但是排序速度却得到了极大提高。

它的函数原型如下:、

void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));

四个参数分别是:

1 待排序数组首地址
2 数组中待排序元素数量
3 各元素的占用空间大小
4 指向函数的指针,用于确定排序的顺序

这个解释比较抽象,我们先看一个具体的例子

#include<stdio.h>
#include<stdlib.h>
int comp(const void*a,const void*b)
{ 
   return *(int*)a-*(int*)b;
}
int main()
{
  int *array;
  int n;
  scanf("%d",&n);
  array=(int*)malloc(n*sizeof(int));
  int i=0; for(;i<n;i++)
  { 
   scanf("%d",(array+i));
  }
  qsort(array,n,sizeof(int),comp);
  for(i=0;i<n;i++)
  {
    printf("%d\t",array[i]);
  }
  return0;
}

通过这个例子,我们能很快理解前三个参数的用途。第四个参数是一个函数指针,理解起来比较困难。我们只需要记住他的写法就好。

int compare( void * elem1, void * elem2 );

Compare函数的返回值     描述 
<0                    elem1将被排在elem2前面 
0                     elem1 等于 elem2 
>0                    elem1 将被排在elem2后面 

这个函数的两个参数都是void*类型,在具体使用中,要转换成具体的类型,例如在上面的例子中,就转换为了int*。