關于幾種類型的快排函數的說明

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)).