关于几种类型的快排函数的说明

qsort的写法如下:

qsort(s,n,sizeof(s[0]),cmp);

其中第一个参数是的参与排序的数组名（或者可以理解成开始排序的地址）

这样的表达式，第二个参数是参与排序的元素个数；第三个是单个元素的大小，推荐使用sizeof(s[0])这样的表达式；

第四个参数是很多人觉得非常困惑的比较函数啦，关于这个函数，以下还要说：

cmp只是个函数名，可以随便起个名字；他是英语单词“比较”的前三个字母。

int cmp(const void *a,const void *b);

返回值必须是int，后面的两个参数的类型都必须是const void *;

假设是对int排序的话，若a>b返回一个正值，小则负值，相等为0；

另外如果对数组进行部分排序，比如对一个是s[n]的数组从s[i]开始的m个元素，只需要在第一个和第二个参数上进行一些修改：qsort(&s[i],m,sizeof(s[i]),cmp);

例子1：对int型的排序

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

int s[1000],n,i;

int cmp(const void *a,const void *b)

{

 return(*(int *)a-*(int *)b);

}

int main()

{

 cin>>n;

 for(i=0;i<n;i++)

  cin>>s[i];

 qsort(s,n,sizeof(s[0]),cmp);

 for(i=0;i<n;i++)

  cout<<s[i]<<" ";

 return 0;

}

例子2：对double型的排序

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

double s[1000];

int n,i;

int cmp(const void *a,const void *b)

{

 return((*(double *)a-*(double *)b>0)?1:-1);

}

int main()

{

 cin>>n;

 for(i=0;i<n;i++)

  cin>>s[i];

 qsort(s,n,sizeof(s[0]),cmp);

 for(i=0;i<n;i++)

  cout<<s[i]<<" ";

 return 0;

}

例子3:对一个字符数组排序：

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

char s[1000];

int n,i;

int cmp(const void *a,const void *b)

{

 return(*(char *)a-*(char *)b);

}

int main()

{

 cin>>n;

 for(i=0;i<n;i++)

  cin>>s[i];

 qsort(s,n,sizeof(s[0]),cmp);

 for(i=0;i<n;i++)

  cout<<s[i]<<" ";

 return 0;

}

例子4：对字符串数组排序（char *s[]型）：

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

char *s[1000];

int n,i;

int cmp(const void *a,const void *b)

{

 return(strcmp(*(char **)a,*(char **)b));

}

int main()

{

 cin>>n;

 for(i=0;i<n;i++)

 {

   s[i]=(char*)malloc(sizeof(char*));

   cin>>s[i];

 }

 qsort(s,n,sizeof(s[0]),cmp);

 for(i=0;i<n;i++)

  cout<<s[i]<<" ";

 return 0;

}

例子5：对结构体得排序

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

struct node

{

 double date1;

 int no;

}s[100];

int i,n;

int cmp(const void *a,const void *b)

{

 struct node *aa=(node *)a;

 struct node *bb=(node *)b;

 return(((aa->date1)>(bb->date1))?1:-1);

}

int main()

{

 cin>>n;

 for(i=0;i<n;i++)

 {

   //s[i]=(char*)malloc(sizeof(char*));

   s[i].no=i+1;

   cin>>s[i].date1;

 }

 qsort(s,n,sizeof(s[0]),cmp);

 for(i=0;i<n;i++)

  cout<<s[i].date1<<" ";

 return 0;

}

例子6：对结构体得排序2：

#include <iostream>

#include<stdlib.h>

#include<string>

using namespace std;

struct node

{

 double date1;

 int no;

}s[100];

int i,n;

int cmp(const void *a,const void *b)

{

 struct node *aa=(node *)a;

 struct node *bb=(node *)b;

    if(aa->date1!=bb->date1)

 return(((aa->date1)>(bb->date1))?1:-1);

 else

  return ((aa->no)-(bb->no));

}

int main()

{

 cin>>n;

 for(i=0;i<n;i++)

 {

   //s[i]=(char*)malloc(sizeof(char*));

   s[i].no=i+1;

   cin>>s[i].date1;

 }

 qsort(s,n,sizeof(s[0]),cmp);

 for(i=0;i<n;i++)

 {

  cout<<s[i].date1<<" ";

     cout<<s[i].no<<endl;

 }

 return 0;

}

说明：

快速排序是不稳定的，一般表现在其使用的时间是不确定的，最好情况是O((n)和最坏情况O(n的平方）而平均值是

O(nlog(n)).