排序算法（2） 快速排序——快排原理以及快排函数qsort

#include <stdio.h> 
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用 
void quicksort(int left,int right) 
{ 
 int i,j,t,temp; 
 if(left>right) 
 return; 
 
 temp=a[left]; //temp中存的就是基准数 
 i=left; 
 j=right; 
 while(i!=j) 
 { 
 //顺序很重要，要先从右往左找 
 while(a[j]>=temp && i<j) 
 j--; 
 //再从左往右找 
 while(a[i]<=temp && i<j) 
 i++; 
 //交换两个数在数组中的位置 
 if(i<j)//当哨兵i和哨兵j没有相遇时
 { 
 t=a[i]; 
 a[i]=a[j]; 
 a[j]=t; 
 } 
 } 
 //最终将基准数归位
 a[left]=a[i]; 
 a[i]=temp; 
 
 quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程 
 quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程 
} 
int main() 
{ 
 int i,j,t; 
 //读入数据 
 scanf("%d",&n); 
 for(i=1;i<=n;i++) 
 scanf("%d",&a[i]); 
 quicksort(1,n); //快速排序调用 
 
 //输出排序后的结果 
 for(i=1;i<=n;i++) 
 printf("%d ",a[i]); 
 getchar();getchar(); 
 return 0; 
}

这个是我们自己写快排的代码，其实在C和C++的库函数里面，有一个自带的快排函数qsort

这个函数的头文件：

#include <stdlib.h>

这个函数的书写格式，函数声明是这样：

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

声明里面的参数的分别是：

base -- 指向要排序的数组的第一个元素的指针。

nitems -- 由 base 指向的数组中元素的个数。

size -- 数组中每个元素的大小，以字节为单位。

compar -- 用来比较两个元素的函数

这几个参数里面，唯独最后一个参数不好理解。最后一个参数，是要传给他一个比较函数，比较函数是什么？就是比较两个数大小的函数；从哪里找这个函数？自己写！！

是的，最后那个参数其实就是一个自己写的比较函数。

为了方便大家理解，我们举个例子来使用一下。

#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int values[] = { 40, 10, 100, 90, 20, 25 };// 自定义的一个序列

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}// 这个就是我们自己写的比较函数，用于比较a，b大小.如果a小于b，则返回值为负数（< 0），也即a会排在b的前面。同理，若a大于b，则a会排在b的后面。所以，这里的qsort()为从小到大即升序排序。如果需要从小到大，那么就返回b-a即可

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
//调用qsort函数 values 所需要排序的序列的首地址；6 代表序列有6个元素；sizeof（int）因为是个int数组，所以每个元素的大小是sizeof（int）；最后compare就是我们自己的比较函数
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

这个就是qsort函数的实例，不是很理解的可以评论区留言，然后自己多上手试试，这个函数还是比较好用的，这么使用不比我们自己写一个快速排序或者冒泡排序来的快？！

如果在这个基础上，运动动态分配是可以实现一个排序程序的（就是任一序列进行排序），大家也可以上手试一试，不是很难。

好滴，今天的分享到此结束，对了，大伙儿圣诞节快乐哦！！